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 852aab918057c30f3ca63d0c32ee43b8cec004789ef6e6f4 55f141bde90fbb0bec96583f06ea7db0948a77da4ec65f49 1456690653024c312778838e411c579f07261cd3e238fc88 36637b95d94d1eca3e1b33a061fd25683f768462c35eca44 2558c21eaa7fed42f187210ac7a"} |
Let’s look at the public key:
$ openssl rsa -in publickey -pubin -text Public-Key: (1024 bit) Modulus: 00:96:e0:7d:13:84:28:34:45:11:25:9c:59:13:6e: 9b:0a:e9:f1:44:50:1e:d1:0d:e1:76:9a:53:c8:93: e9:6b:db:a2:6b:ce:10:48:1c:e2:1f:53:30:c4:75: 43:61:57:47:9f:4e:c0:9f:45:45:08:1b:ca:6f:94: af:21:27:3c:2b:89:36:a5:f5:59:be:8f:73:9b:b9: 99:c2:d3:72:04:ec:c4:e1:c8:cb:ba:77:43:b8:99: 09:9b:71:3e:aa:96:14:ed:f8:c9:1f:d0:94:ce:61: 92:11:de:f9:39:39:e2:4e:3c:ae:01:34:c7:0b:3a: 18:d9:7b:53:e3:6c:db:3d:e5 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 = requests.post("https://spotted-wobbegong.ctfcompetition.com/checktoken", 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 = requests.post("https://spotted-wobbegong.ctfcompetition.com/checktoken", 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 wu.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 442326d2d7d5ba6b663e0feca1da42752433759e3e083729688de33c02a3e38 a59c0550895f86fe8938f9a59ae121c2431afb03b87bf86ccd4f56505438edc 1faf9f86cc72a4313a54ffad8f15f94177580dc42c1c1c227", "message": "token is invalid"} 't\xf8\x8b\xe2pC\xaf\x9f\xa14\x9b\xe9\x7f\x8c6)B\r\xf23\xb6\xf2 Q\xb8\x16HF\xcc ,\x08s\x1b\x00CTF{***What*happens*to*grapes*whe n*you*step*on*them***They*wine***}' |
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.
3 comments
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?
Author
Which attack? For Bleichenbacher there is nice article http://www.dsi.unive.it/~focardi/RSA-padding-oracle/ , for the attack from the writeup I don’t know.
I managed to get Bleichenbacher to work for this, but it definitely took a while.