Google CTF – Spotted Wobbegong (Crypto 100)

Are you able to defeat 1024-bit RSA?


Summary: breaking RSA with PCKS v1.5 padding and exponent 3.

On the web page we see the two options: get token and check token. It is also said the the message is encrypted using PCKS v1.5 padding. The tokens are randomized. An example token:

{"token": "226ef61c703ff633889a44becc24fce9ba196

Let’s look at the public key:

$ openssl rsa -in publickey -pubin -text
Public-Key: (1024 bit)
Exponent: 3 (0x3)

1024 bit modulus and the exponent is 3, suspicious!

In brief, PKCSv1.5 is a padding for RSA encryption which looks like this:

$(00)(message\ type)(random\ bytes)(00)(message)$.

The message type is usually equal to $02$.

PKCSv1.5 is known to be vulnerable to padding oracle attacks, that is what we have here. There is a writeup on Dobbertin Challenge 2012, where the Bleichenbacher attack is used to decrypt arbitrary messages. But it seems it is quite slow here, also we don’t get the message type byte from the oracle.

Let’s encrypt some correctly padded message and see the answer from the server:

import requests
from libnum import s2n, n2s, invmod
def oracle(c):
    c = "%x" % c
    if len(c) & 1:
        c = "0" + c
    data = '{"token": "%s"}' % c
    r ="", data=data, verify=False)
    return r.content
N = 105949368219170569676644297776119989261727047689020303679150543602433973822995622211997257369689976874802809991413640314155194724653004419692410129247990491389423643529600372760167148548937151460112884769720131611650468716029162594828863368194056749527587059285082313899147126415401813360799509875983663185381
E = 3
m = "\x00\x02"
m = m.ljust(95, "R") + "\x00"
m = m.ljust(128, "M")
c = s2n(m)
c = pow(s2n(m), E, N)
print oracle(c)

The answer is:

"status": "invalid",
"decoded": "4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d4d",
"message": "token is invalid"

If the padding is correct the server leaks the decoded message! We can exploit this to decrypt the token: we just need to find some multiplicatively related correctly padded message.

And that is quite easy: assume that the padded unknown message $m$ has some small factor, e.g. 17. Then we can multiply the ciphertext by modular inverse of $17^e$ and the respective message will be divided by 17. Afterwards, we can multiply it back but by slightly different value, e.g. 16 or 18. As a result, we have multiplied the message by a fraction $16/17$ or $18/17$. In such a way a few of the most significant bits won’t change. And the padding bytes 00 02 will stay correct. If we manage to get the middle 00 byte somewhere (it happens quite often by chance), then we can leak some part of the message. After multiplying it back by the inverse fraction, we will recover part of the original message.

Note that we can’t multiply by the inverse fraction modulo $N$, because we don’t leak the full value, e.g. we don’t leak the random bytes. But we can do it modulo a power of 2. And for this to be possible, both numerator and denominator of the fraction should be odd. So let’s assume we multiply by $19/17$.

Let $m = padding \cdot 2^k + s$, where $k$ is some integer and $s$ is the secret text smaller than $2^{k-8}$. If the described event happens, then

$$m \cdot \frac{19}{17} = \frac{19}{17} \cdot 2^k \cdot padding + \frac{19}{17} \cdot s = rand \cdot 2^t + s’$$.

We leak $s’$ and if we consider the equations modulo $2^t$, then we can multiply $s’$ by $17/19$ and recover $s \pmod{2^t}$.

Let’s try it! Here’s the code:

import json
import requests
from libnum import s2n, n2s, invmod
def oracle(c):
    c = "%x" % c
    if len(c) & 1:
        c = "0" + c
    data = '{"token": "%s"}' % c
    r ="", data=data, verify=False)
    return r.content
# some valid token
token = 0x876c7524d3cf53cd2169a438835c397b2b7e09b783f8b595eb75b88595dec403f10f946141f57dfdcebd330ef2f243b0b8ebbfa32958d2564fcf73768315f5e1ba73e94efd933b696e9cc30978ad73017dfc06a34ee7947cd048deea599597391794e08e43028717bf907929b9195194a2731ac6b98244a73745431398cdaf71
N = 105949368219170569676644297776119989261727047689020303679150543602433973822995622211997257369689976874802809991413640314155194724653004419692410129247990491389423643529600372760167148548937151460112884769720131611650468716029162594828863368194056749527587059285082313899147126415401813360799509875983663185381
E = 3
for d in xrange(3, 50, 2):
    c = token
    c = (c * invmod(pow(d, E, N), N)) % N
    c = (c * pow(d + 2, E, N)) % N
    res = oracle(c)
    print d, ":", res
    if "decoded" in res:
        leaked = json.loads(res)["decoded"].decode("hex")
        t = len(leaked) * 8 + 8
        mod = 2**t
        s = s2n(leaked)
        s = (s * d * invmod(d + 2, mod)) % mod
        print `n2s(s)`

Let’s run it:

$ py 
3 : {"status": "invalid", "message": "Could not decrypt token"}
5 : {"status": "invalid", "message": "Could not decrypt token"}
7 : {"status": "invalid", "message": "Could not decrypt token"}
9 : {"status": "invalid", "decoded": "be004da5a80f8a36ce85ab9be
1faf9f86cc72a4313a54ffad8f15f94177580dc42c1c1c227", "message":
"token is invalid"}
Q\xb8\x16HF\xcc ,\x08s\x1b\x00CTF{***What*happens*to*grapes*whe

Nice! We got the full flag: CTF{***What*happens*to*grapes*when*you*step*on*them***They*wine***}

PS: Note that the described attack does not use the fact the the exponent 3 is small. So maybe the authors expected another attack. Please let me know if you are aware of a suitable attack here which exploits the small exponent.


    • Giltech on May 2, 2016 at 03:02
    • Reply

    Thanks for the write up had tried the Bleichenbacher attack myself and didn’t get anywhere do you have a link to a paper or anything where this type of attack is described?

    1. Which attack? For Bleichenbacher there is nice article , for the attack from the writeup I don’t know.

  1. I managed to get Bleichenbacher to work for this, but it definitely took a while.

Leave a Reply

Your email address will not be published.