BSidesSF 2018 CTF

Learn RSA through a CTF puzzle!

I recently attended BSidesSF 2018, mainly to participate in the CTF (challenges here) with colleagues from Square. We did great overall, placing 3rd of on-site teams. I had a fun time — the event was fantastically organized, and the challenges were a blast (you should definitely attend the BSides nearest to you!).

In particular, I enjoyed the series of challenges about the RSA cryptosystem. Let’s work through the solution of part (1) together.

This article assumes you’re familiar with what RSA is and what it does, but not with how it works (because this challenge will teach you!).

Understanding the challenge

Here’s the challenge:

Realistic Steam Appliance

1) Cup validation system

Protecting the integrity of the custom-purchased cups is of utmost importance. Since the cup area is small we only have room for a small QR code which will be factory-signed. Instead of rolling our own crypto, we’ve decided to go with an unbreakable industry-standard signing algorithm using our public key:

d=0x025F2D1619EF1ABD

Our system will then scan the QR code and validate that it was properly signed by us. For our initial run of cups, we are shipping them with n=0x01A3900C7CD5B305;c=0x16464fd11c039c2 which can be validated with our private key.

P.S, Is not in FLAG: format

In order to begin solving this, we first need to know what algorithm is being used. I’ve already given away that it’s RSA, but how could we figure that out? There are two big hints:

1. The name of the challenge: Realistic Steam Appliance
2. The variable names (n, d, and c). We’ll see why in a second.

Now that we know it’s RSA, we need to figure out what the question is asking. Upfront, the challenge says that we’re validating some data with our private key. Drawing upon prior knowledge of RSA, we know that the RSA algorithm can be used for public-key encryption, or for digital signatures. In a digital signature scheme, Alice can sign a message using her private key and Bob can verify that message using her public key. So, we’re talking about RSA signing.

Given that, what’s the flag we’re looking for? Well, we have only three variables: n, d, and c. In order to understand what these mean, let’s take a look at how RSA works.

Short primer on textbook RSA

Now, let’s take a look at how textbook RSA works. The Wikipedia article does a good job of explaining it and provides a simple, worked example. Take a look if you haven’t seen how RSA works before.

Here’s my summary:

1. Pick two distinct, large primes: p and q.
2. Compute n=pq. n will be our modulus (used below). Its size in bits is the size of both keys.
3. Compute φ(n) = (p − 1)*(q − 1). See this link for what φ(n) is and why we need it.
4. Pick e, the public exponent, so that gcd(e, φ(n)) = 1 (i.e. the two are coprime, which means any prime number that divides one does not divide the other). This property ensures that a ciphertext can decrypt uniquely.
5. Compute d = e^-1 mod φ(n), which will be our private exponent. See these notes on how to compute the modular inverse.

The public key is (n, e); the private key is (n, d). So now we have our keypair.

RSA can be used for encryption and decryption:

• Encrypt a plaintext message m into ciphertext c: c = m^e mod n
• Decrypt a ciphertext c: m = c^d mod n

It can also be used to produce and verify digital signatures:

• Produce a signature for a message m: s = m^d mod n
• Verify a signature s, for m: m == s^e mod n

Note that I mentioned this is textbook RSA — this is what we call RSA as it’s explained in a textbook, but not it’s used in practice. In practice there are many flaws with textbook RSA, so we do things like apply a padding scheme, and among other things such as hashing the message before signing. There’s a lot on the internet about the insecurity of textbook RSA: see the many posts on the cryptography stack exchange (like this one). Also be aware that RSA signing isn’t actually the same thing as RSA decryption, even though in textbook RSA it is.

The solution

The security of RSA relies on two hard problems:

1. Factorizing the product of two large prime numbers. That is, given a number n=pq, there is no efficient algorithm for finding p and q.
2. Modular exponentiation is a one-way function. That is, computing c = m^e mod n is easy, but computing m from c, e, n is hard. This is known as the RSA problem.

If we can defeat (1) or (2), then we’ve broken RSA. We can assume the challenge uses textbook RSA (simply because this is a CTF), so our above description of RSA applies.

The challenge uses different notation.

• They refer to the public exponent e as d.
• They use the variable c, which is usually the ciphertext, but also mentions signatures.
• n is the modulus, same as in our definition.

Despite the differences, as long as we understand how encryption/signing work mathematically, we’ll be okay.

Our goal is to discover m from knowing n, d, and c. Let’s work through the solution.

For RSA to be secure, the modulus must be very large. For about $75 and four hours of time, you can factorize a 512 bit modulus using Amazon EC2. Here, n is far below 512 bits, which makes it way too small to be secure. To calculate the number of bits of n: log base 2 of n = 57 bits! This is trivially factorizable by using Wolfram Alpha, which gives us (p, q) = (113511859, 1040388199).

At this point we know we’ve won, since we’ve defeated requirement (1) from above. It’s a matter of working through the mechanics now. I chose to write some quick and dirty Python in order to find the flag:

The heart of the solution is in attack() . Since we have p and q, we can find φ(n). And knowing φ(n), we can compute the modular inverse to find e (which we’re calling our private exponent for this challenge). From there, we have the private key… decrypt c to find that the flag is LolzRSA. 😊

The details — Euclid’s algorithm

The main issue here is actually figuring out how to compute the modular inverse. Recall that the modular inverse is defined as (m * m^-1) ≡ 1 (mod n) or equivalently (m * m^-1) mod n = 1.

One way to do this is to apply the extended Euclidean algorithm. I’ve done this above in egcd() . This explains why the extended Euclidean algorithm finds the modular inverse, with worked examples!

Defending against the attack

In practice, this particular attack is of no concern, as long as you:

1. Use a sufficiently large modulus (at least 2048 bits in order to be more future-proof).
2. Don’t use textbook RSA. Use a library implementation with padding. For encryption, use RSA-OAEP. For signing, use RSA-PSS with SHA256.