# H4CK1NG G00GL3 - Ep 005 Ch 002: Project Zero Adventure

###### Bleichenbacher strikes back again (and again).

HACKING GOOGLE is a documentary of Google’s cybersecurity teams and H4CK1NG G00GL3 is it’s CTF counterpart. *Project Zero Adventure* is a cryptography challenge I wrote.

In the game, the players control the Security Princess to dodge the obstacles and catch the bugs (a variant of Google Chrome’s dinosaur game). After that, the server will sign messages consisting of the players' name and the score via the `/sign`

API. The players will then submit it to the `/highscore`

API. If the score submitted to the highscore API is negative, they will be given the flag.

However, there is one catch: The server is only willing to sign the results with non-negative scores.

## Challenge Summary⌗

It is given that the server signs messages using a RSA key with a 2048-bit public modulus $n$ and $e = 3$. The messages are signed with PKCS#1 v1.5. The `verify`

method below is how a signature `s`

, correspond to the message `m`

, is being verified. The goal is to forge a signature for messages indicating that the player has a negative score (one example of the message being `["pzero-adventures", "MYZ", -1]`

).

```
class VerifyingKey:
def __init__(self, n, e, bits=2048):
self.n = n
self.e = e
self.bits = bits
# https://datatracker.ietf.org/doc/html/rfc2313#section-10.2
# Note: The only hash algorithm we accept is SHA256.
def verify(self, m, s):
if len(s) != self.bits//8:
raise Exception('incorrect signature length')
s = int.from_bytes(s, 'big')
k = pow(s, self.e, self.n)
k = int.to_bytes(k, self.bits//8, 'big')
if k[0] != 0x00:
raise Exception('incorrect prefix')
if k[1] != 0x01:
raise Exception('incorrect prefix')
padding, digest_info = k[2:].split(b'\x00', 1)
if len(padding) < 8:
raise Exception('invalid padding length')
if padding != b'\xff'*len(padding):
raise Exception('invalid padding content')
sequence = DerSequence()
sequence.decode(digest_info)
_digest_algorithm_identifier, _digest = sequence
sequence = DerSequence()
sequence.decode(_digest_algorithm_identifier)
_digest_algorithm_identifier = sequence[0]
object_id = DerObjectId()
object_id.decode(_digest_algorithm_identifier)
digest_algorithm_identifier = object_id.value
if digest_algorithm_identifier != '2.16.840.1.101.3.4.2.1':
raise Exception('invalid digest algorithm identifier')
_null = sequence[1]
null = DerNull()
null.decode(_null)
octet_string = DerOctetString()
octet_string.decode(_digest)
digest = octet_string.payload
if hashlib.sha256(m).digest() != digest:
raise Exception('mismatch digest')
return True
```

## Solution⌗

**Alternative Writeups (which are usually better).**Of course you would like to read the solutions from our players and our fellow Googlers! Writeup by

*@44670*, writeup by

*@Dvd848*, writeup by

*@dguerri*and writeup by

*@paulsc*.

**Fast forward?**If you are interested

*only*in the solution, you can start reading from part III. I will begin with a literature review.

### Part I: How PKCS#1 v1.5 signature scheme works?⌗

It is well-known that RSA sign messages by “decrypting” them. Assuming that the RSA key is of 256 bytes, the PKCS#1 v1.5 payload to be signed is given below:

Suppose that `DATA`

is of length $l$. According to RFC 2313, `PADDING`

consists of $253 - l$ bytes which are all `0xFF`

. Also, the data are encoded using *Distinguished Encoding Rules (DER)*. Below is an example of DER-encoded data indicating that:

- the hash algorithm being SHA-256, and
- the digest being
`0424974c68530290458c8d58674e2637f65abc127057957d7b3acbd24c208f93`

.

```
βββ¬ 30 31 Sequence type (length 0x31)
βββ¬ 30 0d Sequence type (length 0x0D)
β βββ¬ 06 09 Object identifier type (length 0x09)
β β βββ 608648016503040201 Object identifier content (decoded
β β 2.16.840.1.101.3.4.2.1, SHA-256's OID)
β βββ 05 00 Null type (length 0x00)
βββ¬ 04 20 Octet string type (length 0x20)
βββ 0424974c68530290458c8d58674e2637 Octet string content
f65abc127057957d7b3acbd24c208f93
```

Let $m$ denote the PKCS#1 v1.5 payload. Then the signature is given by $s = m^d \ \text{mod}\ n$.

### Part II: Bleichenbacher’s signature forgery attack in 2006⌗

In 2006, Bleichenbacher shared on CRYPTO'06 (Hal Finney’s summary) a way to easily forge RSA signatures when $e$ is small and the verify function is poorly implemented.

Suppose that the signature is validated by unpadding, retrieving `ALGORITHM`

and `DIGEST`

from `DATA`

and discarding remaining bytes. This is an ideal message:

However, as long as the `ALGORITHM`

and `DIGEST`

are correct, messages in the below format are considered valid as well:

Yes – this is not properly validated. This is disastrous, why?

Let $e = 3$ and suppose we want to forge a signature for a message with its SHA-256 digest being `0424974c68530290458c8d58674e2637f65abc127057957d7b3acbd24c208f93`

.

Equivalently, we want to find $s$ with $s^3 \equiv m\ (\text{mod}\ n)$. Hereby $m$ begins with $m_0$ (which is 61 bytes long) below, i.e., $m = {256}^{195} m_0 + x$ for some “garbage” $x \in [0, {256}^{195})$.

```
m0 = 0x00 01 ffffffffffffffff 30 31 30 3d 06 09 608648016503040201 50 00 04 20 0424974c68530290458c8d58674e2637f65abc127057957d7b3acbd24c208f93
[PADDING ] [DATA ]
[ALGORITHM ] [DIGEST ]
```

It is difficult to work on modulo arithmetic, so let’s lift the modulo away and look for $s$ such that $s^3 = m = {256}^{165} m_0 + x$. It is easy to find a $s$ such that

$${256}^{165} m_0 \leq s^3 < {256}^{165} (m_0 + 1).$$

In short, any of the integer between $\sqrt[3]{{256}^{165} m_0}$ and $\sqrt[3]{{265}^{165} (m_0 + 1)}$ would fit – and that is basically Bleichenbacher’s attack in 2006.

### Part III: …and it constantly strikes back⌗

It is still hard to validate PKCS#1 v1.5 signatures properly after a decade.

In 2016, *Filippo Valsorda* (@filosottile) wrote a blog post on a flaw on such message being validated. In short, it is the `PADDING`

which is not properly validated. You can read the source code of the vulnerable function here.

This is not the end. In 2019, Sze Yiu Chau shared on Black Hat USA that the PKCS#1 v1.5 signatures are *still* not validated correctly (video and white paper here). This yields six CVEs to their research team from various TLS and IPSec libraries.

It is slightly different from BB'06. Instead of stuffing garbage as the suffix, we are putting random bytes in the middle. Mathematically, we are looking for $x$ with

$$s^3 = m = 256^{l_1} \cdot \text{prefix} + 256^{l_2} \cdot x + \text{suffix}$$

for a given $\text{prefix}$, $\text{suffix}$, $l_1$ and $l_2$.

This is harder than stuffing garbage at the very end, because we have to solve the below inequalities and congruences at the same time:

- $256^{l_1} \cdot \text{prefix} \leq s^3 < 256^{l_1} \cdot (\text{prefix} + 1)$, and
- $s^3 \equiv \text{suffix}\ (\text{mod}\ 256^{l_2}).$

Fortunately this is solvable when $l_1 - l_2$ is large (we can stuff more garbage in between) and $e$ is small. Let’s leave this as an exercise to the readers.

### Part IV: …again in H4CK1NG G00GL3⌗

Now back to the challenge. The `verify`

function at the very beginning seems to be implemented correctly. But there is one problem in the following snippet:

```
class VerifyingKey:
# ...SKIPPED...
def verify(self, m, s):
# ...SKIPPED...
sequence = DerSequence()
sequence.decode(_digest_algorithm_identifier)
_digest_algorithm_identifier = sequence[0]
object_id = DerObjectId()
object_id.decode(_digest_algorithm_identifier)
digest_algorithm_identifier = object_id.value
if digest_algorithm_identifier != '2.16.840.1.101.3.4.2.1':
raise Exception('invalid digest algorithm identifier')
_null = sequence[1]
null = DerNull()
null.decode(_null)
octet_string = DerOctetString()
octet_string.decode(_digest)
digest = octet_string.payload
if hashlib.sha256(m).digest() != digest:
raise Exception('mismatch digest')
return True
```

In the snippet, it checks if

- the first item in the sequence is an
*object identifier*being SHA-256’s OID, and - the second item in the sequence (i.e., the parameter) is a
*null*object.

Unfortunately, the method did not check if the sequence has *exactly* two items. An adversary can insert garbage and pretend that being the third item in the sequence. We then can reduce this to the math problem mentioned in part III.

### Part V: …and again, unexpectedly⌗

**Unintended solution?**I was carefully enough to make one mistake, but I was

*not*carefully enough to make

*only*one mistake. This part is dedicated to

*@XMPPwocky*, who found an unintended solution and I was super surprised.

Finally, let’s patch the vulnerability. It is intuitive to check if the sequence of `ALGORITHM`

has exactly two items:

```
class VerifyingKey:
# ...SKIPPED...
def verify(self, m, s):
# ...SKIPPED...
sequence = DerSequence()
sequence.decode(digest_info)
_digest_algorithm_identifier, _digest = sequence
sequence = DerSequence()
sequence.decode(_digest_algorithm_identifier)
+ if len(sequence) != 2:
+ raise Exception('invalid sequence length')
_digest_algorithm_identifier = sequence[0]
object_id = DerObjectId()
object_id.decode(_digest_algorithm_identifier)
digest_algorithm_identifier = object_id.value
if digest_algorithm_identifier != '2.16.840.1.101.3.4.2.1':
raise Exception('invalid digest algorithm identifier')
_null = sequence[1]
null = DerNull()
null.decode(_null)
octet_string = DerOctetString()
octet_string.decode(_digest)
digest = octet_string.payload
if hashlib.sha256(m).digest() != digest:
raise Exception('mismatch digest')
return True
```

Is it sufficient? Surprisingly no. @XMPPwocky found a problem when decoding for `DerNull`

– the latest version of pycryptodome (v3.15.0) does not raise an exception if it contains a non-empty payload!

Normally, a `DerNull`

object consists of two bytes: `05 00`

. However, the below bytes are considered valid a `DerNull`

object:

```
05 27 64696420796f75206c6f6f6b20757020666f7220746865206861736820696e207061727420493f
```

We can experiment this:

```
from Crypto.Util.asn1 import DerNull
_null = bytes.fromhex('05 27 64696420796f75206c6f6f6b20757020666f7220746865206861736820696e207061727420493f')
null = DerNull()
null.decode(_null) # This does not raise an exception!
```

With that said, we can actually stuff garbage in the parameter field. Once again it became the math puzzle in part III.

I tried my best to verify everything except the intended issue while implementing. The unintended solution is definitely a lesson for me. π€© **VERY NICE CATCH!** π