The following Python code implements the encryption scheme:
#!/usr/bin/env python3
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long
from Crypto.Random.random import getrandbits, randint
from Crypto.Hash import SHA512
LOOP_LIMIT = 2000
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 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)
def snore_gen(p, q, g, N=512):
x = randint(1, q - 1)
y = pow(g, -x, p)
return (x, y)
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)
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
def main():
p, q, g = gen_snore_group()
print(f"p = {p}") # p is a prime
print(f"q = {q}") # q is a prime
print(f"g = {g}") # pow(h, r, p) where r = (p - 1) // q, h is a randint
queries = []
for _ in range(10):
# x is priv key, y is pub key
x, y = snore_gen(p, q, g) # y = pow(g, -x, p)
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) # we get the signature of m
print(f"s = {s}")
print(f"e = {e}")
print('can you forge a signature?')
# need to find an m for which s gives a valid signature
m = int(input("m = "))
s = int(input("s = "))
# you can't change e >:)
# since we can't change e, m' = m + ip
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())
if __name__ == "__main__":
main()
We start with the main() function. We obtain p, q and g by invoking gen_snore_group(). In gen_snore_group(), we generate the primes p and q, then calculate r = (p - 1) // q. Finally, we obtain g by doing g = pow(h, r, p) (h is a random int). p, q and g are all given to us as public information.
This is where things get interesting. A for loop iterates 10 times. Within each iteration, we first obtain x and y using snore_gen(p, q, g). x is a random integer and y = pow(g, -x, p).
y=g−x(modp)
We are given y, but not x. Then, we get one query to a signing oracle. The oracle takes in a message m of our choice, then calculates its signature (s, e) using s, e = snore_sign(p, q, g, x, m).
Let's try to understand the math behind snore_sign.
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)
It first generates a random integer k, then calculates r. r, m, p, q generate e, and k, x, e, q generate s. Expressing this mathematically,
r=gk(modp)
e=H((r+m)(modp))(modq)
s=(k+xe)(modq)
After we get the signature (s, e) from the query, we are asked to provide a message m (which we haven't used before), and a valid signature (s, e) for it (but our e must be the same as the one obtained from the query, so we can only change s).
If we can repeat this process of querying the signing oracle and forging a signature 10 times, we get the flag.
Next, let's look at the code for the signature verification:
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
snore_verify takes the m and s we provide. Then, we calculate rv followed by ev. Then we compare ev and the expected signature e to check if they match.
Let's try to work out why the verification would work if our given m and s were indeed correct.
We are given
rv=(gs(modp)×ye(modp))(modp)
=(gs×ye)(modp)
Combining this with the equations from snore_sign, we have
rv=g(k+xe)(modq)×(g−x(modp))e(modp)
which simplifies to
rv=g(k+xe)×g−xe(modp)
=gk(modp)
Then we have
ev=H((rv+m)(modp))(modq)
If our provided s and m were correct, this equation would be the same as our hash e.
So... How do we forge a signature? The key is in identifying a vulnerability in the computation of ev. When we compute the hash during verification, we should be concatenating rv to m instead of adding them together. To forge a signature we can follow the process below:
Query the oracle using a message m, and obtain the signature (s, e).
To forge a signature, send an m' such that m' = m + ip, where i is a positive integer.
Why does this work?
Since we are reusing s, we know that it has to be equivalent to k + xe even though we don't know k and x! This would give us rv=r
Since m' = m + ip, (rv+m′)(modp)=(rv+m)(modp). As such, we would get ev=e
Using pwntools, I wrote a script to repeat this procedure 10 times and obtain the flag from the server. Since it remembers the values of m from previous queries and prevents us from reusing them, I use the following values of m and m' for the 10 iterations: