[Sharif University CTF Quals 2013] one Line encoder For Specialist pRogrammer (crypto200)

[python]>>> len(key)
9
>>> set(key)
set([‘1’, ‘0’])
>>>
>>>
>>> suctf_enc = lambda text, key: reduce(lambda x, y: (x[0] + str(int(y) ^ int(x[1][0])), x[1][1:] + str(int(x[1][4]) ^ int(x[1][0]))), ”.join(map(lambda x: bin(ord(x))[2:].rjust(8, ‘0’), text)), (”, key))[0]
>>>
>>>
>>> suctf_enc(text, key)
‘10100101011010000001001011101110010000001000010111000001101000110010110110001010100000001110010001111011010101100110101001111111001110010110101111111011100000001011110101111100010101001111100011011111111011000110100010000011000110100000010111101100010110000000110010101001100001101110110111101101001001001101010100001101100101001000111110110110001111001000011000011000110000100100001001001100011101101111111101010101000010101110001100010011000111010110010101101011111100111000010100100001000001101010111111011101101110000111111000000000011111010011011010100010000101111100100111000001111001111010101001101110110110011001111101110011100111101100001101101011010110111011111011001100001111001000101101010100000000010011001001110000101100011101011010101100001011101001110010010110111011011011101001110110010000000010100100101000101001001000100110101110111111101111100010101001101110111110010010101011001001100000000101110001001110100010011010100110100001001010111011101111011000111100111010000011111001111010110010110011001000000100010001111001101111100101000110011111’
>>>
>>> # flag = md5(key)[/python]

 

Có thể để ý ngay những chữ viết hoa trong tên bài, nó là LFSR, nhưng kệ boss

Nội dung chính

Ở bài này, chúng ta có một hàm encode, đầu vào là một xâu text và một khóa key. Dựa vào kết quả trả về của hàm len(key) và set(key), ta biết được 2 thông tin:

  • Key dài 9 ký tự.
  • Key chỉ chứa ‘0‘ và ‘1‘.

Như vậy, mình tin chắc rằng mình sẽ làm được, với lựa chọn cho bước đường cùng là brute key để submit. Kế hoạch cụ thể mình đã có, đó là submit từng key cách nhau 10s, tức 1 phút được 6 key, một giờ được 360 key, khoảng 2h sẽ xong. Nếu vẫn bị BTC phát hiện thì đẩy interval lên và cắm máy qua đêm sexy_girl

Tà đạo đã xong, giờ là chính đạo. Tiến hành viết lại cái hàm encode của họ như sau (nói thật là mình mất không hề ít thời gian để đọc về lambda, map và reduce, vì dù nó đơn giản thật nhưng khi áp dụng vào bài cho thì mình lại hơi bị loạn, khá ức chế):

[python]def text_to_bin(text):
return ”.join(map(lambda x: bin(ord(x))[2:].rjust(8, ‘0’), text))

def suctf_enc_rewrite(text, key):
cipher, current_key = (”, key)

for y in text_to_bin(text):
cipher += str(int(y) ^ int(current_key[0]))
current_key = current_key[1:] + str(int(current_key[4]) ^ int(current_key[0]))

return cipher[/python]

Có thể thấy thuật toán mã hóa là rất đơn giản, byte-to-byte bằng phép toán XOR huyền thoại. Chúng ta viết hàm decode như sau:

[python]import binascii

def bin_to_text(bin):
hex = ‘%x’ % int(bin, 2)
if (len(hex) % 2 == 1):
hex = ‘0’ + hex

return binascii.unhexlify(hex)

def suctf_decode(cipher, key):
plain, current_key = (”, key)

for y in cipher:
plain += str(int(y) ^ int(current_key[0]))
current_key = current_key[1:] + str(int(current_key[4]) ^ int(current_key[0]))

return bin_to_text(plain)[/python]

và tiến hành brute để tìm key:

[python]cipher = ‘10100101011010000001001011101110010000001000010111000001101000110010110110001010100000001110010001111011010101100110101001111111001110010110101111111011100000001011110101111100010101001111100011011111111011000110100010000011000110100000010111101100010110000000110010101001100001101110110111101101001001001101010100001101100101001000111110110110001111001000011000011000110000100100001001001100011101101111111101010101000010101110001100010011000111010110010101101011111100111000010100100001000001101010111111011101101110000111111000000000011111010011011010100010000101111100100111000001111001111010101001101110110110011001111101110011100111101100001101101011010110111011111011001100001111001000101101010100000000010011001001110000101100011101011010101100001011101001110010010110111011011011101001110110010000000010100100101000101001001000100110101110111111101111100010101001101110111110010010101011001001100000000101110001001110100010011010100110100001001010111011101111011000111100111010000011111001111010110010110011001000000100010001111001101111100101000110011111’
for k in range(512):
key = bin(k)[2:].rjust(9, ‘0’)
print k, key
print suctf_decode(cipher, key)[/python]

Output chỉ cho ra một giá trị duy nhất khả quan (thì tất nhiên là vậy rồi emo_popo_sweat):

[sh]408 110011000
in computing a linear feedback shift register lfsr is a shift register whose input bit is a linear function of its previous state [/sh]

flag = md5(key) = d2fa68bb166dde1c720bd0c8fd665bae.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *