DiceCTF 2022 - commitment-issue

TL;DR

• RSAをベースにしたCommitment Scheme(?) が用いられ、その際にフラグが使われているがその値は他のパラメータに比べると小さい
• 与えられた値から2変数多項式を構成して、片方の解に関する終結式を求めてからその解をCoppersmith's Attackで求めればフラグが得られそうだが、片方の多項式の次数が大きすぎる
• もう片方の多項式は1変数($x$)な上に次数も小さいので大きい方の多項式の$x$に関する項を割って次数を小さくし、現実的な次数の終結式を求める

Prerequisite

• 終結式
• Coppersmith's Attack

Writeup

次のようなスクリプトとその実行結果が配られる

from random import randrange
from Crypto.Util.number import getPrime, inverse, bytes_to_long, GCD

flag = b'dice{?????????????????????????}'
n = 5

def get_prime(n, b):
	p = getPrime(b)
	while GCD(p - 1, n) != 1:
		p = getPrime(b)
	return p

p = get_prime(n, 1024)
q = get_prime(n, 1024)
N = p*q
phi = (p - 1)*(q - 1)

e = 0xd4088c345ced64cbbf8444321ef2af8b
d = inverse(e, phi)

def sign(message):
	m = bytes_to_long(message)
	return pow(m, d, N)

def commit(s, key, n):
	return (s + key) % N, pow(key, n, N)

def reveal(c1, c2, key, n):
	assert pow(key, n, N) == c2
	return (c1 - key) % N

r = randrange(1, N)
s = sign(flag)
c1, c2 = commit(s, r, n)

print(f'N = {hex(N)}')
print(f'c1 = {hex(c1)}')
print(f'c2 = {hex(c2)}')

フラグを$m$とおくと、ある乱数$r$を用いて次のような関係が成り立っている。

$$\begin{aligned} s &\equiv m^d \mod N \cr c_1 & \equiv s + r \mod N\cr c_2 & \equiv r^5 \mod N \end{aligned}$$

この内、RSAの公開鍵以外に$c_1, c_2$のみが開示される。また、フラグの長さは31文字なので$m \leq 2^{248}$が成り立っている。

フラグが小さいのでなんとなくCoppersmith's Attackや格子基底簡約を使ってフラグを直接求める予感がする。ところが、$c_1, c_2$には$s$という形でしか$m$の情報が含まれておらず、しかも$s$は$N$に近い大きさになるはずで$m$に直さないとこれらのテクニックは使えない。

自然と思いつくのは、$m \equiv s^e \mod N$を利用して$(c_1 - r)^e \equiv m \mod N$とすることである。これによって次のような$\mathbb Z/N\mathbb Z$上の2つの多項式$f_1, f_2$は$x=r, y=m$を解に持つ。

$$\begin{aligned} f_1(x,y) &\coloneqq (c_1 - x)^e - y \cr f_2(x) &\coloneqq x^5 - c_2 \end{aligned}$$

このような状況から$m$を求める方法としてRSAに対するCoppersmith's Short-Pad Attackと同じ要領で終結式を用いることが挙げられる。$x$を消去するような終結式を求めてそれをCoppersmith's Attackを用いて$y$について解けば$y=m$が解として出てくることが期待される。

ところが、$f_1$の$x$の次数は$e$であり、これは非常に大きなことから、終結式を求めたとしても次数が大きくなってCoppersmith's Attackは使えそうに無い。そもそも$f_1$はメモリに乗らないレベルの巨大な多項式になる。

(※この辺で苦しんだので他人のWriteupをちょっと読んだ)

そこで$f_1$の$x$の項を$f_2$で割って、$f_1(x,y) = Q(x)f_2(x) + R(x) - y$となる$R(x)$を考える($R$の次数は高々4)。$f_2$は$r$を根に持つので$f_1(r,y) = R(r) - y$となり、当然$f_1(r,m) = R(r) - m = 0$となるから、$f_3(x,y) \coloneqq R(x) - y$を$f_1$の代わりに用いることが出来る。

多項式$R$の求め方はバイナリ法でやる方法が真っ先に思いついたが、実装が面倒なのでSageの商環を求めるメソッド.quo(<poly>)を使った。

というわけで$f_2,f_3$の終結式を$x$についてとると¹$y$の多項式になっているはずなので、これを.small_roots()で解けばフラグが得られる。

Code

from Crypto.Util.number import long_to_bytes


N = 0xba8cb3257c0c83edf4f56f5b7e139d3d6ac8adf71618b5f16a02d61b63426c2c275ce631a0927b2725c6cc7bdbe30cd8a8494bc7c7f6601bcee5d005b86016e79919e22da4c431cec16be1ee72c056723fbbec1543c70bff8042630c5a9c23f390e2221bed075be6a6ac71ad89a3905f6c706b4fb6605c08f154ff8b8e28445a7be24cb184cb0f648db5c70dc3581419b165414395ae4282285c04d6a00a0ce8c06a678181c3a3c37b426824a5a5528ee532bdd90f1f28b7ec65e6658cb463e867eb5280bda80cbdb066cbdb4019a6a2305a03fd29825158ce32487651d9bfa675f2a6b31b7d05e7bd74d0f366cbfb0eb711a57e56e6db6d6f1969d52bf1b27b
c1 = 0x75240fcc256f1e2fc347f75bba11a271514dd6c4e58814e1cb20913195db3bd0440c2ca47a72efee41b0f9a2674f6f46a335fd7e54ba8cd1625daeaaaa45cc9550c566f6f302b7c4c3a4694c0f5bb05cd461b5ca9017f2eb0e5f60fb0c65e0a67f3a1674d74990fd594de692951d4eed32eac543f193b70777b14e86cf8fa1927fe27535e727613f9e4cd00acb8fab336894caa43ad40a99b222236afc219397620ca766cef2fe47d53b07e302410063eae3d0bf0a9d67793237281e0bfdd48255b58b2c1f8674a21754cf62fab0ba56557fa276241ce99140473483f3e5772fcb75b206b3e7dfb756005cec2c19a3cb7fa17a4d17f5edd10a8673607047a0d1
c2 = 0xdb8f645b98f71b93f248442cfc871f9410be7efee5cff548f2626d12a81ee58c1a65096a042db31a051904d7746a56147cc02958480f3b5d5234b738a1fb01dc8bf1dffad7f045cac803fa44f51cbf8abc74a17ee3d0b9ed59c844a23274345c16ba56d43f17d16d303bb1541ee1c15b9c984708a4a002d10188ccc5829940dd7f76107760550fac5c8ab532ff9f034f4fc6aab5ecc15d5512a84288d6fbe4b2d58ab6e326500c046580420d0a1b474deca052ebd93aaa2ef972aceba7e6fa75b3234463a68db78fff85c3a1673881dcb7452390a538dfa92e7ff61f57edf48662991b8dd251c0474b59c6f73d4a23fe9191ac8e52c8c409cf4902eeaa71714
e = 0xd4088c345ced64cbbf8444321ef2af8b

PRx.<x> = PolynomialRing(Zmod(N))
PRxy.<x2,y2> = PolynomialRing(Zmod(N))

f2 = x^5 - c2
QR.<x3> = PRx.quo(f2)

_f = (c1 - x3)^e
f1 = _f.lift()

f1 = f1.change_ring(PRxy) - y2
f2 = f2.change_ring(PRxy)

f1 = f1.subs(x=x2)
f2 = f2.subs(x=x2)

# stolen from my `Coppersmith's Short-Pad Attack` script
h = f2.sylvester_matrix(f1, x2).det().univariate_polynomial().monic()
roots = h.small_roots(X=2**248, epsilon=1/20)

for r in roots:
    print(long_to_bytes(int(r)))

Flag

dice{wh4t!!-wh0_g4ve_u-thE-k3y}

Resources

• dicectf-2022-challenges/crypto/commitment-issues at master · dicegang/dicectf-2022-challenges: 問題ファイル
• DiceCTF 2022 Writeup | y011d4.log: $(c_1 - x)^e$を$x^5 - c_2$で割るという発想はここから