[SVATTT 2017 Quals] Crypto Write Up

Chào các bạn, trong vòng hơn hai tháng nghỉ để chờ vào chuyên ngành ở FPT :v mình có tập tành chơi Crypto và cảm thấy khá thích thú với mảng nay. Vừa có thể luyện code vừa có thể rèn cả tư duy lẫn bổ sung kiến thức về Cryptography. Tuần vừa qua mình tìm lại các task về crypto của đợt SVATTT này. Tuy đợt đó mình không tham gia nhưng vẫn muốn viết write up cho 3 bài crypto và mong là các bạn sẽ góp ý để mình có thể học hỏi thêm. Let's start now!!!

Crypto100-RSA

Task information : link

Có N,e đoán sơ thì có vẻ bài này liên quan đến RSA

thử factor N xem nào

Tạch rồi :(

thử factor với trường hợp p,q là close primes và Mersenne Prime thì close primes cho ta kết quả :)

Đẹp rồi. Có p,q thì phần còn lại chỉ cần chỉnh code 1 tý thôi

Here's my script: solve.py

2. Crypto100-DES (đã tự ý chỉnh flag)

Task information: link

Do mình đưa về local để chạy. Nên khó tránh được việc lộ flag :(. Bạn nào muốn làm thì run file server và xem file server thôi nha. Còn file ctf thì chớ đụng vào :(

Lướt qua file server.py thì ta nhận thấy vài điều như sau:

1. Có DES-CBC (block_size = 8)
2. pad theo phương thức PKCS#7
3. server sẽ đưa cho mình 1 đoạn cipher và công việc mình cần làm là phải send back lại 1 thứ gì đó để server trả về flag cho chúng ta

Okay ta cần send sha256() của biến challenge. Quay ngược lên ta thấy

và hàm class encrypt như sau:

Nhận thấy cipher.decode('hex').decode('hex') sẽ là (iv + cipher.encrypt(raw))

Hehe. vậy là có iv rồi , tìm key nữa là sẽ decrypt được =))

Nghĩ mãi một hồi thì thấy key chỉ có 2 bytes => có thể brute force

Vậy thì có iv, có key thì đầy đủ yếu có decrypt DES rồi. Nhưng làm sao có thế biết được plaintext trả về đúng hay ko? Okay, dựa vào pad PKCS#7 thôi =)))

Note: 'challenge' được tạo từ random.randint(24, 48)

Trường hợp nếu challenge là 48 bytes thì sau khi sẽ được pad thêm '\x08'*8 là có 56 bytes, cộng với 8 bytes iv sẽ là 64 bytes. Qua 2 lần encode hex thì sẽ có 256 bytes.

=> Request cho đến khi gặp được cipher(256 bytes hex)

Lúc này brute force key, nếu như key nào có thể decrypt sao cho thõa challege[-8:] == '\0x8'*8 thì valid. Dùng tiếp key đó decrypt ra 'challenge' và send back sha256(challenge).hexdigest() cho server và lấy flag thôi :3

Here's my script: solve.py

Crypto300 (đã tự ý chỉnh flag và key)

Task information: link

I have a special thanks to #BlackWings for the instruction

À đưa về local thì cũng chỉ xem file server thôi nhé các bạn :(

Dạo 1 vòng quanh file server.py thì ta thấy:

1. server sẽ thực hiện 2 task: một là nhận mã PIN từ user input và trả về 1 cookie(dạng base64), hai là nhận base64 và trả về mã PIN cho chúng ta
2. len(key) == 64
3. if len(pin) > 4: pin = pin[:4]
4. Cookie sẽ được tạo như sau: b64(xor(b64(plaint),key)) (xor enc ở đây là reapted-key) và plain của chúng ta ở dạng Json
5. sau vài lần fuzz input thử thì thấy rằng có mặt random

Note:

1. Để ý rằng ta có: b64_d(cookie) ^ key = b64(plain)

2. len(key) == 64

=> có nghĩa là b64_d(cookie) có độ dài thõa mãn: 64*n + len(pad) (và pad % 4 == 0)

Bắt đầu lại từ căn nguyên của base64:

1. Một chuỗi base64 sẽ bao gồm A-Z a-z 0–9 / + =
2. Mã hóa base64 sẽ như sau. Lấy mỗi 3 chars trong plain, lúc này ta có tổng cộng 24 bit, từ 24bit đó ta sẽ tách thành từng 6bit và trả về 1 char
3. Nếu như không đủ 3 chars thì sẽ pad thêm '='. Vdu: 1 char plain sẽ pad '==' cho cipher, 2 char plain sẽ pad '=' cho cipher

=> 4 chars b64 -> 1 hoặc 2 hoặc 3 char plain

Từ khái niệm cơ bản này 1 idea xuất hiện :3 (Thanks #BlackWings lần 2 =)))

Nếu như b64_d(cookie) của chúng ta có độ dài thõa : 64*n + 4 bytes, thì khi thực hiện XOR enc thì 4 bytes này sẽ XOR với key[0:4] :) :) :), ta đã biết A ^ B = C đồng thời C ^ B = A

Ta có: b64_d(cookie)[-4:] ^ key[0:4] = 4 chars b64

=> b64_d(cooke)[:-4] ^ 4 chars b64 = key[0:4]

ta đã biến plain ở dạng Json. Vậy thì 4 chars b64 này khi decode base64 sẽ phải thõa mãn: '}' '"}' hoặc '1char"}' (tất cả đều cho ra 4 chars b64). Tạo list 4 chars b64 với 3 format trên và XOR với b64_d(cookie)[-4:] ta sẽ tìm được những key[0:4]. Bây giờ làm sao để biết key[0:4] nào là key[0:4] thật :(

Ta làm như sau:

1. request 1 cipher khác có cùng độ dài ( thõa 64*n + 4 bytes)
2. dùng các key[0:4] tiến hành decrypt với 4 chars cuối ở cipher kia xem liệu có phải thõa: ‘}’ ‘“}’ hoặc ‘1char”}’. save những key thỏa mãn lại
3. request và tiếp tục dùng những key trên decrypt với cipher khác cho đến khi chỉ còn duy nhất 4 chars b64 (decode 4 chars b64 này sẽ được key[0:4])

Phần công việc còn lại là lặp và tìm những cipher có 4bytes cuối lần lượt ở vị trí key [4:8], key[8:12],...

Tiếp tục như thế cho đến khi len(key) == 64 thôi và ta sẽ có được key

Có full key rồi thì phần còn lại quá easy. Decrypt cipher and capture the flag !!!!

Here's my script: solve.py

See also: CVE-2017–9248

Thanks for reading and Happy Breaking !!!