Padding Oracles for a thousand, please

We did a CTF at work.

I have to say it was loads of fun – I’ve never really participated in a CTF before, so it was really good to test my hacking skills against my new colleagues.

We had one instruction from my manager – “don’t let the interns beat you”. I was determined to make sure that didn’t happen, but I was also determined to share as much knowledge and excitement for InfoSec as possible. This meant that once or twice, I may have egged an intern on in the face of the fact that they were about to discover it anyway, and it just seemed like a really good way to keep them interested.

This is not that story.

This is about me turning the corner from knowing about a security failure, to understanding how it works. Let’s see if I can help you guys understand, too.

Tales from the Crypto

That’s the title of my blog, and there’s not a whole lot of cryptography here. It’s just a play on words, which was a little more relevant when I first started the blog back in 2005. So here’s some crypto, at last.

There’s several aspects to cryptography that you have to get right as a developer:

  • Identify whether you’re doing hashing, signing, encryption, encoding, etc.
  • If you have a key, create and store it securely
  • Pick correct algorithms – modern algorithms with few known issues
  • Use the algorithms in a way that doesn’t weaken them

Having tried to teach all of these to developers in various forms, I can tell you that the first one, which should be the simplest, is still surprisingly hard for some developers to master. Harder still for managers – the number of breach notifications that talk about passwords being “encrypted” is a clear sign of this – encrypted passwords mean either your developers don’t understand and implemented the wrong thing, or your manager doesn’t understand what the developer implemented and thinks “encrypted sounds better than hashed”, and puts that down without checking that it’s still technically accurate.

Key creation (so it’s not predictable), and storage (so it can’t be found by an attacker) is one of those issues that seems to go perennially unsolved – I’m not happy with many of the solutions I’ve seen, especially for self-hosted services where you can’t just appeal to a central key vault such as is currently available in all good cloud platforms.

Picking correct algorithms is a moving target. Algorithms that were considered perfectly sound ten or twenty years ago are now much weaker, and can result in applications being much weaker if they aren’t updated to match new understanding of cryptography, and processor and memory speed and quantity improvements. You can store rainbow tables in memory now that were unthinkable on disk just a decade or two ago.

Finally, of course, if all that wasn’t enough to make cryptography sound really difficult (spoiler: it is, which is why you get someone else to do it for you), there are a number of ways in which you can mess up the way in which you use the algorithm.

Modes, block-sizes, and padding

There are a large number of parameters to set even when you’ve picked which algorithms you’re using. Key sizes, block sizes, are fairly obvious – larger is (generally) better for a particular algorithm. [There are exceptions, but it’s a good rule of thumb to start from.]

There are a number of different modes available, generally abbreviated to puzzling TLAs – ECB, CFB, OFB, CBC, GCM, CTR, and so on and so forth. It’s bewildering. Each of these modes just defines a different order in which to apply various operations to do things like propagating entropy, so that it’s not possible to infer anything about the original plaintext from the ciphertext. That’s the idea, at least. ECB, for instance, fails on this because any two blocks of plaintext that are the same will result in two blocks of ciphertext that are the same.

And if you’re encrypting using a block cipher, you have to think about what to do with the last block – which may not be a complete block. This requires that the block be filled out with “padding” to make a full block. Even if you’re just filling it out with zeroes, you’re still padding – and those zeroes are the padding. (And you have to then answer the question “what if the last block ended with a zero before you padded it?”)

There’s a number of different padding schemes to choose from, too, such as “bit padding”, where after the last bit, you set the next bit to 1, and the remaining bits in the block to 0. Or there’s padding where the last byte is set to the count of how many padding bytes there are, and the remaining bytes are set to 0 – or a set of random bytes – or the count repeated over and over. It’s this latter that is embodied as PKCS#5 or PKCS#7 padding. For the purposes of this discussion, PKCS#7 padding is a generalised version of PKCS#5 padding. PKCS#5 padding works on eight-byte blocks, and PKCS#7 padding works on any size blocks (up to 256 bytes, presumably).

So, if you have a three-byte last block, and the block size is 16 bytes, the last block is ** ** ** 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d 0x0d (where “**” represents the last three bytes of data, and 0x0d represents the hexadecimal value for 13, the number of bytes in the padding). If your last block is full, PKCS#7 covers this by making you create an extra 16-byte block, with the value 0x10 (decimal 16) in every byte.

Tying this in to the CTF

It’s not at all unlikely that you wind up with the scenario with which we were presented in the CTF – a service that communicated with AES encryption, in CBC mode, using PKCS#7 padding. The fact that this was described as such was what tipped me off in the first place. This is the perfect setup for a Padding Oracle attack.

An Oracle is simply a device/function/machine/system/person that you send a request to, and get a response back, and which gives you some information as a result. The classical Oracles of Ancient Greece & Roman times were confusing and unhelpful at best, and that’s really something we want from any cryptographic oracle. The term “Random Oracle” refers to a hypothetical system which returns random information to every query. A good cryptographic system is one that is indistinguishable from a Random Oracle.

Sadly, CBC with PKCS#7 padding is generally very different from a Random Oracle. It is a Padding Oracle, because it will tell us when the padding is correct or incorrect. And that’s our vulnerability.

At this point, I could have done what one of my colleagues did, and download PadBuster, choosing parameters and/or modifying code, to crack the encryption.

But… I’ve been attacking this CTF somewhat … non-traditionally, using tools other than the normal ones, and so I thought I’d try and understand the algorithm’s weaknesses, and implement my own attack. I wrote it on the bus on my way into work, and was pleased to see when I got in that it worked – albeit slowly – first time.

How CBC and PKCS#5/7 is vulnerable

When decrypting each block using CBC, we say that PN = DK(CN)⊕CN-1 – which is just a symbolic way of saying that the recipient Decrypts (with key “K”) the current Ciphertext block (block N), and then XORs the result with the previous Ciphertext block (the N-1th block). Let’s also assume that we’re only decrypting those two blocks, N-1 and N, with N being the last block provided to the recipient.

In other modes, the padding check may not deliver the helpful information we’re looking for, but CBC is special. The way CBC decrypts data is to decrypt the current block of ciphertext (CN), which creates an intermediate block DK(CN). That intermediate block is combined with the previous ciphertext block, CN-1, to give the plaintext block, PN. This combining of blocks is done using the XOR (exclusive-or) operation, which has interesting properties any developer should be familiar with. Particularly, it’s important to note that XOR (represented here as “⊕”) is reversible. If X⊕Y=Z, you know also that Z⊕Y=X and Z⊕X=Y. This is one of the reasons the XOR operation is used in a lot of cryptographic algorithms.

If we want to change things in the inputs to produce a different output, we can really only change two things – the current and the previous block of Ciphertext – CN and CN-1. We should really only alter one input at a time. If we alter CN, that’s going to be decrypted, and a small change will be magnified into a big difference to the DK(CN) value – all the bytes will have changed. But if we alter CN-1, just a bit, what we wind up with is a change in the plaintext value PN which matches that change. If we alter the 23rd bit of CN-1, it will alter the 23rd bit of PN, and only that one bit. Now if we can find what we’ve changed that bit to, we can then figure out what that means we must have changed it from.

If we change the last byte of CN-1, to create C’N-1 (pronounced “C prime of N minus 1”) and cycle it through all the possible values it can take, the decryption will occur, and the recipient will reject our new plain text, P’N (“P prime of N”) because it is poorly formed – it will have a bad padding. With one (two, but I’ll come to that in a minute) notable exception. If the last byte of the plaintext decrypted is the value 0x01, it’s a single byte of padding – and it’s correct padding. For that value of the last byte of C’N-1, we know that the last byte of P’N is 1. We can rewrite PN = DK(CN)⊕CN-1 as DK(CN) = CN-1⊕PN – and then we can put the values in for the last byte: DK(CN)[15] = C’N-1[15]⊕0x01.

Let’s say, for illustration’s sake, that the value we put in that last byte of C’N-1 was 0xa5, when our padding was accepted. That means DK(CN)[15] = 0xa5 ⊕ 0x01 = 0xa4. Note the lack of any “prime” marks there – we’ve figured out what the original value of the decrypted last byte was. Note that this isn’t the same as the last byte of the plain text. No, we get that by taking this new value and XORing it with the original last byte of the previous block of ciphertext – that’s CN-1[15]. For illustration, let’s say that value is 0xc5. We calculate PN[15] = DK(CN)[15]⊕CN-1[15] = 0xa4⊕0xc5 = 0x61. That’s the lower case letter ‘a’.

OK, so we got the first piece of plaintext out – the last byte.

[Remember that I said I’d touch on another case? If CN is the original last block of ciphertext, it already contains valid padding! But not necessarily the 0x01 we’re trying to force into place.]

Let’s get the next byte!

Almost the same process is used to get the next byte, with a couple of wrinkles. First, obviously, we’re altering the second-to-last byte through all possible values. Second, and not quite so obvious, we have to tweak the last byte once as well, because we’re looking to get the sequence 0x02 0x02 (two twos) to happen at the end of P’N. The last byte of C’N-1 to achieve this is simply the last byte of C’N-1 that we used to get 0x01, XORed by 0x03 (because that’s 0x02 ⊕ 0x01). In our illustrative example, that’s 0xa6.

And the next, and the next…

Each time, you have to set the end values of the ciphertext block, so that the end of P’N will look like 0x03 0x03 0x03, 0x04 0x04 0x04 0x04, etc, all the way up to 0x10 … 0x10 (sixteen 16s).

Code, or it didn’t happen

So here’s the 200 lines or so that I wrote on the bus. I also wrote a test harness so that this would work even after the CTF finished and got shut down. You’ll find that in the same repo.

I’ve massaged the code so it’s easier to understand, or to use as an explainer for what’s going on.

I plan on expanding this in a couple of ways – first, to make it essentially command-line compatible with ‘PadBuster’, and second, to produce a graphical demo of how the cracking happens.

And in the next post, I’m going to talk a little about how I optimised this code, so that it was nearly 15x faster than PadBuster.

Leave a Reply

Your email address will not be published. Required fields are marked *