Crypto-Snore Signatures

These signatures are a bore! - Richard

Full Implementation

Challenge

def main():
    p, q, g = gen_snore_group()
    print(f"p = {p}")
    print(f"q = {q}")
    print(f"g = {g}")

    queries = []
    for _ in range(10):
        x, y = snore_gen(p, q, g)
        print(f"y = {y}")

        print('you get one query to the oracle')

        m = int(input("m = "))
        queries.append(m)
        s, e = snore_sign(p, q, g, x, m)
        print(f"s = {s}")
        print(f"e = {e}")

        print('can you forge a signature?')
        m = int(input("m = "))
        s = int(input("s = "))
        # you can't change e >:)
        if m in queries:
            print('nope')
            return
        if not snore_verify(p, q, g, y, m, s, e):
            print('invalid signature!')
            return
        queries.append(m)
        print('correct signature!')

    print('you win!')
    print(open('flag.txt').read())

First, we see how the signatures are being created

def gen_snore_group(N=512):
    q = getPrime(N)
    for _ in range(LOOP_LIMIT):
        X = getrandbits(2*N)
        p = X - X % (2 * q) + 1
        if isPrime(p):
            break
    else:
        raise Exception("Failed to generate group")
    r = (p - 1) // q
    for _ in range(LOOP_LIMIT):
        h = randint(2, p - 1)
        if pow(h, r, p) != 1:
            break
    else:
        raise Exception("Failed to generate group")
    g = pow(h, r, p)
    return (p, q, g)

$$p = X - (X \ mod \ 2q) + 1 \\ p = 2kq +1 \\ r = 2k \\ g = h^r \ mod \ p$$

def snore_gen(p, q, g, N=512):
    x = randint(1, q - 1)
    y = pow(g, -x, p)
    return (x, y)

def hash(val, bits=1024):
    output = 0
    for i in range((bits//512) + 1):
        h = SHA512.new()
        h.update(long_to_bytes(val) + long_to_bytes(i))
        output = int(h.hexdigest(), 16) << (512 * i) ^ output
    return output

def snore_sign(p, q, g, x, m):
    k = randint(1, q - 1)
    r = pow(g, k, p)
    e = hash((r + m) % p) % q
    s = (k + x * e) % q
    return (s, e)

$$r = g^k \mod p \\ e = hash((r+m_1) \ mod \ p) \ mod \ q\\ s = k+xe \mod q \\ k = s-xe \mod q$$

The server allows us to sign a message m and gives us s,e

def snore_verify(p, q, g, y, m, s, e):
    if not (0 < s < q):
        return False
    rv = (pow(g, s, p) * pow(y, e, p)) % p
    ev = hash((rv + m) % p) % q
    return ev == e

In the signature verification, we need to give s,m such that hash(rv+m) == e

$$rv = g^s \times y^e \ mod \ p \\ rv = g^s \times g^{-xe} \ mod \ p \\ rv = g^{s-xe} \ mod \ p \\ ev = hash((rv + m_2) \ mod \ p ) \ mod \ q \\$$

If we give the same s and m we used to sign then

$$rv = g^{s-xe} \mod p \\ rv = g^k \mod p \\ r = g^k \mod p \\ ev = hash((rv + m) \ mod \ p ) \ mod \ q \\ e = hash((r+m) \ mod \ p) \ mod \ q \\ ev ==e$$

However, the server has a condition which doesn't allow us to repeat the same message for signature and verification. So, we need to find m1 and m2 such that

$$hash((rv + m_1) \ mod \ p ) \ mod \ q =hash((r+m_2) \ mod \ p) \ mod \ q \\ rv+m_1\equiv r+m2 \pmod p \\ m_1 \equiv m2 \pmod p$$

We can send m1 and m2 as multiples of p to bypass this condition and forge the signature.

from pwn import *
cmd = "ncat --ssl snore-signatures.chal.uiuc.tf 1337"
r = process(cmd,shell=True,stdin=PTY)
r1=r.recvuntil("m =")
p = int(r1.decode().split("\n")[0][3:])
r.sendline("0")
r2=r.recvuntil("m =")
s=int(r2.decode().split("\n")[0][4:])
r.sendline(str(p*1))
r.recvuntil("s =")
r.sendline(str(s))
for i in range(2,11):
    r1=r.recvuntil("m =")
    r.sendline("0")
    r2=r.recvuntil("m =")
    print(r2)
    s=int(r2.decode().split("\n")[0][4:])
    r.sendline(str(p*i))
    r.recvuntil("s =")
    r.sendline(str(s))
print(r.recv())
b'correct signature!you win!uiuctf{add1ti0n_i5_n0t_c0nc4t3n4ti0n}'