N1CTF2020

An A+ CTF! An incredible amount of tasks, from mid-tier to top-tier difficulty level. Objectively the task set alone deserves a ~100 rating on CTFTime¹.

I did the crypto tasks and will outline solves for those below. I won't post full problems or detailed expositions, it's more just notes that should allow anyone who attempted the problems to solve them. I also glanced at some of the "easier" tasks in misc and web, but even the entry-level tasks in those categories was beyond me.

Personal downside #1: very biased toward web, rev, and pwn, which I am pretty clueless about, though those are the "true" staples of CTF. I realize this is more like a pure upside for most people.

On the end of the first day there were only three crypto tasks released yet more than fifteen(!?) web, pwn, and rev tasks out. I sat around twiddling my thumbs a bit, feeling pretty useless.

The only misc-like task I saw involved PHP, which is more of a mental plague than a programming language². I played around with it a bit, but finally just went to bed feeling a little bit dumber and somewhat frustrated because I thought all tasks had been released and that I'd be useless for the rest of the CTF.

Personal downside #2: Two more crypto were released just after I'd gone to sleep on day two, so I only had a few hours for them when I woke up. Although the new tasks were a nice surprise, the timing was very unfortunate for me.

Plea for organizers in general: please consider having all tasks out by the mid-way point of the CTF. If not, then communicate your planned task release schedule so it's possible to better manage our time?

We ended up placing 13th³.

You're given some code which generates a QR-code image of the flag and uses that image to create two new randomized images which–when combined–would reconstruct the original (albeit transposed? I am guessing, I didn't actually run the code). You also receive one of the images generated. It struck me as a little cryptic.

I ignored the whole visual threshold part of the task and noted it uses Python's random module to generate the pixels in the output images. That's a lot of random data, and the QR-code image it's based on has a lot of known fixed output. After double-checking that the QR-image had enough known pixels (you get to reverse one bit of state per pixel) and where it was (it would be hell if it wasn't contiguous), it reduces to a "standard" reverse-the-RNG-state task.

For the reversing Python's MT the easy way you need \(32 \cdot 672\) contiguous bits of output. That is if you don't have to worry about missing state. You need to undo the tempering that MT does to its output words:

def untemper(x):
  x ^= (x >> 18)
  x ^= (x << 15) & 0xefc60000
  x ^= ((x << 7) & 0x9d2c5680) ^ ((x << 14) & 0x94284000) ^ ((x << 21) & 0x14200000) ^ ((x << 28) & 0x10000000)
  x ^= (x >> 11) ^ (x >> 22)
  return x

You combine words i, i+1, and i+M to get word i+N:

tmp = w[i][31] ^ w[i+1][:31]  # using slice notation to select bits
w[i+N] = tmp>>1 ^ w[i+M] ^ (A if tmp[0] else 0)

M, N, A are constants from _randommodule.c in CPython source code. Then you reapply the tempering (see aforementioned .c source) and it should match Python's output. That's the basic idea.

It was a task which is very easy to realize the solution but rather painful to implement. I struggled with infinite little indexing bugs. The headache I got from trying to directly indexing into bin(random.getrandbits(...)) was not worth it. (Bits within words run from bit \(2^{31}\) to \(1\), but the words are in little-endian order.) I even had bugs in the final solution as some randomness was leaking through, but fortunately QR-codes are highly redundant, so I didn't care. Then again I probably did things needlessly complicated by reverse-generating the original QR-code instead of simply generating the "companion" image to the one shared.

Apart from headaches it gave me with my own bugs, it's actually a fairly clever task, because there aren't any obvious "hints" that points you in the right direction, so it might take a while to notice. I was pretty lucky.

Several random 256-bit elliptic curves are generated and used to do a standard key exchange to AES-encrypt the flag. The curves are all asserted to be non-smooth and resistant to MOV attack. You get the public output of the exchanges as well as the encrypted messages. It's a very nice and clean task with a likewise straightforward implementation. It was a pure blessing after the indexical spaghetti that was VSS.

The key to realize is that the secret is reused (for both client and server). The generated random curves have a lot of small random subgroups, so you can solve the discrete log in those subgroups (multiply the generator and public keys by \((p-1)/q\) to put it in the subgroup of size \(q\)), get constraints like \(secret = x_i \pmod{q_i}\), and then do Chinese Remainder when you have enough. A partial Pohlig-Hellman, if you will.

I think I did most of this task in REPL, but the pseudo-code sketch would be:

crt_r, crt_s = [], []
for ec,pk_r,pk_s in data:
  order = ec.order()
  for f in small_factors(order):
    crt_r.append( (babystepgiantstep(f, pk_r*(order/f), g*(order/f)), f) )
    crt_s.append( (babystepgiantstep(f, pk_s*(order/f), g*(order/f)), f) )

r,s = crt(*crt_r)[0], crt(*crt_s)[0]

In this task (against a live server) you're asked for elliptic curve parameters \((p, a, b)\) and two points \((G_1, G_2)\) and then have to solve 30 rounds of distinguishing \(G_1 \cdot r \cdot s\) from \(G_1 \cdot x\) when given \(G_1 \cdot r\) and \(G_2 \cdot s\) (for random secret integers \(r, s, x\)). It will throw an exception if you give it a singular curve or points not on the curve.

At first glance I thought this was too similar to FlagBot, because there are no checks against the points being in a small subgroup. I knew you could also use trace 1 curves on which the much-copy-pasted Smart attack works, but I only have that code in some Sage docker; I wanted to use my own comfortable code and homemade Python libraries. Besides, I got this: I thought it would just be a matter of trivially putting them into small subgroups and solving the CRT again. A bit too easy, maybe…

Yeah, after a while I realized my oops: it required a very large prime modulus \(p\) and calls E.order() on the curve – and there's a timer on the program. The E.order() call takes well over a minute, sometimes several minutes, and so there's no time to do the loop. I wasted some time trying to find random curves for which E.order() was smooth or took less time but…

Finally I relented and tested E.order() on a curve with \(|E_p| = p\). It was instant, of course, so… sigh Copy-pasted Sage code it is, then.

Now the problem was to generate curves with trace 1, which I didn't know how to do, but poiko talked of a DEFCON task which had involved generating such curves and gave me a paper: http://www.monnerat.info/publications/anomalous.pdf

From the paper I figured I wanted curves under primes \(p = 11 m (m+1) + 3\) with \((a,b)\) which gives j-invariant equal to \(-2^{15}\), I quickly found plenty such curves. Then copy-paste Smart_Attack() and blah, blah, the usual stuff. (I really despise copy-pasting.) A bit unrewarding due to my stubbornness, but I have to admit it was a good task in the end, even if the "hidden" constraint of "the given curve must also have a fast E.order()" was a bit devious⁴.

A fun task which had two stages.

It generates some RSA-modulus \(n = p*q\) and encrypts a large vector with lots of numbers. These numbers are the vector (dot) products between the flag and random numbers, offset by some small error, and then modulo a small prime. You are given the random numbers used for free, but the errors are secret.

The primes are generated in a truly bizarre way:

mark = 3**66
def get_random_prime():
  total = 0
  for i in range(5):
    total += mark**i * getRandomNBitInteger(32)
  fac = str(factor(total)).split(" * ")
  return int(fac[-1])

It generates a number that has "small" digits in base-\(3^{66}\) and returns the largest prime in the factorization of this number. That's one of the oddest ways to generate primes I've seen.

But (the "a-ha" moment) it means that \(n*x\) also has "small" digits in base-\(3^{66}\) for some \(x\) which is itself also "small" (compared to \(n\)).

I used a lattice like

[   n * HH, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[   1 * HH, HL, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[B**1 * HH, 0, HL, 0, 0, 0, 0, 0, 0, 0, 0],
[B**2 * HH, 0, 0, HL, 0, 0, 0, 0, 0, 0, 0],
[B**3 * HH, 0, 0, 0, HL, 0, 0, 0, 0, 0, 0],
[B**4 * HH, 0, 0, 0, 0, HL, 0, 0, 0, 0, 0],
[B**5 * HH, 0, 0, 0, 0, 0, HL, 0, 0, 0, 0],
[B**6 * HH, 0, 0, 0, 0, 0, 0, HL, 0, 0, 0],
[B**7 * HH, 0, 0, 0, 0, 0, 0, 0, HL, 0, 0],
[B**8 * HH, 0, 0, 0, 0, 0, 0, 0, 0, HL, 0],

to find \(x\). There might be better ways, but it worked. Now to factor. Trivially you can find the first and last digits of the primes. There's probably some more clever way to do the whole thing, but I just did the dumb thing and used the base-\(B\) digits of \(n*x\) as coefficients for a polynomial over \(\mathbb{Z}_p\) for some large \(p\) and factored that. That gave me two numbers back (when multiplied so the least/most significant digits match), each of which shared one of the big primes with \(n\). This was all a bit rushed because it took me too long to discover the "trick" of finding \(n \cdot x\) and I just did everything in the REPL at this point, using my own utility libraries and NTL wrapper.

So now I had \(n=p*q\) and could decrypt the vector to get a big system of linear relations with "small errors" modulo some small prime. The lattice is life, the lattice is love. Maybe there's a more clever way to solve this as well, but did I mention I was a little pressed for time at this point? The system in its entirely was too big for my poor, slow LLL, but a small random subset of equations worked just fine (every equation involved the entire flag).

I "solved" this task but was a little too late. I had already realized the solution by the last hour or two, but underestimated how many datasets I needed and wasted some time with self-doubt, double-checking, and massaging uncooperative lattices. When the competition ended I went to eat and by the time I got back there was enough data and I got the (bittersweet) flag easily.

Like FlagBot it's a deceptively clean and simple task, where you don't realize the problem until that sweet "a-ha!" moment. The server uses generated DSA constants (a (huge) prime \(p\), a generator \(g\) for a large prime (\(q\)) subgroup of \(\mathbb{Z}_p\)) to prove that it knows \(x\) in \(y=g^x \pmod p\) by giving you \(y\), \(t=y^v \pmod p\) (for some secret ephemeral key \(v\)) and \(r = v - c \cdot x \pmod q\) with \(c\) being a SHA256 constant the recepient can derive from \((g, y, t)\). It looks respectable and above the board at first glance…

But basically you need to forget everything I just said and ignore the whole business with \(p\) and discrete logs. With \(r\) you're given a system of inequalities like \(c_i \cdot flag + r_i < flag \pmod{q_i}\), because the ephemeral key is erroneously generated to be less than \(x\) which was asserted to be 247 bits in the code (while \(q\) is 256 bits), so each equation ought to reveal a little bit more about \(x\). It is clearly another lattice problem.

I'm not sure if there are any better or more clever ways to set up the lattice, but what worked for me in the end was the most obvious and straightforward:

[[1,     0, c0, c1, ...,  cn],
 [0, 2^248, r0, r2, ...,  rn],
 [0,     0, q0,  0, ...,   0]
 [0,     0,  0, q1, ...,   0]
 [0,     0,  0,  0, ...,  qn]]

b'n1ctf{S0me_kn0wl3dg3_is_leak3d}' Since I can no longer enter it on the site, I'll leave it here to be sad and alone. :(