Midnight Sun CTF Quals 2022 - BabyZK

TL;DR

• $x_i$を与えると$g^{m(x_i)} \mod p$をくれるクエリに17回問い合わせられる
• そこから任意の$x$に対して$g^{m(x)} \mod p$を100回正確に求めるチャレンジがある
• 線形代数と基底簡約を利用して$p$の倍数を複数用意し、そこから最大公約数を求めて$p$を導出する
• 任意の$x$に対して、$m(x)$が既知の$m(x_i)$の線形結合で表現出来るので、$\prod g^{s_im(x_i)} \mod p$を求めてチャレンジに提出する

Prerequisite

• 線形代数
• 基底簡約

Writeup

次のようなスクリプトが動いている

#!/usr/bin/python3

from sys import stdin, stdout, exit
from secrets import randbelow
from gmpy2 import next_prime

from flag import FLAG


class BabyZK:

    def __init__(self, degree, nbits):
        self.p = self.__safeprime(nbits)
        self.degree = degree
        self.m = [randbelow(self.p-1) for i in range(self.degree)]
        self.g = 2 + randbelow(self.p-3)
        self.ctr = 0

    def __safeprime(self, nbits):
        stdout.write("Generating safeprime...")
        p = -1
        while True:
            q = next_prime(randbelow(2 * 2**nbits))
            p = 2*q + 1
            if p.is_prime():
                break
        return p

    def __eval(self, x: int) -> int:
        y = 0
        for a in self.m:
            y += y * x + a
        return y % (self.p-1)

    def prover(self, x: int) -> int:
        if self.ctr > self.degree + 1:
            raise Exception("Sorry, you are out of queries...")
        self.ctr += 1
        return int(pow(self.g, self.__eval(x), self.p))

    def verify(self, x: int, u: int):
        if not u < self.p or u < 0:
            raise Exception("Oof, this is not mod p...")
        if int(pow(self.g, self.__eval(x), self.p)) != u:
            raise Exception("No can do...")


bzk = BabyZK(15, 1024)

def prove():
    stdout.write("> ")
    stdout.flush()
    challenge = int(stdin.readline())
    stdout.write("%d\n" % bzk.prover(challenge))
    stdout.flush()

def verify():
    for i in range(100):
        challenge = randbelow(bzk.p)
        stdout.write("%d\n" % challenge)
        stdout.flush()
        response = int(stdin.readline())
        bzk.verify(challenge, response)
    stdout.write("%s\n" % FLAG)
    stdout.flush()

banner = lambda: stdout.write("""
1) Query the prover oracle.
2) Prove to verifier that you know the secret.
3) Exit.
""")

choices = {
    1: prove,
    2: verify,
    3: exit
}

banner()
stdout.flush()

while True:
    try:
        choice = stdin.readline()
        choices.get(int(choice))()
    except Exception as e:
        stdout.write("%s\n" % e)
        stdout.flush()
        exit()

安全素数$p$と$p$未満の整数$g$に対して$\mathbb F_p$上の14次多項式$m(x)$が定義されており、どれも未知である。これに対して次の2つのコマンドを実行出来る。

1. 17回まで$x_i$を指定して$g^{m(x_i)} \mod p$を得る
2. $x_i$が指定され、$g^{m(x_i)} \mod p$を提出するチャレンジを100回行い、全部成功するとフラグが得られる。1回でも失敗すると終了する

$p$が安全素数であることから、指数を直接求めることは難しく、このことから多項式$m$を求めることが難しい。そもそも$g$すら分かっていないし求める方法も思い浮かばない。そこで、$m,g$を求めるのは諦めて$p$を求めた上で2のチャレンジに成功する事を考える。

$m(x) = \sum_{i=0}^{14} m_i x^i$とおく。すると、1のクエリで指定した$x_i$に対して$m(x_i)$は次のような行列積で表される。17回クエリを発行出来るので$1 \leq i\leq 17$とする。

$$\begin{pmatrix} 1 & x_1 & x_1^2 & \dots & x_1^{14} \cr 1 & x_2 & x_2^2 & \dots & x_2^{14} \cr &&&\vdots \cr 1 & x_{17} & x_{17}^2 & \dots & x_{17}^{14} \cr \end{pmatrix} \begin{pmatrix} m_0 \cr m_1 \cr \vdots \cr m_{14} \end{pmatrix} = \begin{pmatrix} m(x_1)\cr m(x_2)\cr \vdots\cr m(x_{17}) \end{pmatrix}$$

わかりやすさの為に左辺の17x15行列を$B$、($m_0, m_1, \dots, m_{14})^T$を$\boldsymbol m$、右辺を$\boldsymbol a$とおいて、$B\boldsymbol m = \boldsymbol a$とする。ここである整数$x$に対して$\boldsymbol x = (1, x, x^2,\dots,x^{14})$を考えると、$B$の次元が15次元なので$\boldsymbol sB = \boldsymbol x$となる$\boldsymbol s = (s_1, s_2, \dots, s_{17})$が存在する。

よって、上の式に両辺から$\boldsymbol s$を左から掛けると次が成り立つ。

$$m(x) = \boldsymbol x \boldsymbol m = \boldsymbol s \boldsymbol a = \sum_{1 \leq i \leq 17} s_im(x_i)$$

$g$の指数にこれらを用いて次が成り立つ。

$$g^{m(x)} \equiv \prod_{1 \leq i \leq 17} \left(g^{m(x_i)}\right)^{s_i} \mod p$$

17回のクエリによって、$g^{m(x_i)}$は$1 \leq i\leq 17$の範囲なら既知であり、簡単な行列の計算によって$\boldsymbol s$も既知である。したがって後は$p$を求める事さえできれば、2のチャレンジは突破出来る。

肝心の$p$を求める方法だが、$p$を法として合同な2つの数を用意するとその差が$p$の倍数となるから、それを複数集めてGCDを求めれば$p$(と比較的小さい数の積)が手に入ることが期待出来る。

手元にあるのは$g^{m(x_i)} \mod p$が17個だけであるから、$\prod g^{r_im(x_i)} \equiv \prod g^{s_im(x_i)} \mod p$となるような、$(r_1, \dots, r_{17}), (s_1, \dots, s_{17})$を求めたい。これは結局指数法則によって次のような$(r_1, \dots, r_{17}), (s_1, \dots, s_{17})$を求めることになる。$\bmod p-1$による合同ではなく、イコールなのは$p$が判明していないからである。

$$\begin{aligned} \sum_{1 \leq i \leq 17} r_im(x_i) = \sum_{1 \leq i \leq 17} s_im(x_i) \Leftrightarrow \sum_{1 \leq i \leq 17} (r_i - s_i)m(x_i) = 0 \end{aligned}$$

$t_i \coloneqq r_i - s_i$とおいて、$\boldsymbol t =(t_1, t_2, \dots, t_{17})$とすれば、上の$B\boldsymbol m = \boldsymbol a$の式より、$\boldsymbol tB = 0$となる$\boldsymbol t$を求めれば良く、これは$B$の核を求めることに同じである。この$\boldsymbol t$に対して$\boldsymbol t\boldsymbol a = 0$となるので、$\prod g^{t_im(x_i)} \equiv 1 \mod p$となって、左辺が$p$で法を取らずに計算出来れば両辺から1を引くことで$p$の倍数を求められそうである。

ただし、ここで求めた$\boldsymbol t$には$p$が判明していない事に由来する次の2つの問題がある。

1. $p$が判明していないのに、負の数が$\boldsymbol t$に含まれており、逆数が計算できない
2. $p$が判明していないため、$g^{t_im(x_i)}$が$t_i$の大きさ次第で非常に大きくなり、時間空間計算量が爆発する

1については簡単に解決出来て、負であるような$t_i$は両辺に$g^{-t_im(x_i)}$を掛けることで次のような式に変形出来る事を利用する。

$$\prod_{t_i \geq 0} g^{t_im(x_i)} \equiv \prod_{t_i \lt 0} g^{-t_im(x_i)} \mod p$$

これで左辺も右辺も計算出来るので、この差をとれば$p$の倍数が手に入る。

面倒なのは2の方でSageMathの.kernel()で求めた核は$10^5$弱の大きな値が含まれており、各$g^{m(x_i)} \mod p$が1024bit程度と考えると、$g^{t_im(x_i)}$は$p$で法をとらないため1億bitぐらいの巨大な数になってしまう。

(※ここでかなり詰まって恒例のWriteupカンニングタイムになった)

そこで登場するのが基底簡約である。$\ker B$の核(2次元)を基底とする格子を考え、これを簡約した基底もまた核となるので、簡約すると$t_i$が大きくても$10^4$未満の値に落ち着いてくれる。これで無事に計算量的に問題無い$\boldsymbol t$が求まった事になるので$\prod_{t_i \geq 0} g^{t_im(x_i)} - \prod_{t_i \lt 0} g^{-t_im(x_i)}$を2つ計算して最大公約数を取り、2や3といった小さい余分な数が含まれているからこれを除き、1つの大きな素数を得て$p$が求められる。

後は前半で述べたようにチャレンジで用いる$x$に対して$\boldsymbol sB = x$ちなるような$\boldsymbol s$を求めて、$\prod (g^{m(x_i)})^{s_i} \mod p$を計算すれば、$g^{m(x)}$が求められる。

Code

from pwn import process, remote


def choice(c):
    sc.sendline(str(c).encode())


def prove(x):
    choice(1)
    sc.recvuntil(b"> ")
    sc.sendline(str(x).encode())
    m_x = int(sc.recvline())

    return m_x


def verify(p, xs, l):
    chall = int(sc.recvline())
    rhs = [chall**i for i in range(15)]
    rhs = vector(rhs)
    exps = l.solve_left(rhs)
    ans = 1
    for x, e in zip(xs, exps):
        e %= (p-1)
        ans *= (F_p(x) ^ e)

    sc.sendline(str(int(ans)).encode())


l = [
    [x**i for i in range(15)] for x in range(17)
]

l = matrix(l)
ker_l = matrix(l.kernel().basis())
ker_l = ker_l.LLL()


print("[+] Init")
sc = process(["python3", "chall.py"])
sc.recvuntil(b"3) Exit.\n")
print("[+] Done")

g_pow_mx = []
for x in range(17):
    g_pow_mx.append(prove(x))

kps = []
for j in range(2):
    lhs = 1
    rhs = 1
    for x in range(17):
        e = ker_l[j][x]
        if e > 0:
            lhs *= (g_pow_mx[x] ^ e)
        else:
            rhs *= (g_pow_mx[x] ^ (-e))

    kps.append(lhs - rhs)

print("[+] two multiples of p are prepared")
p = gcd(kps)
factors = list(factor(p))
for _p, e in factors:
    if e == 1:
        p = _p

assert is_prime(p)
q = (p-1)//2
assert is_prime(q)
print("[+] Prime is calculated")
print(f"{p=}")
F_p = GF(p)

choice(2)

for i in range(100):
    print(i)
    verify(p, g_pow_mx, l)

sc.interactive()

Flag

ローカルでやっただけなので無し

Resources

• Midnight-Sun/BabyZK.ipynb at main · Neobeo/Midnight-Sun: 格子基底簡約を使っているWriteup