CSAW CTF Finals 2019

It’s been more than a week since CSAW (I know I’m late with this post), and even though I’ve been busy with school, I decided to make a few writeups. In general, things went well! We were the first team to max the crypto, including first bloods on the two highest-value challenges. I also first-blooded the Smash challenge 😎

The heartbreaking part came towards the end, when we dropped to fourth place. Our only hope was the Yeet Wars challenge, which awarded points at the end of the CTF. PPP was set to receive 100 points, and we calculated that this put them 25 ahead of us. Coincidentally, there were also two challenges worth 25 points: Smash, which I had already done, and Chess. If we solved Chess, then we would actually win the tiebreaker by earning the points first.

So we played chess for an hour. We never won. :(

It turns out that PPP hoarded solved a four hundred point challenge in the last three minutes, so none of this mattered anyways. We ended up placing fourth as expected, but I’m satisfied for my first year. I’d like to thank the organizers for another successful CSAW, and I’ll try to be back next year!

macrypto

This challenge involves a Rust program slightly obfuscated with macros. Fortunately, while Rust macros can be very powerful, we can just think of these as inlined functions.

I’m not going to detail the deobfuscation since that would take too long, but the general idea is that the program reads in a plaintext, appends the flag, and encrypts the result using a stream cipher (RC4, but I didn’t realize it at the time).

Although most of the macros were straightforward, one thing I did find strange was the s! macro.

macro_rules! s { ($x:expr, $y:expr) => { $x ^= $y; $y ^= $x; $x ^= $y; }}

It’s not entirely clear what s! does at first glance, but it turns out to perform a swap. I thought this was pretty neat, since it avoids allocating space for a temporary variable. The stream cipher uses this swap to update the state array a, which determines the key byte at each stream position.

for b in m.iter() {
  let mut k: T = 0;
  i = a!(i, 1); j = a!(j, a[u!(i)]);
  s!(a[u!(i)], a[u!(j)]);
  k = a!(a[u!(i)], a[u!(j)]);
  c.push(b ^ a[u!(k)]);
}

This seems fine, but what if a[i] and a[j] point to the same value in memory? The swap actually breaks down! In particular, on the off chance that i equals j, the element at that position becomes zero. Over time, as a becomes more populated with zeros, the keystream grows more biased towards null bytes. I found that after around two hundred thousand iterations, the keystream was reliably null. Sure enough, sending that many bytes to the server works!

ezpz

We’re given the source for a server that uses elliptic curve cryptography to perform a number of tasks:

• Sign points on the curve
• Encrypt short messages
• Encrypt the flag

There’s an obvious bug in the signing code that lets us specify the coefficients of a new curve to sign over. Using this, we can force the server to use insecure curves and leak the private key.

coeffs, x, y = json.loads(d)
curve = EllipticCurve(GF(self.p), coeffs)
point = self.priv * curve((x,y))
return json.dumps([int(i) for i in point])

Every team I know of, including us, used this line of attack during the CTF. However, I want to talk about a much simpler solution that I only realized afterwards. I’ve talked to the challenge organizer and confirmed that the solution below is unintended.

To encrypt the flag, the server first maps its bytes to the x-coordinate of a point M on the elliptic curve. Then, it computes the ciphertext U, V = kP, kQ + M, where P is the base point and Q is the public key.

msg = Integer(msg.encode('hex'), 16)
k = random_prime(self.p)
c = self.P * k
cp = self.pub * k
pm = self.E.lift_x(msg)
return json.dumps([[int(i) for i in c], [int(i) for i in (cp + pm)]])

Decrypting the ciphertext requires computing M = V - dU, where d is the private key. This works because dU == dkP == kdP == kQ.

We can’t directly decrypt the flag, since we don’t know d. However, remember that the server also includes functionality for signing points, which is done by multiplying the point by d.

So let’s sign U! We receive dU from the server, which we can then use to decrypt the flag. Throughout the entire process, we did not recover d. Instead, we used the server as an oracle to perform the only operation we needed d for.