Padding Oracle 2: Speeding things up

Last time, I wrote about how I’d decided to write a padding oracle exploit tool from scratch, as part of a CTF, and so that I could learn a thing or two. I promised I’d tell you how I made it faster… but first, a question.

Why build, when you can borrow?

One question I’ve had from colleagues is “why didn’t you just run PadBuster?”

It’s a great question, and in general, you should always think first about whether there’s an existing tool that will get the job done quickly and easily.

Time

Having said that, it took me longer to install PadBuster and the various language components it required than it did to open Visual Studio and write the couple of hundred lines of C# that I used to solve this challenge.

So, from a time perspective, at least, I saved time by doing it myself – and this came as something of a surprise to me.

The time it used up was my normally non-productive time, while I’m riding the bus into Seattle with spotty-to-zero network connectivity (there’s none on the bus, and my T-Mobile hot-spot is useful, but neither fast nor reliable down the I-5 corridor). This is time I generally use to tweet, or to listen to the BBC.

Interest

I just plain found it interesting to take what I thought I knew about padding oracles, and demonstrate that I had it solidly in my head.

That’s a benefit that really can’t be effectively priced.

Plus, I learned a few things doing it myself:

• Parallelisation in C# is easier than it used to be.
• There’s not much getting around string conversions in trying to speed up the construction of a base64-encoded URL, but then again, when executing against a crypto back-end, that’s not your bottleneck.
• Comments and blank lines are still important, especially if you’re going to explain the code to someone else.

Performance

The other thing that comes with writing your own code is that it’s easier to adjust it for performance – you know where the bottlenecks might lie, and you can dive in and change them without as much of a worry that you’re going to kill the function of the code. Because you know at a slightly more intuitive level how it all works.

You can obviously achieve that intuitive level over time with other people’s code, but I wasn’t really going to enjoy that.

Looking at some of the chat comments directed at the PadBuster author, it’s clear that other people have tried to suggest optimisations to him, but he believes them not to be possible.

Guessing

Specifically, he doesn’t see that it’s possible to use guesses as to the plaintext’s likely contents to figure out what values should be in the ciphertext. You just plug the values 0..255 into the N-1 ciphertext block until your padding error from the N block goes away, and then that value can be XORed with the padding value to get the intermediate value from the N block. Then the intermediate value gets XORed with the original ciphertext value from the N-1 block to give the original plaintext.

Let’s see how that works in the case of the last block – where we’re expecting to see some padding anyway. Let’s say our block size is 4. Here’s what two of our ciphertext blocks might look like:

Pretty random, right? Yeah, those are actually random numbers, but they’ll work to illustrate how we work here.

We iterate through values of C_N-1[3] from 0..255, until we get a response that indicates no padding errors.

0x30 comes back without any padding errors. That’s convenient. So, we’ve sent “be484530714fcc63”, and we know now that we’ve got a padding byte correct. Buuut that isn’t the only right padding byte, because this is the last block, which also has a valid padding byte.

In fact, we can see that 0x30 matches the original value of the C_N-1 block’s last byte, so that’s not terribly useful. Our padding count has a good chance of not being 1, and we’re trying to find the value that will set it to 1.

Keep iterating, and we get 0x32, giving us a request that doesn’t contain a padding exception. Two values. Which one made our padding byte 0x1, so we can use it to determine the intermediate value?

The only way we get two matches will be because the real plaintext ends in a padding count that isn’t 0x1. One of those values corresponds to 0x1, the other corresponds to the padding count, which could be 0x2..0x4. [Because we’re using four byte blocks as an example – a real-life example might have a 16-byte block size, so the padding count could be up to 0x10]

The clue is in the original plaintext – 0x30 MUST be the value that corresponds to the original padding count, so 0x32 MUST correspond to 0x1.

[If the original padding count was 0x1, we would only find one value that matched, and that would be the original value in C_N-1]

That means the Intermediate value is 0x32 XOR 0x1 = 0x33 – which means the plaintext value is 0x3 – there’s three bytes of padding at the end of this block.

We can actually write down the values of the last three plaintext and intermediate blocks now:

Wow – that’s easy! How’d we do that? Really simple. We know the last padding must be three bytes of 0x3, so we write those down. Then the intermediate bytes must be the XOR of 0x3 with the value in the C_N-1 block.

[I chose in the code, instead of just “writing down” the values for each of those bytes, to check each one as I did so, to make sure that things were working. This adds one round-trip for each byte of padding, which is a relatively low cost, compared to the rest of the process.]

Now, if we want to detect the next byte, we want to change the last three bytes of C_N-1, so they’ll set the P_N values to 0x4, and then iterate through the target byte until we get a lack of padding errors.

So, each new value of the last few bytes of C_N-1 will be C’[i] = C[i] XOR 0x3 XOR 0x4 – taking the value in the original, XORing it with the original plaintext, and then with the desired plaintext to get a new value for the ciphertext.

I’ve put those values of C’_N-1 in the table above.

This trick doesn’t just stop with the padding bytes, though. I’m going to guess this is a JSON object, so it’s going to end with a ‘}’ character (close-brace), which is 0x7d.

So, C’ = C XOR 0x7d XOR 0x4 = 0xbe XOR 0x7d XOR 0x4 = 0xc7.

Let’s try that – we now send “c74f4237” – no padding error!

A successful guess for the last four bytes of P_N. Now we can fill in more of the table:

Awesome.

That does require me making the right guess, surely, though?

Yes, but it’s amazing how easy it is to either make completely correct guesses, or just pick a set of values that are more likely to be good guesses, and start by trying those, failing back to the “plod through the rest of the bytes” approach when you need to.

I’ve coded an English-language frequency table into my padding oracle code, because that was appropriate for the challenge I was working on.

This code is available for you to review and use at https://github.com/alunmj/PaddingOracle/blob/master/PadOracle/Program.cs

You can imagine all kinds of ways to improve your guesses – when proceeding backward through a JSON object, for instance, a ‘}’ character will be at the end; it’ll be preceded by white space, double quotes, or brackets/braces, or maybe numerics. A 0x0a character will be preceded by a 0x0d (mostly), etc.

Parallelisation

The other big performance improvement I made was to parallelise the search. You can work on one block entirely independently from another.

I chose to let the Parallel.For() function from C# decide exactly how it was going to split up work between different blocks, and the result is a whole lot faster. There are some wrinkles to manage when parallelising an algorithm, but I’m not going to get into that here. This is not a programming blog, really!

15x performance improvement

I figured I’d put that in big letters, because it’s worth calling out – the parallelisation alone obviously multiplies your performance by the number of cores you’ve got (or the number of cores the web server has, if it’s underpowered), and the predictive work on the text does the rest. Obviously, the predictive approach only works if you can separate between “likely” and “unlikely” characters – if the plaintext consists of random binary data, you’re not going to get much of a benefit. But most data is formatted, and/or is related to English/Latin text.

Bonus stage – use a decryptor to encrypt!

I haven’t published the code for this part yet, but you can use this same breach to encrypt data without knowing the key.

This is really fun and simple once you get all the previous stuff. Here goes.

Let’s encrypt a block.

Encrypting a block requires the generation of two ciphertext blocks from one plaintext block. What the second block is, actually doesn’t matter. We can literally set it to random data, or (which is important) specific data of our choosing.

The first block of the pair, acting like an IV, we can set to 0. There’s a reason for this which we’ll come to in a minute.

With these two initial blocks, we run the decrypter. This will give us a ‘plaintext’ block as output. Remember how the intermediate block is the plaintext block XORed with the first of the pair of blocks? Well, because we set that first block to all zeroes, that means the plaintext block IS the same as the intermediate block. And that intermediate block was generated by decrypting the second block of the pair. In order for that decryption to result in the plaintext we want instead, we can simply take the intermediate block, XOR it with the plaintext block we want, and then put that into the first ciphertext block. [We’re actually XORing this with the first ciphertext block, but that’s a straight copy in this case, because the first ciphertext block is zeroes.]

Now, draw the rest of the owl

Do the same thing for each of the rest of the blocks.

Sadly, there’s no parallelising this approach, and the guessing doesn’t help you either. You have to start with C_N (randomly generated) and C_N-1 (deduced with the approach above), then when you’ve established what C_N-1 is, you can use the same approach to get C_N-2, and so on back to the IV (C₀). So this process is just plain slow. But it allows you to encrypt an arbitrary set of data.