Snore Signatures

These signatures are a bore!

ncat --ssl snore-signatures.chal.uiuc.tf 1337

Here’s the Python source:

1
#!/usr/bin/env python3
2

3
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long
4
from Crypto.Random.random import getrandbits, randint
5
from Crypto.Hash import SHA512
6

7
LOOP_LIMIT = 2000
8

9

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

18

19
def gen_snore_group(N=512):
20
    q = getPrime(N)
21
    for _ in range(LOOP_LIMIT):
22
        X = getrandbits(2*N)
23
        p = X - X % (2 * q) + 1
24
        if isPrime(p):
25
            break
26
    else:
27
        raise Exception("Failed to generate group")
28

29
    r = (p - 1) // q
30

31
    for _ in range(LOOP_LIMIT):
32
        h = randint(2, p - 1)
33
        if pow(h, r, p) != 1:
34
            break
35
    else:
36
        raise Exception("Failed to generate group")
37

38
    g = pow(h, r, p)
39

40
    return (p, q, g)
41

42

43
def snore_gen(p, q, g, N=512):
44
    x = randint(1, q - 1)
45
    y = pow(g, -x, p)
46
    return (x, y)
47

48

49
def snore_sign(p, q, g, x, m):
50
    k = randint(1, q - 1)
51
    r = pow(g, k, p)
52
    e = hash((r + m) % p) % q
53
    s = (k + x * e) % q
54
    return (s, e)
55

56

57
def snore_verify(p, q, g, y, m, s, e):
58
    if not (0 < s < q):
59
        return False
60

61
    rv = (pow(g, s, p) * pow(y, e, p)) % p
62
    ev = hash((rv + m) % p) % q
63

64
    return ev == e
65

66

67
def main():
68
    p, q, g = gen_snore_group()
69
    print(f"p = {p}")
70
    print(f"q = {q}")
71
    print(f"g = {g}")
72

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

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

80
        m = int(input("m = "))
81
        queries.append(m)
82
        s, e = snore_sign(p, q, g, x, m)
83
        print(f"s = {s}")
84
        print(f"e = {e}")
85

86
        print('can you forge a signature?')
87
        m = int(input("m = "))
88
        s = int(input("s = "))
89
        # you can't change e >:)
90
        if m in queries:
91
            print('nope')
92
            return
93
        if not snore_verify(p, q, g, y, m, s, e):
94
            print('invalid signature!')
95
            return
96
        queries.append(m)
97
        print('correct signature!')
98

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

102
if __name__ == "__main__":
103
    main()

We’re provided a very simple signature forgery problem for what seems like a Schnorr signature scheme. First, we are provided p, q, and g, which will remain constant for each query-verification process. At the start of each iteration of the for loop, we are provided y. Then, we are allowed one query of any message m that we have not used before, and are given the result s and e from the signature. We are then supposed to submit a message, signature pair of m and s, such that m has not previously been seen by the oracle, such that the pair will produce the same e.

Now, I actually saw people in the discord server mentioning that you can just add multiples of p to m, which does actually work, since the server considers it different. However, I think my solution was actually the intended.

Essentially, it all lies in how the signature is verified.

1
def snore_verify(p, q, g, y, m, s, e):
2
    if not (0 < s < q):
3
        return False
4

5
    rv = (pow(g, s, p) * pow(y, e, p)) % p
6
    ev = hash((rv + m) % p) % q
7

8
    return ev == e

Remember, we know p, q, g, and y, and we control m and s. Well, what if just increment s by 1. Then rv will change, but, importantly, since we know all the variables of the expression, we can pretty simply calculate the new value of rv. Then, we can subtract the difference between the new and old value of rv from m (under modulo p), since only rv + m actually matters in the calculation of ev. Thus, our final ev will still equal e!

Here’s my implementation:

1
from pwn import *
2
from Crypto.Util.number import *
3

4
r = remote('snore-signatures.chal.uiuc.tf', 1337, ssl=True)
5

6
def rn():
7
    return int(r.recvline().decode('ascii').split('= ')[-1][:-1])
8

9

10
p = rn()
11
q = rn()
12
g = rn()
13

14
for i in range(10):
15

16
    r.recvuntil(b'y = ').decode('ascii')
17
    y = rn()
18

19
    m = i
20
    r.sendlineafter(b'm = ', str(m).encode())
21

22
    s = rn()
23
    e = rn()
24

25
    o_rv = (pow(g, s, p) * pow(y, e, p)) % p
26

27
    s += 1
28

29
    n_rv = (pow(g, s, p) * pow(y, e, p)) % p
30

31
    n_m = ((o_rv - n_rv) + m) % p
32

33
    r.sendlineafter(b'm = ', str(n_m).encode())
34
    r.sendlineafter(b's = ', str(s).encode())
35

36

37
r.interactive()

1
uiuctf{add1ti0n_i5_n0t_c0nc4t3n4ti0n}