はじめに

SECCON Beginners CTF 2023 の Crypto (cooking) の作問を担当させていただきましたのでその writeup を書いていこうと思います。

まず始めに作問ミスで日本で最も有名な CTF の場を荒らしてしまってすみません。
しばらくサーバーは空いていると思うので参加できなかった方もぜひ他の優秀な方々の問題を解いて楽しんでもらえたら幸いです。

開催概要
- スコアサーバURL：https://score.beginners.seccon.jp/
- 開始時刻：2023/06/03 (土) 14:00 JST
- 終了時刻：2023/06/04 (日) 14:00 JST

[crypto] cooking

from Crypto.Util.number import isPrime, bytes_to_long
from secret import flag
import secrets

meat = bytes_to_long(secrets.token_bytes(256))
assert meat.bit_length() <= 2048
salt = bytes_to_long(secrets.token_bytes(8))
pepper = 3

def bake(meat: int, g: int, p: int):
    baked = (pow((meat ^ salt) * g**pepper, meat + g*pepper, p) + g * (meat ^ salt)**pepper) % p
    return baked

print("Let's cook together!")
print("Give me a prime to cook.")
p = int(input("p = "))
if not (128 < p.bit_length() <= 2048):
    print("p should be 2^128 <= p < 2^2048.")
    exit()
if not isPrime(p):
    print("p should be prime!")
    exit()
print("This is meat:", pow(meat, pepper, p))
for _ in range(16):
    g = int(input("g = "))
    g %= p
    if not (128 < g.bit_length()):
        print("g should be 2^128 <= g.")
        continue
    print("Here you are. Enjoy!", bake(meat, g, p))
print("You must be full.")
challenge = int(input("Thank you. By the way, where do you think this meat comes from?"))
if meat == challenge:
    print("Nice!", flag)

これは meat $m$, salt $s$, pepper $p$, 剰余 $n$ として次のように定式化できます。

素数 $n$ を与えて $p = 3$, $s\approx 2^{64}$, $m\approx 2^{2048}$ に対し $m^3 \pmod{n}$ と $g$ をいくつか与えて署名値を得ることができる。

$$
((m \oplus s)g^p)^{m + gp} + g(m \oplus s)^p \pmod{n}
$$

このとき $m$ を求める問題である。

これはとりあえず $m^p \pmod{n}$ を解いておしまい。すみません...完全に失念してて非想定でした。

今は $m^p \pmod{n}$ 得ることができないものとして話を進めます。ビット数に大きな差が開いているので LLL が出来そうな予感がします。

まず次の値が与えられることを考えます。離散対数問題が含まれるので平文 $m$ に関する情報は得ることが出来ません。

$$
((m \oplus s)g^p)^{m + gp} + g(m \oplus s)^p \pmod{n}
$$

こういうインタラクティブな問題は代数的関係を持つものを与えて解くのが典型です。今回は自由な $g$ を与えることができるのでとりあえず最も簡単な $g, g+1$ を与えてみます。これを $r_0, r_1$ としておくと次のような式が得られます。

$$
\begin{aligned}
r_0 & = ((m \oplus s)g^p)^{m + gp} + g(m \oplus s)^p & \pmod{n} \\
r_1 & = ((m \oplus s)(g+1)^p)^{m + (g+1)p} + (g+1)(m \oplus s)^p & \pmod{n}
\end{aligned}
$$

そうしたときの $r_0, r_1$ の関係はあまり自明なものになってはいません。最も複雑なところは $g^p$ と $(g+1)^p$ のところではないでしょうか。これが解消できれば良さそうです。

ここで $g$ に 1 つの自由度があるのでそれを適用して解消することを考えます。つまり $g^p = (g+1)^p\pmod{n}$ となるような $g$ は $p - 1$ 個存在して、これらの $g$, $g + 1$ を与えます。そうすると次のようになります。

$$
\begin{aligned}
r_0 & = ((m \oplus s)g^p)^{m + gp} + g(m \oplus s)^p & \pmod{n} \\
r_1 & = ((m \oplus s)g^p)^{m + (g+1)p} + (g+1)(m \oplus s)^p & \pmod{n}
\end{aligned}
$$

大分見た目が簡単になりました。大量の積を取っている部分について

$$
\begin{aligned}
(r_0 - (g(m \oplus s)^p))((m \oplus s)g^p)^p = (r_1 - ((g+1)(m \oplus s)^p)) & \pmod{n}
\end{aligned}
$$

これより $m \oplus s$ の $2p$ 次方程式となります。$(g, g+1)$ のペアについて $p - 1 = 2$ 個適用すると同様の異なる方程式が求まります。これより最大公約元を取ることで $(m \oplus s)^p$ が求まります。

これ以上は分解できないのでこれを得たことを確認して、目隠しを外し $m^p\pmod n$ を得ることが出来たとします。そうすると次のような関係式が得られます。

$$
\begin{aligned}
(m\oplus s)^p & = c_1 & \pmod{n} \\
m^p \qquad & = c_2 & \pmod{n}
\end{aligned}
$$

これより Coppersmith's Short Pad Attack を用いて $m$ が求まります。
つまり次のような式 $f_1, f_2$ を用意して $x$ について共通の解を持つとき $x$ に関する終結式 $\mathrm{Res}(f_1, f_2)$ は $\mathrm{Res}(f_1, f_2) = 0$ となります。さらに $\mathrm{Res}(f_1, f_2)$ は $y$ の多項式であるので Coppersmith Method を用いて $y$ について解くことが出来ます。

$$
\begin{aligned}
f_1 & = (x + y)^p - c_1 & \pmod{n} \\
f_2 & = x^p - c_2 & \pmod{n}
\end{aligned}
$$

よって $f_1, f_2$ の最大公約元を取ることで $x = m$ が求まります。

from Crypto.Util.number import *
from pwn import *
import sys

if len(sys.argv) == 3:
    io = remote(sys.argv[1], int(sys.argv[2]))

p = 2^2048 - 2^32
while True:
    p = next_prime(p)
    PR.<x> = PolynomialRing(GF(p))
    f = (x + 1)^3 - x^3
    gs = f.roots()
    gs = list(map(lambda x: x[0], gs))
    if len(gs) != 2:
        continue
    break
print("p", p)

io.sendline(str(p).encode())
io.recvuntil(b'This is meat: ')
m3 = int(io.recvline())
print(m3)

print(gs[0])
rs = []
for i in range(2):
    io.sendline(str(gs[i]).encode())
    io.recvuntil(b'Enjoy!')
    g0 = int(io.recvline())
    io.sendline(str(gs[i] + 1).encode())
    io.recvuntil(b'Enjoy!')
    g1 = int(io.recvline())
    rs.append((g0, g1))
print(rs)

PR.<x> = PolynomialRing(GF(p))
f1 = (rs[0][1] - (gs[0]+1)*x^3) - (rs[0][0] - gs[0]*x^3)*(x*gs[0]^3)^3
f2 = (rs[1][1] - (gs[1]+1)*x^3) - (rs[1][0] - gs[1]*x^3)*(x*gs[1]^3)^3
f1 = f1.monic()
f2 = f2.monic()
f = gcd(f1, f2)
c = - f[0]
print(f)

def franklinReiter(n, e, r, c1, c2):
    R.<x> = PolynomialRing(Zmod(n))
    f1 = x^e - c1
    f2 = (x + r)^e - c2
    return - polygcd(f1, f2).coefficients()[0]

def polygcd(a, b):
    if(b == 0):
        return a.monic()
    else:
        return polygcd(b, a % b)

def CoppersmithShortPadAttack(e, n, C1, C2, eps=1/30):
    P.<x,y> = PolynomialRing(ZZ)
    g1 = x^e - C1
    g2 = (x + y)^e - C2
    print(g1)
    res = g1.resultant(g2)

    Py.<y> = PolynomialRing(Zmod(n))
    res = res.univariate_polynomial()
    res = res.change_ring(Py).subs(y=y)
    res = res.monic()
    kbits = n.nbits()//(2*e*e)
    print(kbits)
    diff = res.small_roots(X=2^kbits, epsilon=eps)
    print(diff)

    return franklinReiter(n, e, diff[0], C1, C2)

m = CoppersmithShortPadAttack(3, p, m3, lift(c))
print(m)

反省

やってしまいました...確かに普通に解けますね...無限謝罪編です...

この問題に対しては上位ビットについて一致したらフラグ渡すという形式や剰余を与えないものとして素因数分解が困難な DLP にすれば問題として成立したと思います。

ただ多くの参加者、かなり優秀な作問者とインフラの方々に迷惑を掛けて申し訳ありません。

今後起きないように作問と同等にレビューに時間を当てるようなスケジュールを組みたいと思います。