2022-06-20

ある種のEdDSAの実装に対するDouble-PubKey Oracle Attack

話題はこれ↓

www.reddit.com

詳しい話はこれ↓

blog.safeheron.com

興味があるところだけ書くと、EdDSAの署名は秘密鍵 $x$ 、公開鍵 $A = xG$ として、平文 $m$ を受け取って次のように計算した $(R, S)$ の組*1。詳しくはwikipediaとかを見てください。

$r = h(h_{\{b \dots 2b-1\}}(k) || m), R = rG$
$e = h(R || A || m)$
$S \equiv r + ex \mod q$

ここで署名のロジックが入力として $(k, m, A)$ を受け取っているとき、 $(R, S) = sign(k, m, A), (R, S') = sign(k, m, A')$ のように不正な公開鍵 $A'$ を渡して、これが計算されてしまうとECDSAにおけるnonce reuse attackのような感じで $x$ が計算できる。

具体的には $S \equiv r + ex \mod q, S' \equiv r + e'x \mod q$ で、 $r, x$ が未知なので2式で引き算をして $r$ を消すと $S - S' \equiv (e - e')x \mod q$ になって、 $x = \frac{S - S'}{e - e'} \mod q$ とやって $x$ が得られる。

上述のポストなどでは署名するロジックは $A$ は受け取らずに自前で計算するか、受け取ってもそれが $k$ に対応したものであることを確かめましょうといってる（まあこれは計算して一致するか見ることになる）。

個人的には引数に誤った値を渡したらロジックが思わぬ挙動になって結果的に困るみたいなのはそうですねと思うんだけど、特にredditの記事では割と深刻っぽい雰囲気で書いてある。誤用しうる状態すらも許せないってことなんだろうか。実際これが攻撃やバグにつながるかと言われると、それこそCTFでくらいしかそういうシチュエーションにならないような気がするし、これで問題を作れって言われても自然な形にするのにはだいぶ苦心することになるだろうな、と思う。暗号界隈的にはどういう受け止め方をされているんだろう。気になる。

redditのスレちゃんと読んでなかったけどCTFでは既出らしいです ctf/2018-12-08-hxp/crypto_uff at master · p4-team/ctf · GitHub

*1:ここで $R$ は曲線状の点だけど $S$ は整数なので注意。あと $k$ は $x = h_{0 \dots b-1}(k)$ であるシード

2022-06-05

SECCON Beginners 2022 - Omni RSA writeup

writeup くらい書いておかないとなにもしていないような悲しい気持ちになるのでwriteupです

問題はこう

from Crypto.Util.number import *
from flag import flag

p, q, r = getPrime(512), getPrime(256), getPrime(256)
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
e = 2003
d = inverse(e, phi)

flag = bytes_to_long(flag.encode())
cipher = pow(flag, e, n)

s = d % ((q - 1)*(r - 1)) & (2**470 - 1)

assert q < r
print("rq =", r % q)

print("e =", e)
print("n =", n)
print("s =", s)
print("cipher =", cipher)

こういう問題をみたら、 $ed \equiv 1 \mod \phi$ をたてて、 $\phi$ を開いて $N, p, q, r$ で表したうえで $ed = 1 + k(N + \dots + 1)$ という形に剰余を開きたくなりますね。そのあと $N$ か $e$ で剰余を取り直す。

しかし今回の場合与えられている $s$ は $u \equiv d \mod (q-1)(r-1)$ の下位470bitなので愚直にそういうアプローチは取れずちょっと工夫が必要になりそうです。とにかく書いてみると、 $u = s + x*2^{470}$ として

$e(s + x*2^{470}) \equiv 1 \mod (q-1)(r-1)$

です。適当な整数 $k$ を持ち出してきて剰余を開き、ついでに $t = r \% q = r - q$ も与えられているので、 $r = q + t$ とおきなおすとこうです。

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

一見これで $\mod q$ を取り直して $\beta = 0.25$ くらいでcoppersmith methodをすると $x$ が十分小さいので解けるように見えます。実際解けるっぽくて作問者writeupではそうなっていたんですが、私はパラメータの調整を雑にやった結果これでは解けないという誤った確信に至ったので別の方法をとりました。

ここで $\mod 2^{470}$ をとると下式のようになり、未知数は $k, q$ ですが、 $e \lt k$ で $e = 2003$ なので全探索すれば良さそうなので未知数は実質 $q$ だけです。

$es \equiv 1 + k(q-1)(q+t-1) \mod 2^{470}$

これをいきなり解くのは難しいので*1、更に簡単にして $\mod 2^m$ を考えます。

$es \equiv 1 + k(q-1)(q+t-1) \mod 2^m$

すると十分小さい $m$ の元では $q$ の下位bitの候補が全探索できます。まず $m=1$ で $q$ の最下位bitの候補を2通り探索し、続いて $m=2$ として下から2bit目の候補を探索します。候補数が $2^m$ 個に増えそうですが、 $q$ の下位bitと一致している場合は必ず等式が成り立つことを考えると、どこかのタイミングで上位bitの候補がなくなった場合は下位bitの選択がまちがっていたということなので捨ててよく、候補数はそんなに増えないことが期待できます*2。

というように $m$ を $1$ から $470$ 枝刈り全探索をやって残っていた候補はわずかなはずなので、そのなかで $n$ を割り切れるやつが $q$ です。というわけで $q$ が求められたので、 $r = q + t$ から $r$ を、 $n = pqr$ から $p$ を求めて素因数分解が完了したのでRSAは解けました。

エクスプロイトはこう！ 2冪で小さい方から枝刈り全探索というとTSG CTF 2019のOPQRXを思い出しますねとおもったけどこれは大きい方からだったか……

from Crypto.Util.number import inverse

t = 7062868051777431792068714233088346458853439302461253671126410604645566438638
e = 2003
n = 140735937315721299582012271948983606040515856203095488910447576031270423278798287969947290908107499639255710908946669335985101959587493331281108201956459032271521083896344745259700651329459617119839995200673938478129274453144336015573208490094867570399501781784015670585043084941769317893797657324242253119873
s = 1227151974351032983332456714998776453509045403806082930374928568863822330849014696701894272422348965090027592677317646472514367175350102138331
cipher = 82412668756220041769979914934789463246015810009718254908303314153112258034728623481105815482207815918342082933427247924956647810307951148199551543392938344763435508464036683592604350121356524208096280681304955556292679275244357522750630140768411103240567076573094418811001539712472534616918635076601402584666

qs = []

def dfs(sz, qbits, k):
    if sz == 470:
        qs.append(qbits)
        return

    if sz > 256 and qbits.bit_length() > 256:
        return

    q1 = qbits
    q2 = qbits | (1 << sz)

    a = e*s % 2**(sz+1) == (1 + k*(q1-1)*(q1+t-1)) % 2**(sz+1)
    b = e*s % 2**(sz+1) == (1 + k*(q2-1)*(q2+t-1)) % 2**(sz+1)
    if a:
        dfs(sz + 1, q1, k)
    if b:
        dfs(sz + 1, q2, k)

for k in range(1, e):
    dfs(0, 0, k)

for q in qs:
    if n % q != 0:
        continue
    r = q + t
    p = n // (q*r)
    phi = (p - 1) * (q - 1) * (r - 1)
    e = 2003
    d = inverse(e, phi)

    m = pow(cipher, d, n)
    print(bytes.fromhex(hex(m)[2:]))

*1:SageはHensel's liftを使ってこういうのを解く方法も提供しているらしくそれでも解けそうでした https://twitter.com/nuo_chocorusk/status/1533324083135324160

*2:具体的にどのくらいに抑えられるのかは知りません。なんかやったらうまくいったので……

2022-05-14

TSG Live!8 CTF writeup - Two Keys

今年もまた世界で一番楽しいCTF、人生でもっとも頭を高速に回転させる必要のある100分間、TSGの作問力に舌を巻く儀式であるところのTSG Live! CTFが盛大に開催されました。今回は全然解けなくて非常に悔しい思いをしたので精進します。それはそれとしてCryptoのwriteupを一つくらい書いておくか、ということでTwo Keysという問題のwriteupです。

問題概要

要するに $N_1 = pq, N_2 = (p + s)*(q + t)$ の2つのRSAです

from Crypto.Util.number import *
from flag import flag

def nextPrime(n):
    while True:
        n += 1
        if isPrime(n):
            return n

class RSA:
    def __init__(self, p, q):
        assert isPrime(p) and isPrime(q)
        self.p = p
        self.q = q
        self.e = 65537
        self.d = pow(self.e, -1, (self.p-1) * (self.q-1))
    def encrypt(self, x):
        return pow(x, self.e, self.p * self.q)
    def decrypt(self, y):
        return pow(y, self.d, self.p * self.q)
    def printPublicKey(self):
        print(f"N = {self.p * self.q}")
        print(f"e = {self.e}")

p = getPrime(512)
q = getPrime(512)
pp = nextPrime(p)
qq = nextPrime(q)
rsa1 = RSA(p, q)
rsa2 = RSA(pp, qq)

x1 = int.from_bytes(str.encode(flag[:len(flag)//2]), "big")
x2 = int.from_bytes(str.encode(flag[len(flag)//2:]), "big")
y1 = rsa1.encrypt(x1)
y2 = rsa2.encrypt(x2)

assert x1 == rsa1.decrypt(y1)
assert x2 == rsa2.decrypt(y2)

print("First half:")
rsa1.printPublicKey()
print(f"y = {y1}")
print()
print("Second half:")
rsa2.printPublicKey()
print(f"y = {y2}")

解法

とりあえず $s, t$ は小さいことを期待して全探索することにして、 $N_1, N_2$ から $p, q$ に関する式を建てます。 $N_2$ を開いて

$N_2 = (p + s)(q +t) = pq + pt + qs + st = N_1 + pt + qs + st$ です。さらに $q = \frac{N_1}{p}$ なので

$N_2 = N_1 + pt + \frac{N_1}{p}s + st$ 。両辺に $p$ をかけて整理すると $-tp^2 + (N_2 - N_1 - st)p - sN_1 = 0$ という二次方程式になります。

正しい $s, t$ が求められていればこの式の解 $p$ が整数になるはずであることを利用して探索中の $s, t$ が求めている値かどうかをチェックし、最終的に整数 $p$ が得られれば勝ちです

exploit

時間が少ないCTFだと雑なコードを書いてしまい、結果的にタイムをロスします。丁寧にassertとか入れて仮説とその実装の正しさを保ちながらきれいに書きましょう（反省）

from gmpy2 import iroot
from tqdm import tqdm

N1 = 568...
e = 65537
c1 = 541...

N2 = 568...
e = 65537
c2 = 549...

for s in tqdm(range(10,10000)):
    for t in range(10,10000):
        a = -t
        b = N2 - N1 - s*t
        c = -s*N1

        if b**2 - 4*a*c <= 0:
            continue

        D, ok = iroot(b**2 - 4*a*c,2 )
        if not ok:
            continue
        if (-b + D) % (2*a) == 0:
            p = (-b + D) // (2*a)
            print(p)
            q = N1 // p

            pp = (p + s)
            qq = N2 // pp
            assert pp*qq == N2

            d1 = pow(e, -1, (p-1)*(q-1))
            m1 = pow(c1, d1, N1)

            d2 = pow(e, -1, (pp-1)*(qq-1))
            m2 = pow(c2, d2, N2)

            print(bytes.fromhex(hex(m1)[2:]) + bytes.fromhex(hex(m2)[2:]))

        if (-b - D) % (2*a) == 0:
            p = (-b - D) // (2*a)
            print(p)
            q = N1 // p

            pp = (p + s)
            qq = N2 // pp
            assert pp*qq == N2

            d1 = pow(e, -1, (p-1)*(q-1))
            m1 = pow(c1, d1, N1)

            d2 = pow(e, -1, (pp-1)*(qq-1))
            m2 = pow(c2, d2, N2)

            print(bytes.fromhex(hex(m1)[2:]) + bytes.fromhex(hex(m2)[2:]))

感想

この問題も他の問題も楽しかったです

ふるつき

v('=')v かに

ある種のEdDSAの実装に対するDouble-PubKey Oracle Attack

SECCON Beginners 2022 - Omni RSA writeup

TSG Live!8 CTF writeup - Two Keys

問題概要

解法

exploit

感想