CakeCTF 2022 | Rock Door - crypto-writeup-public

#CakeCTF2022

from Crypto.Util.number import getPrime, isPrime, getRandomRange, inverse, long_to_bytes
from hashlib import sha256
import os
import secrets


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


q = 139595134938137125662213161156181357366667733392586047467709957620975239424132898952897224429799258317678109670496340581564934129688935033567814222358970953132902736791312678038626149091324686081666262178316573026988062772862825383991902447196467669508878604109723523126621328465807542441829202048500549865003
p = 2*q + 1

assert isPrime(p)
assert isPrime(q)

g = 2
flag = os.getenv("FLAG", "FakeCTF{hahaha_shshsh_hashman}")
x = h(secrets.token_bytes(16) + flag.encode())
y = pow(g, x, p)


def sign(m: bytes):
    z = h(m)
    k = h(long_to_bytes(x + z))
    r = h(long_to_bytes(pow(g, k, p)))
    s = (z + x*r) * inverse(k, q) % q
    return r, s


def verify(m: bytes, r: int, s: int):
    z = h(m)
    sinv = inverse(s, q)
    gk = pow(g, sinv*z, p) * pow(y, sinv*r, p) % p
    r2 = h(long_to_bytes(gk))
    return r == r2


print("p =", p)
print("g =", g)
print("y =", y)

print("=== sign ===")
m = input("m = ").strip().encode()
if b"goma" in m:
    quit()

r, s = sign(m)
# print("r =", r) do you really need?
print("s =", s)

print("=== verify ===")
m = input("m = ").strip().encode()
r = int(input("r = "))
s = int(input("s = "))
assert 0 < r < q
assert 0 < s < q

ok = verify(m, r, s)
if ok and m == b"hirake goma":
    print(flag)
elif ok:
    print("OK")
else:
    print("NG")

明らかにDSA。署名オラクルがあるが、goma を含む文字列は署名してもらえない。また、署名のうちrは意地悪で渡してもらえない

目的はhirake gomaの署名になっている(r, s)を得ること

署名プロセスが一般的なDSAと少し異なっている。一般的には $k$ は乱数で、 $r = g^k \mod p$ となるところが、 $k$ は $x + z$ のsha256をとったもの、 $r$ は $g^k \mod p$ のsha256をとったものになっている

def sign(m: bytes):
    z = h(m)
    k = h(long_to_bytes(x + z))
    r = h(long_to_bytes(pow(g, k, p)))
    s = (z + x*r) * inverse(k, q) % q
    return r, s

この問題では $p, q$ は1024bit程度なのにたいして、 $r, k$ は256bitで比較的小さいことがわかる

また、 $x$ も次のようにsha256を使って生成されており256bit程度

x = h(secrets.token_bytes(16) + flag.encode())

署名がなりたっているということは以下の式が成り立つということ。

$s \equiv (z + xr) / k \mod q$

これを式変形して以下のように表す。ただし $t = z + xr$ と置いた

$sk \equiv t \mod q$

$k, t$ はそれぞれ256bit, 512bit程度で $q$ に比べて小さい。

$sk - tq$ ができるだけ小さくなるように $k, t$ を選べばよいわけだから、次のような基底のLLLで $k, t$ がもとまる

$\begin{pmatrix} 1 & s \ 0 & q \ \end{pmatrix}$

$k$ が分かれば $r$ が求まり、 $r$ が求まれば $x = (t - z)/r$ として $x$ がわかる。 $x$ がわかったので署名はやり放題で、hirake goma も署名できそう

from ptrlib import Socket
from hashlib import sha256
from Crypto.Util.number import long_to_bytes, inverse

def thues_lemma(a, mod):
    R = Zmod(mod)
    A = matrix([
        [1,   a],
        [0, mod]
    ])
    A = A.LLL()
    return int(abs(A[0][0])), int(abs(A[0][1]))

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


g = 2
def sign(m: bytes):
    z = h(m)
    k = h(long_to_bytes(x + z))
    r = h(long_to_bytes(pow(g, k, p)))
    s = (z + x*r) * inverse(k, q) % q
    return r, s

q = 139595134938137125662213161156181357366667733392586047467709957620975239424132898952897224429799258317678109670496340581564934129688935033567814222358970953132902736791312678038626149091324686081666262178316573026988062772862825383991902447196467669508878604109723523126621328465807542441829202048500549865003
p = 2*q + 1

sock = Socket("localhost", 9999)
m = b"the quick brown fox"

sock.sendlineafter("m = ", m)
# r = int(sock.recvlineafter("r = "))
s = int(sock.recvlineafter("s = "))

t, k = thues_lemma(s, q)
if k > t:
    t, k = k, t
r = h(long_to_bytes(pow(g, k, p)))
x = (t - h(m)) * inverse(r, q) % q

m2 = b"hirake goma"
r2, s2 = sign(m2)

sock.sendlineafter("m = ", m2)
sock.sendlineafter("r = ", str(r2))
sock.sendlineafter("s = ", str(s2))

print(sock.recvline())