DES, AES implementation and applied RSA signature from CTF challenge
Dạo gần đây mình cho tham gia 2 cuộc thi CTF là FPT UniSecAthon (vòng trường chọn đội thi SV ATTT thôi :v ) và MATESCTF 2018 round 1. Và Mình đã feed 3 bài như title, sau 1 thời gian đọc lại, làm lại mình có rút ra được tý kinh nghiệm cũng hiểu rõ hơn về 3 phần này (nói đúng ra là ban đầu gặp kiến thức chỉ là về DES, AES và RSA signature chỉ là số 0). Cả DES và AES mà mình gặp trong CTF thì thường về “block cipher mode operation” hơn là implementation của DES và AES, nên gặp trúng 2 bài về implementation mình feed “vờ lờ”, nhưng đó cũng là cơ hội để mình ngồi lại, đọc thêm và hiểu hơn về DES và AES.
- Playing with DES (FPT UniSecAthon)
[+] Đây là source challenge: link
Bài này hoàn toàn là blackbox (no source) nên là các bạn build local r tự làm thử xem :>
Vài câu đầu là warm up chăng? Tiếp nào
key = ‘9ebbd404b503cfa8’
input_block = ‘cd3bfa599dacaba9’
output_block = ‘3d37f3b01bbb31d8’
Yêu cầu: tìm 1 key mới sao cho
[+] encrypt(input_block,new_key) = output_block :hacknao:
Trước đây khi làm UIT Hacking Contest 2018 mình có gặp bài DES của @qd với yêu cầu:
[+] encrypt(encrypt(input,key1),key2) = input (:hacknao:)
Lần đó cũng là lần ngậm hành vì bị :hacknao: =))), các bạn có thể xem qua writeup :>, cái này gọi là semi-weak key
Trong DES thì có 4 weak key và 6 cặp semi-weak key, vậy weak key và semi-weak key có tính chất như thế nào?
[+] với weak key thì: encrypt(encrypt(input,key),key) = input
khi weak key qua key schedule thì sẽ tạo ra toàn 0 hoặc toàn 1 cho tất cả các Ki, điều đó có nghĩa là subkey cũng y hệt key(do được tạo từ key) có nghĩa là chỉ 1 subkey, từ đó mới có tính chất
encrypt(encrypt(input,key),key) = input
[+] với semi-weak key thì: encrypt(encrypt(input,key1),key2) = input
còn với semi-weak thì sẽ tạo ra 2 subkey khác nhau, do đó cần đến 2 key để có thể trả về input ban đầu
Note: bạn nào muốn thử xem với weak key và semi weak thì tạo key có gì đặc biệt và nó trông như thế nào thì cứ việc get 1 cái pure lib của DES trên python về debug, bạn sẽ nhìn được rõ hơn và cách hoạt động của DES.
Như thế thì cũng chả liên quan gì đến có 2 key cho ra cùng 1 output, thế là mình đã feed toàn bộ thời gian thi :<, về nhà tìm đọc thêm thì thấy rằng key trong DES thì chỉ 56 bit là được sử dụng trong quá trình mã hóa còn 8 bit còn lại chỉ là check bit :>
Đến đây thì biết làm thế nào mà 2 key ra 1 output rồi nhé =))), flip parity bit trong key1 để có được key2
Yêu cầu tiếp theo:
[+] encrypt(complement(input_block), new_key) == complement(output_block)
Vẫn với input_block và output_block ta cần tìm 1 key khác sao cho thỏa yêu cầu, lập tức google complememt
Explain : link
Có nghĩa là ta sẽ có:
[+] encrypt(input,key) = output
=> encrypt(complement(input), complement(key)) = complement(output)
Có nghĩa là chỉ cần complement key hồi nãy là ta qua được question 5
Câu hỏi này cũng là step cuối, khoai sọ và hay nhất =))
Yêu cầu:
[+] Tìm một input_block và 1 key sao cho:
encrypt(new_block, new_key) = new_block
Ban đầu nhìn vào thì cứ ngỡ đề sai =))), vì nếu encrypt(new_block, new_key) = new_block thì encryption làm vẹo gì :v, nhưng đề cho ta control cả input_block và key :thinking: . Đến đây thì mình nghĩ sẽ có liên quan đến tính chất weak key vì weak key tạo ra duy nhất 1 subkey, dựa vào đó mình tính toán ngược lại để tìm. Nói về DES thì cũng không thể không nhắc đến Feistel network
Và DES round
Như đã thấy thì DES hoạt động khá giống với Feistel network và thực hiện tất cả 16 round. Vậy hàm f trên hình có ý nghĩa và hoạt động như thế nào?
Như trên hình thì hàm f lấy 2 giá trị Ri(32 bit) và Ki (48 bit) (0<i<=16) và cho ra 48 bit. Ri sẽ được mở rộng qua expansion function và XOR với Ki.
Chú ý rằng ở round cuối thứ tự R và L sẽ thay đổi sau đó qua IP_inv và trả về output
Quay lại Question 6 vấn đề của ta là cần tìm:
encrypt(new_block, new_key) = new_block
Dùng weak key? Đúng vậy, khi mà các Ki đã cố định thì khi này hàm f() chỉ phụ thuộc Ri,điều này có nghĩa là ta đã control được, vậy bây h nhiệm vụ là tìm L,R ban đầu qua các round và IP_inv cho ra output=input? :thinking:
[+] thực chất trong Feistel network chỉ thực hiện mã hóa 1 bên (bên R), sau khi plain qua IP thì được phân thành a[0],a[1] (đều 32 bit) các a[i] tiếp theo sẽ được tính như sau:
a[i+2] = a[i] XOR f(a[i+1],K[i]) (0< i <= 16)
Note: từ a[1] trở đi thì a[i] cũng là R[i]
Giả sử cho rằng ta cần a[0],a[1] = a[17], a[16] (tất cả 16 round và do ta muốn tìm output=input) thì ta sẽ chứng minh được là mệnh đề trên tương đương với a[8] = a[9]
Như vậy thì ta chỉ cần chọn 1 giá trị bất kì nào đó cho a[8] và a[9] rồi từ đó tìm các a[0],a[1] là ta có thể chắn chắc rằng a[0],a[1] = a[17], a[16]
Để dễ dàng cho việc thực hiện reserve các a[i] thì các bạn có thể search 1 Pure DES nào đó về edit lại, còn mình sử dụng cái này: link, và 1 đoạn script nhỏ để recover lại input_block
Và đây là full script
Và ta có flag …
Với phần giải thích của mình thì mình đã tham khảo chính trên WU của tác giả bài DM COLLISION GoogleCTF Quals 2018: link và link, đây là 2 nguồn chính để mình có thể hiểu về DES cũng như là weak key trong DES. Cảm ơn a Hiếu là chuẩn bị và implement lại bài DM COLLISON :>
2. AES_return (MATESCTF 2018 Round 1)
Lại một bài về implement nhưng lần này là AES, trong thời gian thi mình nghĩ rằng nó rất khó vì với lý do mình chưa hiểu implement của AES nên cứ mặc định là khó, đó là điều mà mình tiếc nuối nhất khi giải xong bài này, sau khi giải xong thì mình cũng đã hiểu được phần nào đó về implement của AES :<
Challenge:
Challenge source code
Bắt đầu vào thì mình sẽ xem các option của challenge trước:
Với mỗi session thì sẽ tạo 1 key = os.urandom(16) cùng với đưa cho ta flag_enc với key đó và mình được chọn các option tất cả 5 lần (query = 5)
1. encrypt với key
2. to do
3. encrypt với key và sbox tùy ý :thinking:
Okay! Nhiệm vụ rõ rồi đó là tìm flag từ flag_enc mà server send lúc đầu, với option 1 thì có thể nghĩ đến Choosen Cipher Attack nhưng chỉ được request 5 lần thôi :< nên là ý tưởng này không khả thi rồi, vậy chỉ còn option 3, có nghĩa là mình được phép control sbox để từ đó tìm ra flag? Vậy thì với sbox như thế nào thì ta hoàn toàn có thể tìm flag :thinking:
Chú ý những đoạn code này xem thử là sbox có vai trò như thế nào và ta cần giá trị nào của sbox thì dễ dàng cho việc recover flag.
Chú ý rằng hàm sub_bytes mapping các giá trị theo sbox và trong tất cả các round đếu có sub_bytes. Điều này có nghĩa là nếu ta control được sbox thì có nghĩa là ta cũng control được cả sub_bytes. Vậy thì nếu sbox = 0 thì toàn bộ các giá trị của mảng s_box sẽ là 0, có nghĩa là khi sub_bytes(plain_state) với s_box là những giá trị 0 thì plain_state lúc này cũng là những giá trị 0. Sau vòng lặp còn 3 bước là: sub_bytes, shift_row và add_round_key. Điều này có nghĩa là không cần biết trong 10 round plain bị biến đổi ntn thì ở bước sub_bytes(plain_state) ngoài vòng lặp plain vẫn là 0 :magic:. Nếu sub_bytes(plain_state) = 0 thì shift_row(plain_state) cũng là 0
Vậy thì ở bước cuối cùng:
Lul =)) leak key kìa =)), leak được key round thứ 10 rồi thì recover lại key ban đầu là hoàn toàn có thể. Và ta có flag
Full script here: link
3. Moose (MATESCTF 2018 Round 1)
Link challenge: link
Bài này mình cũng feed trong thời gian thi, suy cho cùng trong thời gian thi MATESCTF 2018 Round 1 mình là thằng làm được bài welcome :< của team, may mắn có đồng đội gánh để mình có thêm động lực mà phấn đấu thêm :<.
Lần đầu gặp bài này thì cảm giác vô hướng vì rất dị, chỉ cho 1 file certificate có dạng .DER. HẾT :<<
Trong thời gian thi thì mình cũng đã lần mò gần đến flag theo hint của tác giả nhưng tiếc là vẫn không làm được :( kịp lúc
1 file certificate thông thường thì chỉ chứa các thông tin, pubkey, signature blah blah. Sau một hồi search google thì mình tìm được cách parse hết thông tin bằng “openssl asn1parse” hoặc bạn có thể dùng trang này: link để xem là trong file certificate này chứa những gì, lúc sau thì mình tìm thấy ASN1 Editor (tool này parse hết tất tần tật thuận tiện vler :> ), mà file này tại sao khi dump ra thì có tận 3 pubkey 3 sha256withRSAEncryption (signature nè) và 1 sâu rác không có ý nghĩa gì. Theo lối tác giả mình đã verify hết 3 sig này với 3 pubkey có được nhưng vẫn không được gì, đến hôm sau tác giả có up blog ý tưởng cho từng bài thì mình mới biết cái sâu rác kia là 1 thằng sig khác :sad:, mình vội vã verify nó và …
Description của bài là “what does the moose say?” là mình biết đây là flag rồi =)), vội vàng submit flag: matesctf{mo0o0O0o0o0O} thì …
What the f*ck? sao lại méo được? phải chăng là mình bỏ xót cái gì đó chăng? :feelbad:
Một đêm dài mình ngồi suy nghĩ làm đi làm lại vẫn ra con bò ấy, mạo muội nhắn hỏi idol xem có đúng không
Thế là đêm đó mình ngồi làm mãi, nghĩ đủ cách và vẫn đéo ra :((
Trưa hôm sau đang ngồi ăn cơm thì nghĩ lại: “Ủa sao bài aes_return formatflag là MATESCTF?” thế là mình nghĩ trong đầu thôi cứ thử xem flag có đúng không? Ai ngờ …
1 bài học thật đáng nhớ từ lúc chơi CTF đến h nhưng cũng đáng để remind các bạn =))).
Kể cả người anh đi trước cũng từng trải qua :<< , nên là hãy nhớ viết hoa và viết thường quan trọng như thế nào nhé :>.
Anyway Cảm ơn a Trần Minh đã mang AES implementation và RSA signature vào đề mates để em có dịp ăn hành và có thể học thêm nhiều thứ hơn. Cứ mỗi lần ăn hành thì mình có dịp học hỏi được các thứ hay hơn và mới mẻ hơn, hãy luôn xem đó là động lực mà phấn đấu :>. Điều mình rút ra là mình đã không đọc kĩ implementation của DES, AES và cứ focus nhiều vào mode operation :<
Cảm ơn các bạn đã dành thời gian ra đọc bài của mình, chúc các bạn có một ngày vui vẻ. Thanks ❤❤❤
