Google CTF 2017 Quals - RSA CTF Challenge writeup

"Somebody used PKCS1v1.5 really insecurely. Can you exploit this?"

Just a screenshot

Following the link (, we find a simple form asking us to submit a signature for the challenge text (which is actually just challenge). Viewing the source reveals some interesting snippets:

<!-- TODO: How can we make sure this is PKCS1v1.5/MD5? Also, we need to validate that it's base64. -->
    Paste your signature here: <input id="pwd" type="text" value="" /><br/>
<!-- TODO: remove -->
<div id="adminPubKey" style="visibility:hidden">


Also, it appears that the form sends a POST request with the signature to the /check endpoint to get the flag:

$("#post").submit(function(event) {
  var request = JSON.stringify({"Signature": $('#pwd').val()});

  $.post("/check", request,
    function(data) {
      var result = JSON.parse(data);
      if(result.CheckSucceeded) {
        $("#result").empty().append("Succeeded. Flag is: <kbd>" + result.Flag + "</kbd>");
      } else {
      function(response) {
        console.log('Error: ' + response.responseText);

The page confusingly requests to sign the challenge with a public key, but it's likely just a typo. From what the source says, the server expects a signed MD5 hash with PKCS#1 v1.5 padding, encoded in Base64. We also should check out that admin key, for example, saving it to a file and using the pycrypto library:

from Crypto.PublicKey import RSA
from Crypto.Util.number import size

key = RSA.importKey(open('admin.key').read())
print "N = %s" % key.n
print "e = %s" % key.e
print "N size is %s bits" % size(key.n)
(ctf)$ python
N = 151412633855954843819733434464125339052568898102931536911637903559841544558723973043050816338485284590514808104500875340749604123632852946469150713976173372290733260940828083371874628381129699367481235628443486831633794198594140144657045371665601505687547633943899965976948544127536969540495613484548832768341
e = 3
N size is 1024 bits

Signing a message with RSA works like this: the message is hashed, the resulting hash is padded to the modulus size, following some kind of a padding scheme, then raised to the power of the private exponent d (modulo N) and passed to the other party for verification. The verification, then, consists of raising the signature to the power of the public exponent e modulo N, basically reversing it to the padded hash state, and checking the result. The hash here is MD5, and the padding (PKCS#1 v1.5) involves encoding the hash with ASN.1 and prepending it with the bytes 00 01 FF .. FF 00, with as many FF bytes as needed to get it to, in our case, 1024 bits, or 128 bytes.

RSA PKCS#1 v1.5/MD5 signature

But how would we go about signing the message without a private key?

Well, it turns out that as long as e is very small (and it is for us, 3 being one of the most popular sizes), and the PKCS#1 v1.5 implemenation of the verifying party is not entirely accurate, we could do exactly that. In 2006, Daniel Bleichenbacher described a method of forging RSA signatures when e equals 3, exploiting the fact that most implementations did not check that the padded message actually ended after the ASN.1/hash block; that is, when supplied with a fake signature which after the exponentiation - cubing, here - would form a correctly left-padded block, they would ignore everything else and accept it.

Bleichenbacher 2006 attack

While Bleichenbacher demonstrated this with a 3072 bit key, further research followed, resulting in successful forging of 1024-bit signatures of MD5 and SHA-1 hashes; but the catch is, the paper assumes some control over the source message (they forge X.509 certificates, so the hash could be easily manipulated by bruteforcing, say, the expiration date value), and we have none. So when it comes to the requirement that there should be no less than 8 FF bytes of padding, we fail at finding a good cube root:

from Crypto.Signature import PKCS1_v1_5
from Crypto.Hash import MD5
from Crypto.Util.number import bytes_to_long, long_to_bytes, size

def true_cbrt(n):
    lo = 0
    hi = n
    while lo < hi:
        mid = (lo+hi)//2
        if mid**3 < n:
            lo = mid+1
            hi = mid
    return lo

h ="challenge")
print "MD5 of challenge: %s" % h.hexdigest()

padded = PKCS1_v1_5.EMSA_PKCS1_V1_5_ENCODE(h, 1024/8)

print "Real message:"
print padded.encode('hex')

asn1hash = padded.split("\xff\xff\xff\x00")[-1]
forged_prefix = "\x00\x01" + "\xff"*8 + "\x00"
forged = (forged_prefix + asn1hash).ljust(128, "\xff")

print "Desired forged message:"
print forged.encode('hex')

sig = true_cbrt(bytes_to_long(forged))
print "Closest forged message 1:"
print long_to_bytes(sig ** 3).rjust(128, "\x00").encode('hex')

sig -= 1
print "Closest forged message 2:"
print long_to_bytes(sig ** 3).rjust(128, "\x00").encode('hex')
(ctf)$ python
MD5 of challenge: b04ec0ade3d49b4a079f0e207d5e2821

Real message:

Desired forged message:

Closest forged message 1:

Closest forged message 2:

As you can see, we narrowly miss our target here; it rests in between of our messages differing by 1, so we can't do much more without reducing the number of FF bytes to six or less (which doesn't work, too). So, maybe there could be something else wrong with the implementation?

As a matter of fact, indeed there could be. In 2016, Filippo Valsorda (@FiloSottile) wrote this article on the issue in python-rsa (later assigned CVE-2016-1494) - in short, while the part of the message following the hash wasn't ignored, the bug allowed using any kind of byte being used instead of the FF padding as long as it wasn't a zero.

Of course, the beginning of the message in that case could be simply 00 01 with no regard to the following bytes up to the very end, where the 34 bytes of the ASN.1 encoded MD5 hash would reside. So we could search for a value resulting in those 34 bytes when cubed (Filippo offers a simple algorithm for that, provided the hash value we need is odd - and luckily it is), and then combine it with a simple cube root for the prefix.

Filippo Valsorda 2016 rsa-crypto attack

The only catch here is that we should check for null bytes in the padding output so it would still appear valid. Let's do this just as lazily as Filippo did:

import os
import asn1
import requests
import base64
from Crypto.Signature import PKCS1_v1_5
from Crypto.Hash import MD5
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes, size

def true_cbrt(n):
    lo = 0
    hi = n
    while lo < hi:
        mid = (lo+hi)//2
        if mid**3 < n:
            lo = mid+1
            hi = mid
    return lo

def get_bit(n, pos):
    return (1 if (n & (1 << pos)) else 0)

message = "challenge"

key = RSA.importKey(open('adminpub.key').read())
h =
padded = PKCS1_v1_5.EMSA_PKCS1_V1_5_ENCODE(h, size(key.n)/8)

asn1hash = "\x00" + padded.split("\xff\xff\xff\x00")[-1]

asn1hash_l = bytes_to_long(asn1hash)

# find the value resulting in ASN.1 + hash suffix when cubed
sig_suffix = 1
for bit_pos in range(len(asn1hash) * 8):
    if get_bit(sig_suffix ** 3, bit_pos) != get_bit(asn1hash_l, bit_pos):
        sig_suffix ^= (1 << bit_pos) # flip the incorrect bit

if not long_to_bytes(sig_suffix ** 3).endswith(asn1hash):

print "Signature suffix found"

# combine the cube roots checking for null bytes
while True:
    prefix = bytes_to_long("\x00\x01" + os.urandom(1024/8 - 2))
    sig_prefix = long_to_bytes(true_cbrt(prefix))[:-len(asn1hash)]
    sig = sig_prefix + long_to_bytes(sig_suffix)
    if "\x00" not in long_to_bytes(bytes_to_long(sig) ** 3)[:-len(asn1hash)]:

print "Full signature obtained"

print "Resulting padded message:"
print long_to_bytes(bytes_to_long(sig) ** 3).encode('hex')

sig = sig.rjust(128, "\x00")
sig = base64.b64encode(sig)
r ="", json={"Signature":sig})
print r.text
(ctf)$ python 
Signature suffix found

Full signature obtained

Resulting padded message:

{"CheckSucceeded" : 1, "Flag" : "CTF{zx2fn265ll7}"}

And that's our flag right there!