# GoogleCTF 2017: RSA CTF Challenge

Jul 02, 2017We are first presented with a simple HTML form that asks us to sign the word `challenge`

in order to login. If we look at the source of the page, we find a hidden div that includes an RSA public key and references to base64 encoding and PKCS1v1.5 / MD5. Our goal then seems to be to forge a signature for `challenge`

in PKCS1v1.5 format that will be accepted by the given public key.

If done properly, this is impossible, but because PKCS1v1.5 is such a brittle scheme, minor errors in its implementation can result in major security vulnerabilities.

## PKCS1v1.5

Before we talk about the implementation error, let’s first describe how PKCS1v1.5 works.

A PKCS1v1.5 block looks like this:

`00 || BT || PS || 00 || D`

where:

`BT`

is the block type and is 01 for private key operations (digital signatures) and 02 for public key operations (encryption)`PS`

is the padding string and consists of \( k - 3 - D \) bytes where \( k \) is the byte-length of the RSA modulus. For block type 01, the padding bytes should all be FF and for block type 02, the padding bytes should be “pseudorandomly generated and nonzero.”`D`

is the actual data in question.

For digital signatures `D`

is an ASN.1 encoded value that includes information about the hash function used and the hash of the message to be signed. For our purposes,

`D = 3020300c06082a864886f70d020505000410 || MD5('challenge')`

To create an RSA signature, we construct a PKCS1v1.5 block of the above format, treat it as an integer \( c \), and compute \( m = c^d \ (\mathrm{mod} \ n) \). The result \( m \) is our signature.

## The Vulnerability

We aren’t given the source code for the signature validator, so we must do some guesswork on the implementation error. The HTML form makes a reference to “End-to-End Encryption” even though the challenge involves signatures, not encryption.

Perhaps it’s possible that the website builders confused RSA Encryption with RSA Signatures and used the wrong type of PKCS1v1.5 padding. Specifically, instead of checking that the padding string consisted of only FF bytes, maybe they treated it as if it was block type 02 and just checked that it had only nonzero bytes.

How can we take advantage of this? On it’s own this doesn’t help us, but when combined with the fact that the RSA public exponent is very small (\( e = 3 \)), it becomes relatively straightforward to forge valid signatures.

If we can craft a padding string such that the resulting PKCS1v1.5 block is a perfect cube, we can simply take the cube root of it and use it as our signature \( m \). Then, the validator will compute \( m^e \ (\mathrm{mod} \ n) = m^3 \), and the result will be our crafted block.

## The Attack

We need to find a 1024-bit perfect cube with leading bytes `00 01`

and trailing bytes equal to `00 || D`

. The attack is outlined in this Stack Exchange post; we’ll have to modify it slightly for this challenge.

Let’s start with the trailing bytes condition. `00 || D`

is \( 1 + 18 + 16 = 35 \) bytes \( = 280 \) bits long, so this condition is equivalent to saying that that our cube modulo \( 2^{280} \) should equal D. Let’s call our cube \( x^3 \) and let’s represent D as the variable \( d \).

We want:

\[ x^3 = d \ (\mathrm{mod} \ 2^{280}) \]

Elementary number theory tells us that if \( v \) is the inverse of \( 3 \) modulo \( \phi(2^{280}) \), Then

\[ x = d^v \ (\mathrm{mod} \ 2^{280}) \]

(This only works if \( d \) has a modular cube root, which is true only for odd \( d \). Happily, our \( d \) is odd.)

Next, let’s consider the leading bytes condition. This can be formulated mathematically as \[ 2^{1008} \le x^3 < 2 \cdot 2^{1008} \]

\[ \sqrt[3]{2^{1008}} \le x < \sqrt[3]{2 \cdot 2^{1008}} \]

(The \( 1008 \) comes from the fact that length of the padding plus the trailing bytes is \( 1024 - 2 \cdot 8 = 1008 \) bits).

So to finish, we just need to find an \( x \) that satisfies both of these mathematical conditions. We can do this by picking any \( x \) in the interval, and adjusting it slightly so that it equals \( d^v \) modulo \( 2^{280} \). The resulting number’s cube should have the appropriate leading and trailing bytes.

There’s actually one more condition that we’ve ignored so far: the padding string shouldn’t contain any null bytes. This will happen by chance with probability \( (255/256)^{91} \approx 70\% \) so we can just try a bunch of candidates until one works.

## The code

You can find a simple python script to compute the signature here. The key section is reproduced below:

The script produces the integer

```
x = 176368846691323817807583646497896249461582346736585043753352378054480534894624774082565108943018895713
```

which, when converted to a byte string and base64 encoded is:

```
AUKKL5jXKK3upjPt+nUNI8iXdZSASpmMLeHoAi4zdZ3XEyfjVk0NxdGpYQ==
```

Submitting this signature to the website yields the flag `CTF{zx2fn265117}`

.