Try   HackMD

InterKosenCTF 2020 - padrsa

Writeup

Outline

こちらが与えた平文がフラグにパディングを施し、RSAで暗号化するシステムが動いている。
3 <= e <= 65537の範囲でeを指定することが出来、パディングによって非常に長くなることも無いため、短い平文で小さいeを指定すればその結果のe乗根を取ることでパディングを特定することが出来る。
また、パディングは暗号化毎に更新されるが、前の暗号化のパディングに依存するので一度パディングを特定すれば以後のパディングは完全に特定可能になる。
これでパディングを施すと元の平文以外の部分が判明するので同じ平文を暗号化する際、パディング後の差は判明する。
したがってFranklin-Reiter Related Message Attackを適用することが出来るのでこれを使って平文を求める。

rの特定

CTF終了後に書いたWriteupと全く同じ

ある平文

m1,m2 を暗号化することを考える。ここで2つの平文はパディングが違うだけで元は同じ、といった状況で差がわかるものとする。つまり
m2am1+b:=f(m1)modn
のような形で現されるとする。
これらを暗号化すると次のようになる

c1m1e1modnc2m2e2modn

この内、下部の式から

m2 を消去して
m1
の式にすると次のようになる。

c2f(m1)e2=(am1+b)e2modn

ということで解が

m1 の次のような2つの合同方程式が得られる

g1(x):=xe1c10modng2(x):=(ax+b)e2c20modn

g1,g2 共に
x=m1
が解となるので
g1(x)(xm1)h1(x)modn
g2(x)(xm1)h2(x)modn
が成り立つはずである。
この公約式
xm1modn
を求めることでパディング付きの平文
m1
を入手することが出来る。

今回はフラグ

flag に対しパディングを施すので
m:=flag(256)8
とすると

m1=pad1+mm2=pad2+m

が成り立つので

m2=m1+(pad2pad1) の形で表すことが出来る。つまり
f(x)=x+(pad2pad1)
である。
最初にパディングの初期パラメータを求めたので
pad1,pad2
は既知である。よってこの攻撃を使うことが出来る。

Code

各種パラメータ導出(Python)

from pwn import remote from binascii import unhexlify, hexlify from Crypto.Util.number import bytes_to_long, long_to_bytes from xcrypto import int_nth_root, crt def select(s, sel, c=b"> "): s.recvuntil(c) s.sendline(str(sel)) def recv_and_unhex(s): s.recvuntil(b"c: ") raw_res = s.recvline().rstrip() res = bytes_to_long(unhexlify(raw_res)) return res def enc_flag(s, e): select(s, 1) s.recvuntil(b"e: ") s.sendline(str(e)) return recv_and_unhex(s) def enc_msg(s, e, msg): select(s, 2) s.recvuntil(b"e: ") s.sendline(str(e)) s.recvuntil(b"m: ") s.sendline(msg) return recv_and_unhex(s) def update_nonce_and_r(nonce, r): nonce += 1 r = long_to_bytes(((bytes_to_long(r) << 1) ^ nonce) & (2 ** 64 - 1)) return nonce, r if __name__ == '__main__': target = "crypto.kosenctf.com" port = 13001 s = remote(target, port) s.recvuntil(b"n: ") n = int(s.recvline().rstrip()) print("n =", n) res = enc_msg(s, 4, b"10") p_root = int_nth_root(res, 4) assert p_root ** 4 == res r = long_to_bytes(p_root)[2:] assert len(r) == 8 assert long_to_bytes(p_root)[1] == 0x10 assert long_to_bytes(p_root)[0] == (r[0] | 1) nonce = 1 nonce, r = update_nonce_and_r(nonce, r) r_1 = r top_1 = (r_1[0] | nonce) c_1 = enc_flag(s, 3) print("r_1 =", bytes_to_long(r_1)) print("top_1 =", top_1) print("c_1 =", c_1) print("e_1 =", 3) nonce, r = update_nonce_and_r(nonce, r) r_2 = r top_2 = (r_2[0] | nonce) c_2 = enc_flag(s, 5) print("r_2 =", bytes_to_long(r_2)) print("top_2 =", top_2) print("c_2 =", c_2) print("e_2 =", 5)

Franklin-Reiter Attack(SageMath)

from binascii import hexlify, unhexlify from string import printable def str_to_num(s): return int(hexlify(s), 16) def num_to_str(s): hexed = hex(s)[2:] if len(hexed) % 2 == 1: hexed = "0" + hexed return unhexlify(hexed) def gcd(a, b): while b: a, b = b, a % b return a.monic() def franklinreiter(c_1, c_2, e_1, e_2, N, a, b): P.<X> = PolynomialRing(Zmod(N)) g_1 = X^e_1 - c_1 g_2 = (a*X + b)^e_2 - c_2 # get constant term result = -gcd(g_1, g_2).coefficients()[0] return result # from python script n = 6180182076075669553847797352021705161407057822273009211975027847886592187364795585321878201219916214679512948408420492057080029954553687237543072192738343 r_1 = 5655088158697192486 top_1 = 78 c_1 = 5784246907243910588148058033857925015684589827267322084436324323001854593611520452639260633880726806080187381294234527975431737188323643138790562935147493 e_1 = 3 r_2 = 11310176317394384975 top_2 = 159 c_2 = 4765570819063457199521080761532079898191213351230012600594262540387297732107535927511105746243568592475224440637561608638399984817077961474940793569924545 e_2 = 5 for flag_length in range(11, 70): print("[+] attempting:", flag_length) pad_1 = top_1 * (256 ^ (flag_length+8)) + r_1 pad_2 = top_2 * (256 ^ (flag_length+8)) + r_2 diff = pad_2 - pad_1 plain = num_to_str(franklinreiter(c_1, c_2, e_1, e_2, n, 1, diff)) if b"KosenCTF{" in plain: print(plain)

Flag

当日はチームメイトが解きましたが、鯖が生きていたのとチームメイトが非想定解で解いていたので運営想定解で復習しました

KosenCTF{p13as3_mak4_padding_unpr3dictab13}

感想

InterKosenCTF 2020 Writeupでチームメイトの解法を取り上げましたが、こんな感じでズルをして(一般的にCTFはズルをするゲームなので悪口では無い)暗号方面の難易度を下げる非想定解より、暗号自体の地力を問われる想定解で面白かったです。
運営はCryptoボス問を想定して出したそうですが、Pwn的にズルをする非想定解もFranklin-Reiter Attackへ持ち込む想定解もどちらもそこそこ難しく、解法も綺麗だったので非想定解があってもボス問らしいという素晴らしい問題でした。

Franklin-Reiter Attackは何かで読んでその時は頭の片隅に入れていただけでしたが、この問題の復習をきっかけに思い出したのと実装まで漕ぎ着けたので良かったです。今回は使いませんでしたが、この前ステップになることもあるCoppersmith's Short Pad AttackもCTFで出る前に習得しておきたいです。

昨年のInterKosenCTFはCryptoのボス問だけ残して終えてしまい、今回はチームとしては解けたものの私の貢献は無だったので、2年連続でCryptoボス問に敗北したことになります。来年も開催があるならCryptoボス問を倒して三度目の正直を果たしたいです。

参考文献