CRYPTO
1. CRY301 (1000 pts)
Một bài crypto giải bằng kiến thức toán học và tư duy về code. Full source code đề bài xem tại đây
Bài này yêu cầu mình tìm được số xban đầu từ kết quả của 2 hàm easyone(x) và alittlebitharderone(x).
a. Phân tích hàm easyone(x)
Nhìn sơ qua hàm easyone(x), có 3 phép biến đổi chính được lặp đi lặp lại 3 lần
- Phép xor với left shift bit của chính nó
- Phép nhân
- Phép & với
0xffffffffffffffffffffffffffffffff.
def easyone(x):
assert(x < 2 ** 128)
x ^= x >> (64 + 19)
x *= 0xd3856e824d9c8a26aef65c0fe1cc96db
x &= 0xffffffffffffffffffffffffffffffff
x ^= x >> (64 + 3)
x *= 0xe44035c8f8387dc11dd3dd67097007cb
x &= 0xffffffffffffffffffffffffffffffff
x ^= x >> (64 + 20)
x *= 0xc9f54782b4f17cb68ecf11d7b378e445
x &= 0xffffffffffffffffffffffffffffffff
x ^= x >> (64 + 2)
return x
Như vậy, có 2 bài toán đặt ra cần giải quyết:
- Tìm x biết ax = b \pmod na∗x=b(modn) với aa, bb, nn* đã biết.
- Khôi phục lại kết quả phép xor. Tìm x có a \oplus x = ba⊕x=b với aa, bb đã biết. Khá đơn giản với x=a \oplus bx=a⊕b.
Cùng đi sâu hơn chút vào từng bài toán 1 nhé
Bài toán 1: Tìm x biết ax = b \pmod na∗x=b(modn) với aa, bb, nn* đã biết.
Đây là bài toán cơ bản cơ bản về inverse mod (modular inverse) trong finite field (trường hữu hạn). Đơn giản, mình có thể tìm xx bằng cách x = a^{-1} b \pmod nx=a−1∗b(modn), trong đó a^{-1} \pmod na−1(modn) là giá trị inverse modulo của a trong finite field \bmod (n)mod(n*).
Chi tiết cách tìm inverse mod bằng toán học với extended euclidean algorithm có thể xem tại đây. Lúc code giải thì mình dùng luôn hàm invert(a, n) trong thư viện gmpy2 của python để tìm a^{-1} \pmod na−1(modn)
Mình chuyển 1 đoạn code sang dạng bài toán gốc để dễ hình dung. Cụ thể, đoạn code dưới đây biểu diễn dưới dạng toán học sẽ là x 281159923981539500379670095774511568603 = b \pmod nx∗281159923981539500379670095774511568603=b(modn) với bb* có thể thu được từ việc dịch lại phép xor (sẽ nói ở bài toán 2).
Lưu ý: x &= 0xfffffffffffffffffffffffffffffffftương đương với x %= 0xffffffffffffffffffffffffffffffff, hay x %= 2**128
x *= 0xd3856e824d9c8a26aef65c0fe1cc96db #281159923981539500379670095774511568603
x &= 0xffffffffffffffffffffffffffffffff
Như vậy, ta có thể dễ dàng tìm xx với x = b281159923981539500379670095774511568603^{-1} \pmod {2^{128}}x=b*∗281159923981539500379670095774511568603−1(mod2128).
x *= gmpy2.invert(268448390289851351177030176676964262981, 2**128)
x &= 0xffffffffffffffffffffffffffffffff
Vấn đề là để hoàn thiện quá trình giải thì mình cần tìm bb, nghĩa là cần phải giải quyết bài toán số 2. Ngay sau đây 
Bài toán 2: Khôi phục lại kết quả phép xor
Để giải quyết phần xor này, chúng ta cần phải lưu tâm x sau khi bitshift thì còn những bit nào còn giữ nguyên, bit nào dịch chuyển để thực hiện xor.
x ^= x >> (64 + 2)
Để dễ hình dung, bạn có thể nhìn hình mô phỏng trước và sau khi leftshift dưới đây. Bit màu xanh là những bit còn giữ nguyên sau khi leftshift. Bit màu vàng là bit màu xanh được chuyển ra sau khi leftshift. Bit màu đỏ là những bit có thể bị thay đổi sau bitshift (và cũng là bit thực sự tham gia xor)
Dễ dàng nhận thấy, phần bit dùng để xor với giá trị x ban đầu vẫn giữ nguyên sau khi xor \longrightarrow⟶ Như vậy mình có thể dễ dàng khôi phục phần bit dùng để xor bằng cách leftshift lại giá trị sau khi xor bằng đúng một khoảng dùng để xor trước đó (tức leftshift (64+2) đơn vị trong trường hợp trên).
x ^= x >> (64 + 2)
Kết luận trên đúng với tất cả trường mà x được leftshift ít nhất 64 đơn vị.
Vậy là mình đã giải quyết xong cả 2 bài toán trên! Cuối cùng mình có đoạn code để lấy giá trị x từ hàm easyone(x) như sau:
def solveeasyone(x):
x ^= x >> (64 + 2)
x *= gmpy2.invert(268448390289851351177030176676964262981, 2**128)
x &= 0xffffffffffffffffffffffffffffffff
x ^= x >> (64 + 20)
x *= gmpy2.invert(303397380928069120521467215513016862667, 2**128)
x &= 0xffffffffffffffffffffffffffffffff
x ^= x >> (64 + 3)
x *= gmpy2.invert(281159923981539500379670095774511568603, 2**128)
x &= 0xffffffffffffffffffffffffffffffff
x ^= x >> (64 + 19)
return int(x)
Tada, first round~~
b. Phân tích hàm alittlebitharderone(x)
Giải quyết hàm này cũng cần giải quyết 2 bài toán như hàm easyone(x). Bài toán 1 về tìm inverse mod hoàn toàn giống hệt. Cái khó hơn nằm ở Bài toán 2, do mình không thể ngay lập tức khôi phụ được bit dùng trong phép xor trước đó từ kết quả thu được.
Tuy nhiên, điều đáng mừng là nguyên lý cách làm vẫn thế. Chúng ta cũng sẽ dùng những bit còn nguyên, để khôi phục lại những bit gốc, rồi lân la dần dần để khôi phục toàn bộ bit gốc đó. Mình mô phỏng với 1 bài toán nhỏ với 1 chuỗi 6 bit với độ leftshift bằng 2 như sau:
Với trường hợp như trên, mình khôi phục lại giá trị ban đầu của x bằng cách đi qua từng bước như sau đây (Mô tả bằng hình ảnh cho dễ hiểu nhé)
Xor 2 bit đầu (2 bit còn giữ nguyên sau khi xor) với 2 bit liền kều sau nó. Những bit còn lại giữ nguyên. Như vậy, mình đã khôi phục lại được bit số 3 và bit số 2
Xor tiếp 2 bit vừa thu được (bit số 3 và 2) với 2 bit liền kề sau nó để khôi phục tiếp 2 bit còn lại (bit 5 và 6)
Vậy làm mình đã thu lại được đoạn bit gốc, tức giá trị của x cần tìm. Với chuỗi bit dài hơn, mình chỉ cần chạy quá trình trên lặp đi lặp lại là được.
Dễ rồi phải không? Mặc dù mình nghĩ ra được ý tưởng mình việc code tốn của mình tận 30 phút... và cuối cùng lại chỉ thành 1 đoạn code ngắn ngủi sau:
def xor(a, b):
return ''.join(str(int(_a) ^ int(_b)) for _a, _b in zip(a, b))
def shiftsolong(x, bitshift):
x = '{0:b}'.format(x)
for i in range(0, len(x) - bitshift):
x = x[:bitshift*(i+1)] + xor(x[bitshift*i:bitshift*(i+1)], x[bitshift*(i+1):bitshift*(i+2)]) + x[bitshift*(i+2):]
return int(x, 2)
Ta nói đời về căn bản là buồn mà 
Thôi tổng hợp lại, thì mình có đoạn code lấy lại giá trị x từ hàm alittlebitharderone(x)
def solvehardone(x):
x = shiftsolong(x, 2)
x *= gmpy2.invert(268448390289851351177030176676964262981, 2**128)
x &= 0xffffffffffffffffffffffffffffffff
x = shiftsolong(x, 20)
x *= gmpy2.invert(303397380928069120521467215513016862667, 2**128)
x &= 0xffffffffffffffffffffffffffffffff
x = shiftsolong(x, 3)
x *= gmpy2.invert(281159923981539500379670095774511568603, 2**128)
x &= 0xffffffffffffffffffffffffffffffff
x = shiftsolong(x, 19)
return int(x)
Qua vòng 2 và nhận được flag. Chỉ là không kịp submit nữa...
Nếu có ước muốn trong cuộc đời này, mình sẽ ước có một không gian riêng mà thời gian chảy chậm để ngồi debug trước khi hết giờ FUSEC 
2. CRY302 (1000 pts)
1 bài liên quan tới hash, cách thực hiện khá dễ. Full source code bạn có thể xem tại đây
a. Bổ đề
Tóm tắt lại thì mình sẽ được đưa cho 1 số tiền ngẫu nhiên từ 1 tới 2000 và bị bắt phải mua 1 cái FLAG có giá tận 99,999. Kiểu gì cũng không đủ cho được.
Khi mình order 1 vật phẩm bất kỳ, order của mình sẽ có cấu trúc dạng kiểu product=FLAG&price=99999&time=1633845957.70&sign=67df43a8c83ea4ee53ac7bb61cc9a51661f5b55b54153afb942246c11a3ab9a93cb7a1cecb235195eab957fceb3e3daaf3e97f484d29718aea8b0f63e1a3704a (đã được decode từ chuỗi base64 encoded)
Khi nhập lại cái order ở trên để xác nhận mua sản phẩm, order này được kiểm tra các cấu trúc và tính toàn vẹn, cụ thể gồm:
- Tồn tại cặp parameter-value
sign={sign_value} - Có signature hợp lệ
sha512(signkey+payment).hexdigest() == signature
Sau khi qua các bài check trên, payment sẽ được truyền vào hàm parse_sql(self, query) để tiến hành extract các parameter tương ứng.
def parse_qsl(self, query): m = {} parts = query.split(b'&') for part in parts: key, val = part.split(b'=') m[key] = val return m
Với cách hàm parse hoạt động như này, giả sử query có 2 cặp giá trị của price (ví dụ như price=99999&price=0) thì giá trị price cuối cùng sẽ được quyết định bởi cái đằng sau. Điều đó đồng nghĩa với việc nếu mình có thể kéo dài cái payment của mình bằng cách append thêm 1 đoạn &price=0, mình có thể mua bất cứ thứ gì trong cửa hàng!
Ý tưởng kéo dài 1 đoạn payment được hash đã đưa mình đến hash length extension attack
b. Hash length extension attack
Hash length extension attack là gì?
Hash length extension attack cho phép mình kéo dài chuỗi văn bản được hash, đồng thời tính toán giá trị hash mới hợp lệ cho chuỗi văn bản được kéo dài ra từ hash của chuỗi văn bản ban đầu.
Nguồn đọc hiểu hash length extension attack
Trước hết, cần phải hiểu được sha512 hoạt động như thế nào đã. Bạn có thể xem tổng quan về hàm sha512 tại đây và xem chi tiết cách sha512 vận hành từng bước 1 tại đây. Thanks for Indian guys 
Tiếp đó, mình đọc mô tả cách hash length extension attack hoạt động, và có bản demo tại đây. Thực ra trước có 1 bài blog bằng tiếng Việt cho họ hash SHA luôn, mà giờ trang đấy sập rồi Nên mình sẽ mô tả lại trong bài này để các bạn hiểu dưới góc độ python code, phòng trường hợp các bạn đọc demo trên mạng đều code bằng C và không hiểu gì =)))
Điều kiện để thực hiện hash length extension attack
Để thực hiện được hash length extension attack mà văn bản xác thực có dạng secret_value + public_value, mình cần có đủ 3 dữ kiện:
- Độ dài của
secret_value, ở trong bài này chính là độ dài của signkey. Bài không cho cụ thể nhưng chỉ cho 24 giá trị khả năng, hoàn toàn có thể bruteforce. Mình không cần giá trị của secret_value! - Giá trị của
public_value, ở trong bài này chính là payment - Giá trị hash của
secret_value + public_value, ở trong bài này chính là sign
Vậy là bài này hội tụ đủ cả 3 yếu tố để tiến hành rồi.
Tiến hành tấn công thôi!
Mục tiêu của mình bao gồm:
- Append thêm 1 đoạn
&price=0 vào cuối payment - Tạo ra 1 giá trị
sign mới sao cho sha512(signkey+payment) = sign với payment mới
Sơ sơ cơ chế hoạt động của hash length extension attack sẽ như sau.
- Cơ chế hoạt động của hàm hash: Hàm hash sha512 sẽ chia input đầu vào thành các khối 1024 bits, mỗi khối lại chia thành từng phần nhỏ
h[i]gồm 128 bits. Một tuple (h[0], h[1], h[2], h[3], h[4], h[5], h[6], h[7]) được gọi là current_state của hàm hash hiện tại. current_state sẽ được dùng để tính state cho khối 1024 bits tiếp theo. Hàm xử lý quá trình này gọi là round_function hoặc compress (tùy theo tài liệu). Kết quả cho khối 1024 bits cuối cùng chính là giá trị hash mình thu được. - Cơ chế hoạt động của hash length extension attack: Từ cơ chế hoạt động trên của hàm hash, mình có thể thấy rằng chỉ cần biết được
current_state và khối 1024 bits cuối cùng, mình hoàn toàn có thể tính toán state cho khối 1024 bits tiếp theo, trong đó, khối 1024 bits sẽ có giá trị tùy ý mình thích. Đó cũng chính là giá trị hash mới với chuỗi văn bản được kéo dài.
Khá là đơn giản phải không. Giờ mình sẽ đi vào cụ thể nhé:
- Order FLAG, nhận giá trị
order trả về product=FLAG&price=99999&time=1633849486.36&sign=275e626950c677c05a669e4e9d73f015858ca2b477335b2e99f419f9f0bc860736e95bd87de1226764c70f8c59029edc10e6b2a514342bb85f0c29fe24b9d3e2. Tách payment và sign riêng. - Padding cho
payment để payment có dạng k1024k*∗1024, và lấy block cuối cùng, thu được product=FLAG&price=99999&time=1633849486.36\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02P. Vốn chuỗi ban đầu không dài hơn 1024 bits nên cũng chỉ có block duy nhất. Trong phần ví dụ này, mình giả sử độ dài của signkey bằng 31. Cơ chế padding mình đính kèm nguồn ở trên. - Append chuỗi
&price=0 vào chuỗi đã được padding ở trên. Lại tạo 1 khối 1024 bits có chứa &price=0 bằng cách padding, thu được &price=0\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x018 - Extract
state từ giá trị sign, sau đó đưa state cùng khối 1024 bits có chứa &price=0 ở trên vào hàm compress của sha512, thu được giá trị sign mới bằng ad38b9ceecbdf41de6bb33970a473ecc1c500935e2cfd90007be639fa6754b6272c45340fca0f173090748722cc1e25e3440cc9975c3b712a8cabe7809cf6d7f - Nối chuỗi
payment mới và sign mới vào với nhau, chuyển lên server và lấy flag. order mới sẽ là product=FLAG&price=99999&time=1633849486.36\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02P&price=0
Vậy là xong!
c. Full code exploit
Vì bài không cho giá trị cụ thể của độ dài signkey, nên mình phải viết 1 đoạn code chạy tự động trong khoảng giá trị [8, 32][8,32]. Full code exploit có thể xem ở đây. Trong code này, mình có sử dụng lại thư viện hlextend của stephenbradshaw trên github, với một chút chỉnh sửa để output ra có dạng byte thay vì string.
def solve():
[REDACTED]
#order
output = recvuntil(clientSock, b'Your choice:')
clientSock.sendall(b'2\n')
output = recvuntil(clientSock, b'ID:')
clientSock.sendall(b'6\n')
output = recvuntil(clientSock, b'Your choice:')
order = output.split(b'\n')[0][len('Your order:'):].strip()
order = b64decode(order).decode('latin-1')
sp = order.rfind('&sign=')
sign = order[sp+6:]
payment = order[:sp]
append_msg = '&price=0'
for i in range(8, 33):
sha = hlextend.new('sha512')
new_payment = sha.extend(append_msg, payment, i, sign)
new_sign = sha.hexdigest()
new_order = new_payment + b'&sign=' + new_sign.encode()
new_order = b64encode(new_order)
#confirm order
clientSock.sendall(b'3\n')
output = recvuntil(clientSock, b'Your order:')
clientSock.sendall(new_order + b'\n')
output = recvuntil(clientSock, b'Your choice:')
if b'FUSec{' in output:
flag = output.decode()[output.index(b'FUSec{'):output.index(b'}')+1]
print(flag)
break
Flag FUSec{th1s_1s_4n_0ld_vul_bUt...}
3. CRY303 (991 pts)
Một bài siêu khó về Knapsack cipher sử dụng LLL (Lenstra–Lenstra–Lovász), hay còn gọi là Latice Reducation Technique, để giải.
Nói thật thì bài này mình cũng không tự làm được lúc tham gia giải CTF, nhưng search google được 1 bài giống tới 90%, nên chỉ đọc hiểu code rồi giải lại. Bởi vì bài cũng không có gì khác biệt mấy, nên mình để nguồn bài gốc ở đây để các bạn đọc vậy.
Đề bài này và code giải (đã sửa theo bài) mình để ở github của mình.
Thế là hết crypto rồi. Nếu mà kịp giải hết thì mình cũng mạnh dạn insert bomman meme gáy... nhưng không được nên gà không gáy nữa...
written by thangpd3160
