This year's redpwnCTF had some nice crypto challenges (scrambled-elgs, keeper-of-the-flag, retrosign), but also had some rather guessy and bad challenges (round-the-bases, quaternion-revenge). Particularly quaternion-revenge, where we spent hours trying to work out a solution only to find that sending
i*i (or something similar) gives the flag, despite this not even making sense (since
i*i = -p). In hindsight, we should have tried this earlier, but regardless, having "strange" behaviour on the remote without there being a good reason for, or without it being made explicit, is poor challenge design. The crypto category was very easy compared to the other categories, but overall, the CTF was well-run and fun to play.
Keeper of the Flag
can you convince keeper of the flag to give you flag?
nc mc.ax 31538
#!/usr/local/bin/python3 from Crypto.Util.number import * from Crypto.PublicKey import DSA from random import * from hashlib import sha1 rot = randint(2, 2 ** 160 - 1) chop = getPrime(159) def H(s): x = bytes_to_long(sha1(s).digest()) return pow(x, rot, chop) L, N = 1024, 160 dsakey = DSA.generate(1024) p = dsakey.p q = dsakey.q h = randint(2, p - 2) g = pow(h, (p - 1) // q, p) if g == 1: print("oops") exit(1) print(p) print(q) print(g) x = randint(1, q - 1) y = pow(g, x, p) print(y) def verify(r, s, m): if not (0 < r and r < q and 0 < s and s < q): return False w = pow(s, q - 2, q) u1 = (H(m) * w) % q u2 = (r * w) % q v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q return v == r pad = randint(1, 2 ** 160) signed =  for i in range(2): print("what would you like me to sign? in hex, please") m = bytes.fromhex(input()) if m == b'give flag' or m == b'give me all your money': print("haha nice try...") exit() if m in signed: print("i already signed that!") exit() signed.append(m) k = (H(m) + pad + i) % q if k < 1: exit() r = pow(g, k, p) % q if r == 0: exit() s = (pow(k, q - 2, q) * (H(m) + x * r)) % q if s == 0: exit() print(H(m)) print(r) print(s) print("ok im done for now") print("you visit the flag keeper...") print("for flag, you must bring me signed message:") print("'give flag':" + str(H(b"give flag"))) r1 = int(input()) s1 = int(input()) if verify(r1, s1, b"give flag"): print(open("flag.txt").readline()) else: print("sorry")
The server implements DSA and requires us to forge a signature for the message "give flag" to get the flag. We can obtain two signatures from the server for two different messages (other than the message that we need to sign to get the flag).
Below is a brief overview of DSA, see wikipedia for full details.
- Choose a key length and a modulus length (common values, and the values used in the challenge, are )
- Choose an -bit prime , and an -bit prime such that
- Choose a random and compute . This is done so that is a generator of the subgroup of order
- Choose a secret signing key
- The private key is and the public key is
To sign a message :
- Choose a random nonce (this must be random!)
- Compute , where is a cryptographic hash function
The signature is .
To verify a signature :
- Check that and , otherwise return invalid signature
- Check that , otherwise return invalid signature
After reading the server code and verifying that the signing and verifying implementation is sound we notice that two things are different from standard DSA; the hash function, and the nonce generation. Specifically, the generated nonces are not random enough. They are given by , where is some random number that is fixed across both of the signings that we have access to.
Bad Nonces in DSA
Before we proceed, we look at how detrimental bad nonces are in DSA. Given two signatures and (for messages and ) signed by a single private key and related nonces and (for some known linear function ), we can recover . From step 3 of the signing procedure, we have the relations
This is a linear system in the unknowns and , and can therefore be easily solved.
Solving the Challenge
Now that we have the motivation, we notice that if we choose our two messages and such that we know the relation between the two nonces that are derived from these messages, we can recover the secret signing key and forge the required signature. Peculiarly, the custom hash function being used is based on SHA1 which is known to be broken. We can find 640-byte collisions from here. Notice that if the hashes for two messages are the same, then the nonces will differ by 1. This puts us in the situation of the previous section, so we can recover the secret signing key.
To actually solve the system of equations found in the previous section, we make use of Sage's convenient methods for doing so. Of course, we could rearrange the terms by hand to isolate , but that is annoying and error prone. It also becomes a lot harder when we have more than two equations. There are two methods I like to use. One is by Gröbner basis techniques, and another is by taking resultants.
Gröbner basis: We construct the two polynomials and find the variety of the ideal generated by them. The variety is simply the set of solutions satisfying both polynomials. Under the hood, it is computed by first finding a Gröbner basis of the ideal, which can be thought of as a new set of polynomials that generate the same ideal, but with nicer properties that make it easier to find the solutions of the system.
R.<k,x> = GF(q) f1 = s1*k - h1 - x*r1 f2 = s2*(k+1) - h2 - x*r2 V = Ideal([f1, f2]).variety() k, x = V[k], V[x]
Resultants: We construct the two polynomials as before and eliminate a variable (in this case
k), by taking the resultant of the two polynomials. Sage has inbuilt
resultant methods for polynomials over the integers, but for polynomials over finite integer rings, it seems to not work. We can define our own resultant function from its definition as the determinant of the Sylvester matrix of the two polynomials. Once we eliminate one variable, we are left with a polynomial in the other variable (in this case
x). Sage has an inbuilt method to find roots of univariate polynomials modulo prime integers, so we can use that to recover
from sage.matrix.matrix2 import Matrix def resultant(f1, f2, var): return Matrix.determinant(f1.sylvester_matrix(f2, var)) R.<k,x> = GF(q) f1 = s1*k - h1 - x*r1 f2 = s2*(k+1) - h2 - x*r2 x = resultant(f1, f2, k).univariate_polynomial().roots()
Full solve script:
from pwn import * from hashlib import sha1 messageA = open('./messageA', 'rb').read() messageB = open('./messageB', 'rb').read() assert sha1(messageA).digest() == sha1(messageB).digest() assert messageA != messageB conn = remote('mc.ax', 31538) print(conn.recvline().decode()) conn.sendline(input('pow: ')) conn.recvuntil('solution: ') p = int(conn.recvline().decode()) q = int(conn.recvline().decode()) g = int(conn.recvline().decode()) y = int(conn.recvline().decode()) conn.recvline() conn.sendline(messageA.hex()) h1 = int(conn.recvline().decode()) r1 = int(conn.recvline().decode()) s1 = int(conn.recvline().decode()) conn.recvline() conn.sendline(messageB.hex()) h2 = int(conn.recvline().decode()) r2 = int(conn.recvline().decode()) s2 = int(conn.recvline().decode()) R.<k,x> = GF(q) f1 = s1*k - h1 - x*r1 f2 = s2*(k+1) - h2 - x*r2 # V = Ideal([f1, f2]).variety() # k, x = V[k], V[x] from sage.matrix.matrix2 import Matrix def resultant(f1, f2, var): return Matrix.determinant(f1.sylvester_matrix(f2, var)) x = resultant(f1, f2, k).univariate_polynomial().roots() conn.recvline() conn.recvline() conn.recvline() h = int(conn.recvline().decode().split(':')) k = int(1337) r = pow(g, k, p) % q s = (pow(k, q-2, q) * (h + x * r)) % q conn.sendline(str(r)) conn.sendline(str(s)) print(conn.recvline().decode())