Dobbertin Challenge 2012

The Dobbertin Challenge is issued every two years since 2006, in honor and memory of Prof. Hans Dobbertin.

http://cryptochallenge.nds.rub.de:50080/

A simple JSON Web Service is provided, which processes PIN codes of users. A user can send his encrypted PIN to the Web Service, which decrypts and stores the PIN. The Web Service allows to use cryptographically strong algorithms (RSA-OAEP and AES in GCM-mode) as well as algorithms with known weaknesses (RSA-PKCS#1 v1.5 and AES in CBC-mode). To create a ciphertext, a sender may choose among these algorithms.

In order to protect the confidentiality of PINs, encryption based on the JSON Web Encryption standard (link) is used. This standard allows to apply symmetric and asymmetric encryption algorithms.

You are the attacker who wants to learn the secret PIN of user Bob. You have already eavesdropped a ciphertext which contains Bob’s PIN:
eyJhbGciOiJSU0FfT0FFUCIsIml2IjoieXY2NnZ2ck8yNjNleXZpSSIsInR5cCI6IkpXVCIsImVuYyI6IkExMjhHQ00ifQ==.
ZBnPlwONWHxGDrtCxxopS4y4SrMZIAhUg3HI+SbLMxfPVRPW8yunejrkmfSLO1H/0tOx4ssggygHjG7sUfxL8A==.
i2vygn2vqFpsmep3etrD5Yh5xLP9xYhJdvn63WmHEPYChA==.

Server Certificate

Summary: RSA-PKCS#1 v1.5 and AES-CBC padding oracles attacks

Intro

Let’s look into the protocol. We are given an example:

POST /service HTTP/1.1
Content-Length: 217
Content-Type: text/plain; charset=ISO-8859-1
Host: cryptochallenge.nds.rub.de:50080
Connection: Keep-Alive
User-Agent: Apache-HttpClient/4.2.1 (java 1.5)

eyJhbGciOiJSU0FfT0FFUCIsIml2IjoieXY2NnZ2ck8yNjNleXZpSSIsInR5cCI6IkpXVCIsImVuYyI6IkExMjhHQ00ifQ==.
ZBnPlwONWHxGDrtCxxopS4y4SrMZIAhUg3HI+SbLMxfPVRPW8yunejrkmfSLO1H/0tOx4ssggygHjG7sUfxL8A==.
i2vygn2vqFpsmep3etrD5Yh5xLP9xYhJdvn63WmHEPYChA==.

HTTP/1.1 200 OK
Content-length: 24
Date: Fri, 12 Oct 2012 08:04:48 GMT

Data successfully stored

We know that three parameters are sent: choice of algorithms, asymmetric ciphertext and symmetric ciphertext. Let’s look at the choice of algorithms:

"eyJhbGciOiJSU0FfT0FFUCIsIml2IjoieXY2NnZ2ck8yNjNleXZpSSIsInR5cCI6IkpXVCIsImVuYyI6IkExMjhHQ00ifQ==".decode("base64")
{"alg":"RSA_OAEP","iv":"yv66vvrO263eyviI","typ":"JWT","enc":"A128GCM"}

Oh, it’s encrypted using “strong” schemes. Let’s look how the service reacts on invalid ciphertexts:

If we send the same data, but with some randomly changed byte in asymmetric part, we get:

Couldn’t decrypt: data hash wrong

And for changed byte for symmetric part:

Couldn’t decrypt: mac check in GCM failed

Yeah, they should be wrong. The probability of fooling these schemes is really very small.
But we also have “bad” schemes (RSA-PKCSv1.5 and AES-CBC). Let’s fuzz them:

Asymmetric way

{"alg":"RSA1_5","iv":"yv66vvrO263eyviI","typ":"JWT","enc":"A128GCM"}
# + original ciphertexts result in this error:
 
Couldn't decrypt: Blocktype mismatch: -110'

We see a padding error for RSA (it’s not an AES-GCM error because it would be “mac check in GCM failed”).
So we have a padding oracle for RSA PKCS v1.5 padding, which is known to be insecure.
It can be broken with the Bleichenbacher’s attack (very good article on this).
Also, the error text: “Blocktype mismatch: -110” gives us much more information than simple yes/no padding oracle (that text means that the second byte, which is blocktype and must be “\x02” for valid padding is equal to -110 (“\x92”)).
Thus, we can obtain the secret message much faster.

Some notes about attack:

• The method is based on fact that you know the possible range for secret message (which is derived from padding format)
• Then, you check padding for different multipliers: enc(s * m). This is possible due to RSA multiplicativity:

  pow(m * s, e, n) = pow(m, e, n) * pow(s, e, n) = c * pow(s, e, n)

  pow(m * s, e, n) = pow(m, e, n) * pow(s, e, n) = c * pow(s, e, n)

• When we get some blocktype error, we know a range for

  m1 = s * m (mod n)

  m1 = s * m (mod n)

• From this ranges we can narrow down the range for the secret message
• Also, given some blocktype error, we can shift it left (multiply by 2) while the highest byte is zero and learn some lower bits
• A good thing is that even if the secret message is not padded correctly for PKCS v1.5, we can find some multipler s for which the padding is ok, and decrypt it first. And then simply multiply the decryption by invmod(s, n)

Scripts for this attack.

Run the script and get in ~5 minutes:

...
Bleichenbacher attack finished with 915 oracle requests
PLAINTEXT: {"My PIN:":"5983"}

A symmetric way

Now let’s look into symmetric crypto:

{"alg":"RSA_OAEP","iv":"yv66vvrO263eyviI","typ":"JWT","enc":"A128CBC"}
# + original ciphertexts result in this error:
 
Couldn't decrypt: initialisation vector must be the same length as block size'
 
# fix IV
{"alg":"RSA_OAEP","iv":"yv66vvrO263eyviIAAAAAA","typ":"JWT","enc":"A128CBC"}
# + original ciphertexts result in this error:
 
Couldn't decrypt: last block incomplete in decryption'
 
# oh and 16 byte blocks for symmetric CT
{"alg":"RSA_OAEP","iv":"yv66vvrO263eyviIAAAAAA","typ":"JWT","enc":"A128CBC"}
# with random 32-byte ciphertext
 
Couldn't decrypt: pad block corrupted'

The same: we have a padding oracle for AES-CBC mode.
How can we use it to decrypt the secret message?
Since we don’t have a ciphertext for simple AES, we can’t apply the classic padding oracle attack.

GCM mode itself is CTR mode + MAC tag. That means we know

AES(Nonce || Counter) ^ MessageBlock

Nonce is “iv” that was sent in params dict for the secret message: "yv66vvrO263eyviI".decode("base-64").
Counter is also known (it starts from 2: counter=1 is used by GCM-MAC).

We know a pattern for the message and there are only 10000 possible pins – so we can make a guess for MessageBlock and thus for AES(Nonce || Counter).

• If our guess is correct, the message will be decrypted to (Nonce || Counter) ^ IV and checked for valid padding.
• If it’s not – the message will be random and most probably the padding will be wrong.

To take advantage of this, we can manipulate IV to make a valid padding. An easy way to do this is to set IV = Counter ^ "\x00\x00\x00\x01" – so the message will end with Counter ^ Counter ^ "\x00\x00\x00\x01" = "\x00\x00\x00\x01", which is considered a valid padding.

Here’s a script for this attack:

algo_choice, rsa, aes = split(data)
block1 = aes[:16]
counter = 2
msg_pattern = '{"My PIN:":"%04d' # 16 bytes
 
for pin in xrange(10000):
    msg = msg_pattern % pin
 
    iv = "yv66vvrO263eyviI".decode("base64").rstrip()
    iv += pack(">I", counter ^ 1)
 
    algo_choice = '{"alg":"RSA-OAEP","iv":"%s","typ":"JWT","enc":"A128CBC"}' % \
                                      iv.encode("base64").rstrip(" \n=")
    aes = xor(block1, msg)
 
    r = requests.post(url, data=join(algo_choice, rsa, aes))
    if "pad block corrupted" not in r.content:
        print "\nGOOD PIN", pin
    else:
        write(".")
        flush()

This is quite simple, but we’ll get a lot of false positives: random padding with probability higher than 1/256 will be valid. Indeed, within first 1000 pins there are 8 false pins:

GOOD PIN 120
GOOD PIN 128
GOOD PIN 276
GOOD PIN 290
GOOD PIN 392
GOOD PIN 770
GOOD PIN 963
GOOD PIN 984
...

To avoid this, we can test “good” pins with another valid padding: “\x02\x02” instead of “\x00\x01”:

Full script

for pin in xrange(10000):
    msg = msg_pattern % pin
 
    for pad in (0x1, 0x202, 0x30303):
        iv = "yv66vvrO263eyviI".decode("base64").rstrip()
        iv += pack(">I", counter ^ pad)
 
        algo_choice = '{"alg":"RSA-OAEP","iv":"%s","typ":"JWT","enc":"A128CBC"}' % iv.encode("base64").rstrip(" \n=")
        aes = xor(block1, msg)
 
        r = requests.post(url, data=join(algo_choice, rsa, aes))
        if "pad block corrupted" in r.content:
            break
 
        print "PIN %04d PASSED %08x PAD" % (pin, pad)

Run this and after ~25 (~45 minutes all pins) minutes we’ll get the right answer:

...
PIN 5983 PASSED 00000001 PAD
PIN 5983 PASSED 00000202 PAD
PIN 5983 PASSED 00030303 PAD
...

And 41 false positive for 00000001 pad.