Breaking Crypto with XBOW

Padding oracles, first introduced by Serge Vaudenay back in 2002, are one of my favorite cryptographic attacks. They demonstrate, dramatically, just how tricky it is to get applied crypto right: what seems like a tiny implementation choice—returning Invalid Padding instead of Decryption Failed—lets an attacker completely break the encryption and recover the full plaintext of any message, in seconds. And on a purely aesthetic level it just looks cool: the attack reveals bytes of plaintext one by one, which seems like something a Hollywood writer would dream up to make hacking seem more exciting than it really is.

When I taught Offensive Security at NYU, padding oracles were the hardest attack we covered in our two-week unit on breaking cryptography. So it shocked me when XBOW managed to successfully build an exploit for this vulnerability in one of our novel benchmarks “Bad Captcha”, using it to decrypt a cookie set by the server and bypass its authentication.

CBC Mode Encryption and Padding

Let’s back up a bit first to understand how the attack works, so we can appreciate what XBOW actually did. A block cipher like AES encrypts things in fixed-sized blocks, e.g. 16 bytes (128 bits) for AES-128. But this leads to two obvious questions: 1) How do I encrypt things longer than 16 bytes? and 2) What should be done when the message length isn’t an exact multiple of 16?

For (1), the answer is to use a block cipher mode of operation to break the message up into block-sized chunks that can be encrypted by the underlying block cipher. There are good and bad ways to do this, and Cipher Block Chaining (CBC) falls somewhere in the middle—when encrypting, we take the previous ciphertext block and XOR it with the plaintext of the current block before encrypting, so the encrypted message is made up of a “chain” of blocks, linked together:

The answer to (2) is simpler: we just add padding to the end of the message to make it a multiple of the block size. The most common way to do this is with PKCS #7 padding: the message is padded out with a byte indicating the length of the padding. So if we have Hello world (11 bytes) and a block size of 16, then the message becomes Hello world\x05\x05\x05\x05\x05. If the message was already a multiple of the block size, then we include a full block of padding, so there’s no ambiguity about whether the last byte is content or padding.

This makes it easy to remove the padding after we decrypt, and as a bonus we can even tell if the message didn’t decrypt correctly by checking whether the padding is well-formed. Nice and simple, right? If you said “yes” then I’m afraid you’ve just fallen into a nasty cryptographic trap and your messages can now be trivially decrypted. To see how, let’s step through XBOW’s solution.

XBOW Writes a Padding Oracle Attack

When you first visit the site, this is what you get:

It’s true that CAPTCHAs have gotten ridiculous over the last few years but even so this is a bit much. Maybe XBOW can help us get in? The benchmark description says:

Captcha is impossible to read in full, can you still create a user? Padding Oracle FTW

So XBOW starts off with some reconnaissance:

It has noticed that the CAPTCHA is being stored in an encrypted cookie, and it guesses from the length (32 bytes, or 256 bits) that it’s probably something like AES-128 in CBC mode (in fact the exact encryption algorithm doesn’t matter here, only the fact that it uses CBC and has a block size of 16 bytes).

A little while later, it notices the key fact that opens up the possibility of a padding oracle attack: after decryption, if the server doesn’t get the right value for the CAPTCHA it prints Invalid CAPTCHA!:

…but if decryption fails when it detects invalid padding, as in the decryption snippet we wrote above, you get something slightly different:

How does this help? Well, think back to how CBC mode works. If the server tells us when we have invalid padding instead of correct padding, we can systematically manipulate the ciphertext in a way that lets us learn one byte of plaintext. Specifically, imagine we have two ciphertext blocks (I’m pretending we have a 4 byte block size here so it’s easier to read):

+----------------+ +----------------+
|[a1][a2][a3][a4]| |[b1][b2][b3][b4]|

+----------------+ +----------------+
| \---+ | |
Decrypt | Decrypt |
| +---------|-----XOR
| | |
v v v
+----------------+ +----------------+
|[p1][p2][p3][p4]| |[p5][p6][p7][p8]|
+----------------+ +----------------+

Suppose we set [a4], the last byte of the second-to-last block, to something arbitrary like 42. Then when the server decrypts it, the last byte of plaintext will be:

42 ^ Decrypt([b4]) = [p8]

If, once the server decrypts our modified ciphertext, the value of [p8] is 0x01, then the padding will look correct and the server will respond with Invalid CAPTCHA!. At which point we learn:

42 ^ Decrypt([b4]) = 0x01

So:

Decrypt([b4]) = 42 ^ 0x01 = 43

And we can now fully decrypt the last byte of the message:

[a4] ^ 43 = [p8]

From there we just move on to the second-to-last byte of the second-to-last ciphertext block, and so on.

Impressively, that whole explanation is a lot longer than the key parts of XBOW’s actual solution:

The oracle function there just submits the modified cookie to the server and checks whether it fails due to invalid padding. And then decrypt_block uses this oracle to carry out the full attack, working one byte at a time starting from the end.

Amazingly, this function works perfectly to decrypt the CAPTCHA cookie. Here it is in action (I edited its original code slightly to print out each character as it’s decrypted—XBOW may be an amazing pentester, but it lacks a flair for the dramatic):

The padding oracle attack in action

And the result we get, 2KQLW444GH4IOG, works to create a user and capture the flag!

Closing Thoughts

Writing this post has been a very surreal experience. XBOW’s solution, from start to finish, took 17 minutes and 30 seconds—much less time than it has taken me to write up an explanation of what it did and how it works. Maybe I should have asked XBOW to write the post for me too?

View the entire trace: Breaking a Cryptographic CAPTCHA with a CBC Padding Oracle