元競プロerによる初めてのCTF writeup - チョコラスクのブログ

この記事はCTF Advent Calendar 2022の23日目の記事です。昨日はXornetさんのペアリングでCTFの問題を解くでした。昔、暗号の文脈以外でWeil pairingを勉強した記憶はあります*1が忘れました。後ほどゆっくり読みたいと思います。

初めまして、チョコラスクです。今年からCTFを始めました。初めて真面目に参加したCTFはzer0pts CTF 2022です。

以前は競技プログラミングをやっていました*2。また、大学で少し数学を勉強していました。

ちゃんとしたwriteupを公開するのは初めて*3で怖いですが、これまでに解いた問題のうち、競プロ知識や数学知識を使っていい感じに解けた問題のwriteupを書いてみます。

CakeCTF 2022 Rock Door
SECCON Beginners CTF 2022 omni-RSA

CakeCTF 2022 Rock Door

問題のソースコードはこちらです。

DSAが実装されており、一度だけ (gomaを含まない) 好きな文字列の署名 $(r, s)$ を計算させることができます。ただし、計算結果は $s$ の方しか得られません。その後、hirake goma の正当な署名を入力できればフラグが得られます。

ソースコード内の各変数がどれぐらいの大きさかを確認してみます。 $q, s$ は 1024 bit程度であるのに対し、 $x, z, k, r$ はSHA256ハッシュを取った結果なので 256 bit程度です。好きな文字列について $s$ を取得すると、 $ks\equiv z+xr\pmod q$ という関係式が成り立ちます。 $z+xr$ は 512 bit程度で、これは $q$ に比べて小さく、 $k$ を適当に選んだとき $ks\bmod q$ が 512 bit程度になる確率は $1/2^{512}$ 程度です。よって、 $k$ が 256 bit程度で $ks\bmod q$ が 512 bit程度という条件だけで $k$ が一意に定まりそうです。

$z$ は入力する文字列から計算できるので、 $k$ がわかれば $xr$ がわかり、さらに $r$ は $k$ から求まるので、 $x$ もわかります。秘密鍵 $x$ がわかれば署名の計算ができるので、解けます。

想定解ではLLLを用いて $k$ を計算していますが、floor sum という (競プロ界では有名な) アルゴリズムを用いることもできるので、それを解説します。

floor sum は、正整数 $n, m$ と整数 $a, b$ に対し、

$\displaystyle{ f(n, m, a, b)=\sum_{i=0}^{n-1} \left\lfloor\frac{ai+b}{m}\right\rfloor }$

を高速に*4計算するアルゴリズムです。

まず、 $0\leq a, b\lt m$ と仮定してよいです。実際、 $a=q_am+r_a$ $(0\leq r_a\lt m)$ とおくと、

$\displaystyle{ f(n, m, a, b)=f(n, m, r_a, b)+q_a\sum_{i=0}^{n-1}i }$

なので、 $0\leq a\lt m$ の場合に帰着できます。 $b$ についても同様です。

$an+b=qm+r$ $(0\leq r\lt m)$ とおきます。 $q\lt y\lt \frac{an+b}{m}$ の範囲に格子点はないことに注意すると、 $f(n,m,a,b)$ は図の青い領域内に含まれる格子点の個数に等しいです。直線 $x=n$ を $x$ 軸、 $y=q$ を $y$ 軸と視点を変えてみることで、

$\displaystyle{ f(n,m,a,b)=\sum_{i=0}^{q-1} \left\lfloor\frac{mi+r}{a}\right\rfloor=f(q,a,m,r) }$

がわかります。

よって、 $(n,m,a,b)$ から $(q,a,m,r)$ の場合に帰着でき、さらに $(q,a,m\bmod a,r\bmod a)$ の場合に帰着できるので、 $(m,a)$ にユークリッドの互除法を適用するのと同じ要領で $a=0$ の場合に帰着でき、 $f(n, m, a, b)$ が求まります。

さて、これを今回の問題にどう適用するかですが、

$\displaystyle{ \left\lfloor\frac{sk}{q}\right\rfloor - \left\lfloor\frac{sk-2^{512}}{q}\right\rfloor= \begin{cases} 1 & ((sk\bmod q) \lt 2^{512}) \\ 0 & ((sk\bmod q) \geq 2^{512}) \end{cases} }$

であることに着目します。すると、 $0\leq k\lt n$ の範囲で $(sk\bmod q) \lt 2^{512}$ を満たす $k$ の個数は

$\displaystyle{ f(n,q,s,0)-f(n,q,s,-2^{512}) }$

と表せます。 $0\leq k\lt 2^{256}$ の範囲で初めて $f(k,q,s,0)-f(k,q,s,-2^{512})>0$ となる $k$ を二分探索することで、 $(sk\bmod q) \lt 2^{512}$ を満たす $k$ を見つけることができます。

# sum[i=0 to n-1] floor((a*i+b)/m)
def floor_sum(n, m, a, b):
    if n == 0:
        return 0
    ret = 0
    if a >= m:
        ret += n*(n-1)//2*(a//m)
        a %= m
    if b >= m:
        ret += n*(b//m)
        b %= m
    if a == 0:
        return ret
    q, r = (a*n+b)//m, (a*n+b)%m
    ret += floor_sum(q, a, m, r)
    return ret

from hashlib import sha256
from Crypto.Util.number import getRandomRange, inverse, long_to_bytes

def h(s: bytes) -> int:
    return int(sha256(s).hexdigest(), 16)

q = 139595134938137125662213161156181357366667733392586047467709957620975239424132898952897224429799258317678109670496340581564934129688935033567814222358970953132902736791312678038626149091324686081666262178316573026988062772862825383991902447196467669508878604109723523126621328465807542441829202048500549865003
p = 2*q + 1
g = 2
y = 37925794679172810656660325405743980058149298941234310232364510309420515092602600523697777529812917758313422672128981188920487521638575170382644658820074833119309713550634143577305912149763628209572141367725296502112007404954248895722761291522996966773323841581645549327400582154539861787835821155142888287483

m1 = b"myon"
z1 = h(m1)
# "myon" に対する s の値
s1 = 34112470810592176118801977602000637660265529835590820260074241304093463468236031746057456541876447210174543389860988306468965410818788719940381401389545593766521657980898975708370037147335849545814914529044948910315266154298872698766582160589313927112886437376450668673875319127868804480390170246274373661339

assert floor_sum(2**256, q, s1, 0)-floor_sum(2**256, q, s1, -2**512) == 1

left = 0
right = 2**256
while right-left > 1:
    mid = (left+right)//2
    if floor_sum(mid, q, s1, 0)-floor_sum(mid, q, s1, -2**512) > 0:
        right = mid
    else:
        left = mid

k1 = left
r1 = h(long_to_bytes(pow(g, k1, p)))
xr1 = (k1*s1-z1)%q
assert xr1%r1 == 0
x = xr1//r1
assert pow(g, x, p) == y

m = b"hirake goma"
z = h(m)

k = getRandomRange(0, q)
r = h(long_to_bytes(pow(g, k, p)))
assert r < q
s = (z + x*r) * inverse(k, q) % q
sinv = inverse(s, q)
gk = pow(g, sinv*z, p) * pow(y, sinv*r, p) % p
r2 = h(long_to_bytes(gk))
assert r == r2
print(f'r = {r}')
print(f's = {s}')

SECCON Beginners CTF 2022 omni-RSA

問題のソースコードはこちらです。

RSA暗号っぽいものが実装されています。 $3$ つの素数 $p, q, r$ を用いており、 $t=(r\bmod q)$ および、秘密鍵 $d$ について $d'=(d\bmod (q-1)(r-1))$ の下 470 bit ( $s$ とする) が与えられます。簡単にわかることとして、 $q, r$ はともに 256 bitで $q\lt r$ なので、 $t=r-q$ です。

42 bit程度の整数 $x$ を用いて $d'=2^{470}x+s$ と書けます。 $ed'\equiv 1\pmod{(q-1)(r-1)}$ なので、正整数 $k$ を用いて

$\displaystyle{ e(2^{470}x+s)=k(q-1)(q-1+t)+1 }$

と書けます。ここで $d'\lt (q-1)(r-1)$ なので $k\lt e$ です。 $k$ は全探索ができそうです。

想定解では $\bmod{q}$ を取ってCoppersmith法で $x$ を求めています*5が、ここでは $\bmod 2^{470}$ を取ってみます。すると $es\equiv k(q-1)(q-1+t)+1 \pmod{2^{470}}$ です。 $k$ を全探索することにすると、未知数は $q$ のみです。 $4k$ 倍して平方完成すると

$\displaystyle{ (k(2q+t-2))^2\equiv k^{2}t^{2}+4kes-4k\pmod{2^{470}} }$

となります。 $k(2q+t-2)$ は 270 bit未満で小さいです。

あとは $x^{2}\equiv a\pmod{2^{470}}$ という方程式が解ければ $q$ がわかり、 $q$ がわかれば $r=q+t$ より $r$ がわかり、 $n=pqr$ より $p$ もわかるので、復号できます。

Henselの補題を思い出すと、これは解けそうです：

$p$ を素数、 $f(x)$ を整数係数多項式、 $k$ を正整数とし、 $f(r)\equiv 0\pmod{p^{k}}$ および $f'(r)\not\equiv 0\pmod{p}$ が成り立っているとする。このとき、 $f(r')\equiv 0\pmod{p^{k+1}}$ , $r'\equiv r\pmod{p^{k}}$ を満たす $r'$ が $\bmod{p^{k+1}}$ で唯一つ存在する。

今回はHenselの補題における微分が0でないという条件が満たされないので、そのままは成り立ちませんが、似たようなことは成り立ちます：

$a$ を奇数、 $k\geq 3$ とし、 $x^{2}\equiv a \pmod{2^{k}}$ が成り立っているとする。このとき、 $x'^{2}\equiv a \pmod{2^{k+1}}$ , $x'\equiv x \pmod{2^{k-1}}$ を満たす $x'$ が $\bmod{2^{k}}$ で唯一つ存在する。

これは、 $x'=x$ と $x'=x+2^{k-1}$ のうちちょうど一方が次の解になることが簡単にわかるので示せます。よって、 $\bmod{2^{3}}$ での解、 $\bmod{2^{4}}$ での解、 $\bmod{2^{5}}$ での解・・・を順番に計算していけば解けます。

これをそのまま実装してもよいですが、SageMathには $p$ 進数を扱う関数が色々用意されているので、それを使うとシンプルに実装できます*6。問題は、 $a\in\mathbb{Q} _ {2}$ が適当な精度で与えられているときに、 $2$ 進数体 $\mathbb{Q} _ {2}$ 上で $x^{2}=a$ を解く問題と考えられ、これはSageMathのsquare_root関数で実現できます。

公式ドキュメントに記載されているように、 $p=2$ の場合精度が1だけ落ちますが、これは、 $a$ が奇数のとき $x^{2}\equiv a \pmod{2^{k}}$ の解は $\bmod{2^{k-1}}$ で (存在すれば) 2個であることから理解できます。

細かい注意として、SageMathの $p$ 進整数環のクラスには絶対精度と相対精度の2種類があります*7。

sage: a = Zp(2, prec = 10)(272)                                                                                                                                  
sage: a                                                                                                                                                          
2^4 + 2^8 + O(2^14)
sage: a.square_root(all=True)                                                                                                                                    
[2^2 + 2^5 + 2^7 + 2^8 + 2^9 + O(2^11), 2^2 + 2^3 + 2^4 + 2^6 + 2^10 + O(2^11)]
sage: a = Zp(2, prec = 10, type = 'capped-abs')(272)                                                                                                             
sage: a                                                                                                                                                          
2^4 + 2^8 + O(2^10)
sage: a.square_root(all=True)                                                                                                                                    
[2^2 + 2^5 + O(2^7), 2^2 + 2^3 + 2^4 + 2^6 + O(2^7)]

今回は常に $\bmod{2^{470}}$ で解きたいので、絶対精度の方を指定するとよいです。

from Crypto.Util.number import *
from output import *

R = Zp(2, prec = 470, type = 'capped-abs')

for k in range(1, e):
    a = k*k*rq*rq + 4*k*e*s - 4*k
    try:
        xs = R(a).square_root(all=True)
    except Exception:
        continue
    x = min([v.lift() for v in xs])
    if int(x).bit_length() > 270:
        continue
    q = (x//k-rq)//2+1
    r = q+rq
    p = n//(q*r)
    d = inverse(e, (p-1)*(q-1)*(r-1))
    print(long_to_bytes(int(pow(cipher, d, n))))