math314のブログ

主に競技プログラミング,CTFの結果を載せます

SECUINSIDE 2014 prequal writeup

竹田氏 500pt 52th でした

pillow_reader crypto 200pt

唯一のcryptoだった。

ファイルをダウンロードすると python3.2aのコンパイル済みのpycが来る。

pillow_reader.pycにPrimeUtilが必要との事なので、要求される関数を実装することで、import出来る状態にする。

デコンパイル出来ないかなーと探していたら unpyc3.py というモジュールが合ったので、それを使った。

さてデコンパイルと思いきや、PKIデコンパイル出来ない。 調べてみると PKI.PKI.encryptの中間コード -> .py への変換が失敗していた 仕方ないのでここだけ手動で直す

p,q = 256bit以下のランダムな素数
n = p * q
l = (p-1) * (q-1) # l = phi(n)
m = l^-1 (mod n)
g = n+1

となっている。 ここで暗号化は

def encrypt(plain):
    # r はランダムな素数
    cipher = pow(g,plain,n**2) * pow(r,n,n**2) % n**2

となっている。 phi(n2) = n*l であるから、 cipherl = gplain * l (mod n2) が成り立つ g = n+1 より、 gplain * l % n**2 = plain * l * n + 1 式変形して (cipherl - 1) / n = plain * l (mod n) l^-1 = m より、 plain = (cipherl - 1) / n * m これがdecryptの式

パケットを見ると こっちの82byteのkey 0x5cb94b9d25716136c6b880bf791f743ecfdf5a383b3aa27093c1673599cbd8a1c160e4a06f777c5b163f0fec50405944d9764bed8c7dd9eb19abc1225b322ed むこうも0x83byteくらいのキーを渡しているのが分かる 0x86e05276d3c364cd6157e23cd972e0a662dff9ebf9ade83eae022c292c767bcd6cf528c7f6ae98af2f7811d99c9e45e7e4e6f1b9841aabf89a84dd0673099b61

向こうから送られてくる鍵が同じなので、pcapからこちらの送るcipherを真似してやれば、adminkeyを調べる必要がなくなる

恐らく raw = 'cat secret\n' を送った時のcipherが

cipher = [0x80,0x00,0x00,0x00,0x1f,0x59,0x85,0x6d,0xbb,0xbe,0x90,0x99,0x5c,0xf9,0x49,0x75,
0xaf,0xd9,0x4d,0xcf,0x46,0xbf,0x2d,0x16,0xd8,0xb8,0xa3,0x75,0x46,0x85,0xd3,0xeb,
0x37,0x65,0xd6,0x91,0x84,0x62,0x37,0x8a,0x2f,0x7e,0x94,0x81,0x82,0xe8,0x4a,0x85,
0x7a,0x25,0xbe,0x05,0x7a,0x12,0x2e,0x9d,0x65,0xe3,0x2f,0xb0,0x1a,0x98,0x4f,0x44,
0x2e,0x78,0x1f,0xa0,0x2e,0x8a,0x4d,0x27,0x28,0xb1,0xa4,0xc3,0xea,0x39,0x05,0xaa,
0x95,0xab,0x9f,0xba,0x7b,0x7d,0xfa,0x3b,0x39,0x11,0x6d,0x49,0xc1,0x0d,0x16,0x17,
0x25,0xaa,0x0b,0xee,0xac,0x18,0xb7,0xa2,0xa9,0xc9,0xd5,0x5a,0x0b,0xf6,0xf1,0xa2,
0xb2,0xca,0x90,0x3e,0xb1,0x50,0x86,0x99,0x5b,0x2f,0x77,0xd7,0x7d,0x3f,0x01,0x67,
0x87,0x08,0xee,0x60]

である。 これを送ればsecretが見れる

'to get flag, just concat flag1 and flag2.' と帰ってくるので、 'cat secret\n flag1 flag2' と送れば良いことになる。 これはlength extension attack.

追加する文字列の長さを k = len(' flag1 flag2') とすれば additional_value = s2i(' flag1 flag2') として、

cipher_2 = pow(cipher,256 ** k,n ** 2) * pow(g,additional_value,n ** 2) % n ** 2

このcipher_2を送れば良いことが分かる

The flag is "7h053 wh0 bu1ld b3n347h 7h3 574r5 bu1ld 700 l0w."(without quote)