redpwnCTF 2020

June 25, 2020

Here are the writeups for all of Tux’s challenges, with solution code. I believe we were the only team to max crypto :)

ratification

This challenge had an unintended solution, so sig1 and sig2 aren’t necessary. The main idea is to use the homormophic properties of RSA to recover n. Since the server already leaks p, that’s enough to break RSA.

Consider a message M and its integer square, M^2. Then their signatures are

Sign(M) := M^d
Sign(M^2) := (M^2)^d == (M^d)^2

In other words, we receive some signature S and S', where the latter former squared modulo n. Notably, if we compute S^2 ourselves, we have the equations

S^2 - S' == 0 (mod n)
S^2 - S' == kn

The one issue that remains is that we send string representations of these numbers, which must be valid unicode. Fortunately, Python will accept small bytes like \x02 and \x04. Solution code here.

P.S. There is nothing special about squares, you can multiply any two messages together and its signature will be the component signatures squared modulo n. Squaring just means that I can use fewer signatures :)

seekrypt

This is a standard implementation of the Goldwasser-Micali cryptosystem with an additional “hint” provided.

We know the composite modulus mod = alpha*beta, as well as some hint y where

y := alpha ^ (flag2 << 0x1f0)

and flag2 is the second half of the flag. Notice that the flag is less than 100 bytes, which guarantees that flag2 is less than 50 bytes, or equivalently 400 bits.

Given that alpha is 1024 bits, this implies that y and alpha share a lot of bits! flag2 only overwrites 400 middle bits:

y == 128 alpha bits | 400 garbage bits | 0x1f0 alpha bits

This should hopefully remind you of a common attack used in RSA: factoring with known prime bits. We can then construct a polynomial and solve for small roots where alpha is approximated by y with those middle 400 bits zeroed out. Recovering x gives us both alpha and flag2, and solve flag1 can simply be decrypted now that we know the private key. Solution code here.

speedy signatures

This was honestly a very tedious challenge to implement, so I’ll go over the main ideas. You may be familiar with ECDSA nonce reuse, but it turns out that as long as you have to signatures which even have related nonces, ECDSA is totally broken.

More specifically, given two signatures that use nonces k, k+diff, we have equations

s1 == inv(k) * (h1 + r1*d) (mod n)
s2 == inv(k + diff) * (h2 + r2*d) (mod n)

where n is the order of the curve. Isolating the nonces:

k == inv(s1) * (h1 + r1*d)
k + diff == inv(s2) * (h2 + r2*d)

Subtracting the first equation from the second:

diff == inv(s2) * (z2 + r2*d) - inv(s1) * (z1 + r1*d)
diff + inv(s1)*z1 - inv(s2)*z2 == d * (inv(s2)*r2 - inv(s1)*r1)
d == (diff + inv(s1)*z1 - inv(s2)*z2) * inv(inv(s2)*r2 - inv(s1)*r1)

Hooray, we have the private key! However, this challenge does not generate nonces like this. Instead, it uses a common base value and adds a random number from 1 to 4096 each time. This implies that diff := k2-k1 falls between -4095 and 4095. We can easily bruteforce all possible differences and check to see whether the resulting candidate is indeed the private key; that is, dG == Q.

The issue is that the server only returns 3 values out of (r1, s1, r2, s2). Furthermore, they are randomly shuffled. Very annoying.

Let’s hope that in the first round, either r1 or r2 is removed. Without loss of generality, suppose it is r1 (we could simply switch our labels otherwise). We can map r1 back to a point P on the curve. This can be done by solving for y in the corresponding equation:

y^2 == x^3 + ax + b (mod p)
y == sqrt(x^3 + ax + b) (mod p)

Notice that this modulus is p, which is not the curve order n. You can take modular square roots using Tonelli-Shanks, but remember that there will be two solutions: y and -y. I think it doesn’t matter which one we use because of symmetry, but one could test both just in case.

Since r2 is the x-coordinate of P + diff*G, we can recover it and extract the private key! We’ll also want to calculate one of the nonce values, for future use.

k1 == inv(s1)*(h1 + r1*d) (mod n)

In the remaining 99 rounds, we only have to use one signature to extract the private key. So regardless of which value the server removes, there will always be a full signature in the 3-tuple it sends; call it (r, s). Let’s also send the same message for both signatures so we always know the hash h.

Since the nonce generation base value is held constant across rounds, we can bruteforce the difference between k1 and the new nonce. For every possible nonce k, the candidate private key is

d := (s*k - h)*inv(r) (mod n)

To review: we hope that the first round returns both s values. If not, reset the connection. Then brute force the nonce difference to recover the private key and k1, which approximates the common base value. In any subsequent round, we bruteforce the actual nonce value using k1. Solution code here.

jeopardy

Our goal is to supply the server with a weak elliptic curve. However, the server has a number of restrictions:

The vulnerability is that the server checks primality using a custom implementation of Miller-Rabin, which only performs one round. Hence we want to find a composite number that tricks Miller-Rabin with significant probability. It must also have relatively small prime factors, so we can run Pohlig-Hellman efficiently.

This paper is a great resource. It tells us to look for Carmichael numbers whose prime factors are all 3 mod 4. When this is the case for some C with m factors, the probability of tricking Miller-Rabin is 1/2^(m-1).

Since this is a golf challenge, we want to find Carmichael numbers with bit length as close to 256 as possible. Fortunately, the paper describes how to generate large Carmichael numbers from small ones.

We could also figure out how to generate Carmichael numbers in general, but I found a list of all C < 10^16 online. The resource is 404, but if you go on Wayback Machine back to 2007, you can download the archive there (lol). My method for choosing which one to use was pretty arbitrary, but I settled on 5 * 13 * 19 * 23 * 37 * 397, which generates:

C := 2546219544036917612349940381838413660553096101698112741559701
  == 1837470101 * 5512410301 * 8268615451 * 10106085551 * 16537230901 * 181909539901

This doesn’t satisfy the mod 4 requirement, but it’s adequate for tricking the server. C has bit length 201, which satisfied the golf requirements at the time that I solved the challenge. Each prime factor has bit length < 40, so Pohlig-Hellman is easily doable.

Next, we have to generate a curve with order C. I used ecgen, which is an evil, unmaintained tool for generating elliptic curves. Someone needs to rewrite this in Sage. Building this is a pain in the ass, so just download the binary and run the before_install commands in the Travis CI build.

Sage provides an implementation of Pohlig-Hellman, but it doesn’t let you supply the factorization. I ended up jacking the source code. And this is enough! Just hurl C at the server until it accepts it and recover the secret key. Solution code here.

newcrypt

Our goal is to factor an RSA modulus, given a set of four hints. The hints are essentially the public keys corresponding to four small private keys. On average, the private keys are 896 bits, which is approximately n^.44.

In the case where there is a single small private key, there are a number of standard attacks: Boneh-Durfee and Wiener’s attack are the most common. However, these private keys far exceed the conventional bounds of n^.28. We need to somehow combine our knowledge of 4 small private keys to raise the bound.

There exist variants of Boneh-Durfee which attack these so-called “simultaneous” bivariate equations, and I spent a long time trying to implement one. However, there’s also a Wiener’s variant which is much simpler and works just as well for these bounds. I highly recommend fully reading the paper, since I won’t explain every detail.

The main idea is that we can construct a matrix equation bM = v such that both b and v are small. Do you see where this is going?

LLL strikes again! v is a short vector in the lattice generated by M, so we can recover it by performing basis reduction on M. Then, all we have to do is solve the linear equation for b.

The paper provides M for two and three exponents, but only provides a good candidate b for four small exponents. It’s up to us to construct this lattice.

Again, I won’t into much detail about the reasoning, but each relation represents a column of the lattice. I computed the relation polynomials symbolically, then matched each term to one of the elements in b and wrote the corresponding e*n term in the lattice.

Try constructing the relations in the three exponent case and matching them against the lattice for a better idea of the process. I should also point out that the paper has incorrect sixth and seventh elements of b in that section.

Next, I had to figure out the diagonal matrix which optimizes the lattice’s determinant. To do so, I did a test run with alpha := .25 and another run with alpha := .5, noting the size of v’s elements. Since log_n(size) has a linear relationship with alpha, this was sufficient for determining the diagonal entries.

Once we have x, its elements are multiples of di and some other terms. We can recover each di (or some small multiple of it) by taking the gcd of every term containing it. Finally, ed-1 is some multiple of the totient, which is enough to invert 0x1337 and decrypt the flag. Solution code here.