CakeCTF 2023: simple signature Upsolve

simple signature

authored by theoremoon

It must be a piece of cake.

import os
import sys
from hashlib import sha512
from Crypto.Util.number import getRandomRange, getStrongPrime, inverse, GCD
import signal


flag = os.environ.get("FLAG", "neko{cat_does_not_eat_cake}")

p = getStrongPrime(512)
g = 2


def keygen():
    while True:
        x = getRandomRange(2, p-1)
        y = getRandomRange(2, p-1)
        w = getRandomRange(2, p-1)

        v = w * y % (p-1)
        if GCD(v, p-1) != 1:
            continue
        u = (w * x - 1) * inverse(v, p-1) % (p-1)
        return (x, y, u), (w, v)


def sign(m, key):
    x, y, u = key
    r = getRandomRange(2, p-1)

    return pow(g, x*m + r*y, p), pow(g, u*m + r, p)


def verify(m, sig, key):
    w, v = key
    s, t = sig

    return pow(g, m, p) == pow(s, w, p) * pow(t, -v, p) % p


def h(m):
    return int(sha512(m.encode()).hexdigest(), 16)


if __name__ == '__main__':
    magic_word = "cake_does_not_eat_cat"
    skey, vkey = keygen()

    print(f"p = {p}")
    print(f"g = {g}")
    print(f"vkey = {vkey}")

    signal.alarm(1000)

    while True:
        choice = input("[S]ign, [V]erify: ").strip()
        if choice == "S":
            message = input("message: ").strip()
            assert message != magic_word

            sig = sign(h(message), skey)
            print(f"(s, t) = {sig}")

        elif choice == "V":
            message = input("message: ").strip()
            s = int(input("s: ").strip())
            t = int(input("t: ").strip())

            assert 2 <= s < p
            assert 2 <= t < p

            if not verify(h(message), (s, t), vkey):
                print("invalid signature")
                continue

            print("verified")
            if message == magic_word:
                print(f"flag = {flag}")
                sys.exit(0)

        else:
            break

Signを呼び出すと、magic_word以外の任意のmessageへの署名をもらえます。
Verifyを呼び出すと、任意のmessageと署名$(s,t)$を渡して検証してもらえます。そして、messageがmagic_wordと一致するとチェックされ、一致したらフラグを得られます。

解法

まず、署名と検証の式を追ってみましょう。
署名は
$$
s \equiv g^{xm+ry} \pmod p , t \equiv g^{um+r} \pmod p
$$
であり、検証は
$$
g^m \equiv s^w \cdot t^{-v} \pmod p
$$
と表せます。
検証の式を$t$について解くと、
$$
t^v \equiv s^w \cdot g^{-m}\pmod p
$$
となります。
さて、keygenを見てみると、
$$
u \equiv (wx-1)\cdot v^{-1} \pmod {p-1}
$$
を定義されています。さらに、

if GCD(v, p-1) != 1: continue

としていることから、$v$は必ずmod(p-1)で逆元$v^{-1}$を持ちます。
先ほどの$t$についての式に両辺を$v^{-1}$乗すると
$$
t \equiv (s^w \cdot g^{-m})^{v^{-1}\pmod{p-1}} \pmod p
$$
となるため、適当な$s$を取得し、検証が必ず通るような$t$を作ることによって検証に成功します。
最後にmagic_wordと作成した$(s,t)$を送ればフラグを取得できます。

import secrets
from hashlib import sha512
from pwn import *
from Crypto.Util.number import inverse, GCD


HOST = "34.170.146.252"
PORT = 45482

MAGIC_WORD = "cake_does_not_eat_cat"


def h(msg):
    return int(sha512(msg.encode()).hexdigest(), 16)

io = remote(HOST, PORT)

io.recvuntil(b"p = ")
p = int(io.recvline().strip().decode())
io.recvuntil(b"g = ")
g = int(io.recvline().strip().decode())
io.recvuntil(b"vkey = (")
wv = io.recvline().strip().decode().rstrip(")")
w, v = wv.split(",")
w = int(w)
v = int(v)
m = h(MAGIC_WORD)

if GCD(v, p - 1) != 1:
        raise ValueError("Unexpected: gcd(v, p-1) != 1")

inv_v = inverse(v, p - 1)
gm = pow(g, m, p)
inv_gm = inverse(gm, p)

while True:
    s = secrets.randbelow(p - 3) + 2
    sw = pow(s, w, p)
    base = (sw * inv_gm) % p
    t = pow(base, inv_v, p)

    if 2 <= t < p:
        break

io.sendlineafter(b": ", b"V")
io.sendlineafter(b"message: ", MAGIC_WORD.encode())
io.sendlineafter(b"s: ", str(s).encode())
io.sendlineafter(b"t: ", str(t).encode())

io.interactive()

Flag: CakeCTF{does_yoshiking_eat_cake_or_cat?}