Just a quick note, because Iâve been sick this week, but last weekend, I put a little more work into my Padding Oracle exploit tool.
You can find the new code up at https://github.com/alunmj/PaddingOracle, and because of all the refactoring, itâs going to look like a completely new batch of code. But I promise that most of it is just moving code from Program.cs into classes, and adding parsing of command-line arguments.
I donât pretend to be the worldâs greatest programmer by any stretch, so if you can tell me a better way to do what Iâve done here, do let me know, and Iâll make changes and post something about them here.
Also, please let me know if you use the tool, and how well it worked (or didn’t!) for you.
The arguments currently supported are:
The only parameter unadorned with an option letter â this is the URL for the resource the Padding Oracle code will be pounding to test guesses at the encrypted code.
Also, âcipher. This provides a .NET regular expression which matches the ciphertext in the URL.
Also, âtextencoding, âencoding. This sets the encoding thatâs used to specify the ciphertext (and IV) in the URL. The default is b64
Also, âiv. This provides a .NET regular expression which matches the IV in the URL if itâs not part of the ciphertext.
Also, âblocksize. This sets the block size in bytes for the encryption algorithm. It defaults to 16, but should work for values up to 32.
Also, âverbose. Verbose â output information about the packets weâre decrypting, and statistics on speed at the end.
Also, âhelp. Outputs a brief help message
Also âparallelism. Dictates how much to parallelise. Specifying â1â means to use one thread, which can be useful to see whatâs going on. â1 means âmaximum parallelisationâ â as many threads as possible. Any other integer is roughly akin to saying âno more than this number of threadsâ, but may be overridden by other aspects of the Windows OS. The default is â1.
Instead of decrypting, this will encrypt the provided text, and provide a URL in return that will be decrypted by the endpoint to match your provided text.
These examples are run against the WebAPI project thatâs included in the PadOracle solution.
Letâs say youâve got an example URL like this:
http://localhost:31140/api/encrypted/submit?iv=WnfvRLbKsbYufMWXnOXy2Q%3d%3d&ciphertext=087gbLKbFeRcyPUR2tCTajMQAeVp0r50g07%2bLKh7zSyt%2fs3mHO96JYTlgCWsEjutmrexAV5HFyontkMcbNLciPr51LYPY%2f%2bfhB9TghbR9kZQ2nQBmnStr%2bhI32tPpaT6Jl9IHjOtVwI18riyRuWMLDn6sBPWMAoxQi6vKcnrFNLkuIPLe0RU63vd6Up9XlozU529v5Z8Kqdz2NPBvfYfCQ%3d%3d
This strongly suggests (because who would use âivâ and âciphertextâ to mean anything other than the initialisation vector and cipher text?) that you have an IV and a ciphertext, separate from one another. We have the IV, so letâs use it â hereâs the command line Iâd try:
PadOracle "http://localhost:31140/api/encrypted/submit?iv=WnfvRLbKsbYufMWXnOXy2Q%3d%3d&ciphertext=087gbLKbFeRcyPUR2tCTajMQAeVp0r50g07%2bLKh7zSyt%2fs3mHO96JYTlgCWsEjutmrexAV5HFyontkMcbNLciPr51LYPY%2f%2bfhB9TghbR9kZQ2nQBmnStr%2bhI32tPpaT6Jl9IHjOtVwI18riyRuWMLDn6sBPWMAoxQi6vKcnrFNLkuIPLe0RU63vd6Up9XlozU529v5Z8Kqdz2NPBvfYfCQ%3d%3d" -c "087gb.*%3d%3d" âi "WnfvRL.*2Q%3d%3d"
This is the result of running that command:
Notes:
Same URL, but this time I want to encrypt some text.
Our command line this time is:
PadOracle "http://localhost:31140/api/encrypted/submit?iv=WnfvRLbKsbYufMWXnOXy2Q%3d%3d&ciphertext=087gbLKbFeRcyPUR2tCTajMQAeVp0r50g07%2bLKh7zSyt%2fs3mHO96JYTlgCWsEjutmrexAV5HFyontkMcbNLciPr51LYPY%2f%2bfhB9TghbR9kZQ2nQBmnStr%2bhI32tPpaT6Jl9IHjOtVwI18riyRuWMLDn6sBPWMAoxQi6vKcnrFNLkuIPLe0RU63vd6Up9XlozU529v5Z8Kqdz2NPBvfYfCQ%3d%3d" -c "087gb.*%3d%3d" âi "WnfvRL.*2Q%3d%3d" âe "Hereâs some text I want to encrypt"
When we run this, it warns us itâs going to take a very long time, and boy itâs not kidding â we donât get any benefit from the frequency table, and we canât parallelise the work.
And you can see it took about two hours.
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.
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.
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.
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.
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.
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:
CN-1 | CN | ||||||
0xbe | 0x48 | 0x45 | 0x30 | 0x71 | 0x4f | 0xcc | 0x63 |
Pretty random, right? Yeah, those are actually random numbers, but theyâll work to illustrate how we work here.
We iterate through values of CN-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 CN-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 CN-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:
CN-1 | CN | ||||||
0xbe | 0x48 | 0x45 | 0x30 | 0x71 | 0x4f | 0xcc | 0x63 |
IN | |||||||
?? | 0x4b | 0x46 | 0x33 | ||||
CâN-1 | PN | ||||||
?? | 0x4f | 0x42 | 0x37 | ?? | 0x3 | 0x3 | 0x3 |
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 CN-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 CN-1, so theyâll set the PN 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 CN-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 PN. Now we can fill in more of the table:
CN-1 | CN | ||||||
0xbe | 0x48 | 0x45 | 0x30 | 0x71 | 0x4f | 0xcc | 0x63 |
IN | |||||||
0xba | 0x4b | 0x46 | 0x33 | ||||
CâN-1 | PN | ||||||
0xc7 | 0x4f | 0x42 | 0x37 | 0x7d | 0x3 | 0x3 | 0x3 |
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.
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!
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.
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.
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.]
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 CN (randomly generated) and CN-1 (deduced with the approach above), then when youâve established what CN-1 is, you can use the same approach to get CN-2, and so on back to the IV (C0). So this process is just plain slow. But it allows you to encrypt an arbitrary set of data.
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.
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:
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.
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.
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.
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.]
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.
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).
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.