こちらが与えた平文がフラグにパディングを施し、RSAで暗号化するシステムが動いている。
3 <= e <= 65537
の範囲でe
を指定することが出来、パディングによって非常に長くなることも無いため、短い平文で小さいe
を指定すればその結果のe
乗根を取ることでパディングを特定することが出来る。
また、パディングは暗号化毎に更新されるが、前の暗号化のパディングに依存するので一度パディングを特定すれば以後のパディングは完全に特定可能になる。
これでパディングを施すと元の平文以外の部分が判明するので同じ平文を暗号化する際、パディング後の差は判明する。
したがってFranklin-Reiter Related Message Attackを適用することが出来るのでこれを使って平文を求める。
CTF終了後に書いたWriteupと全く同じ
ある平文
これらを暗号化すると次のようになる
この内、下部の式から
ということで解が
この公約式
今回はフラグ
が成り立つので
最初にパディングの初期パラメータを求めたので
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)
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)
当日はチームメイトが解きましたが、鯖が生きていたのとチームメイトが非想定解で解いていたので運営想定解で復習しました
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ボス問を倒して三度目の正直を果たしたいです。
e
に対応するようにした