Defeating AES without a PhD

"Cryptography is typically bypassed, not penetrated." – Adi Shamir

FAITH IN THE ARCANE

When I tell a developer that I broke their cryptosystem, there's usually a pregnant pause in the conversation where they take it in, like a young child being shown a magic trick. As the initial wonder passes, though, they are not usually elated.

"I thought AES was safe. What should I use instead?"

Sorry, but AES isn't the issue. AES, despite its very minor known flaws, isn't considered unsafe as of this writing. 6-inch thick steel walls are difficult to break through, but that's not generally how you get past steel walls. One goes around, under, above them, not through.

THE WALL

Our analysis begins by identifying that the target is using cryptography and not just obfuscated or random values. In our example, various URLs contain Base64 encoded data.

http://example.com/redirect.jsp?params=5ZNzp7BUb8EdILJsQCkMQy5gpvYsI0ozQvHON1uwbh4=

Since data encrypted with a strong cipher appears random, it frequently contains characters that will be interpreted as having special meaning by various systems. As such, encrypted data is usually encoded. Our first step is to decode the data. I will use Burp Suite's Decoder tool for this task.

The first thing to notice after decoding is that the output is 32 bytes in length. As this is a multiple of 8, 16, and 32, this indicates that a block cipher is likely in use as those are common block sizes. An additional few bytes might be present, which could indicate a checksum of some sort. It's possible to have ciphertext that isn't a multiple of eight bytes, since there are ciphers that operate on data a byte at a time (stream ciphers). Our big gest clue is randomness. The output from decoding appears random, but humans are bad at "seeing" randomness. To get more objective feedback, we will use a tool called "ent".

Ent tells us that our decoded data recorded in "/tmp/random",after a number of statistical tests, is apparently random. The items that tip us off are the chi square test and the test involving the application of the data as input to a Monte Carlo function. The chi square test is very sensitive to errors in randomness and is commonly used in testing the randomness of data. If data is on the far upper end or far lower end (90%+ or 10%-) then it is showing signs of non-randomness. In the Monte Carlo test, the closer the Monte Carlo value is to Pi, the more randomness is shown in the data.

To contrast, let's analyze a sample that appears random to humans, but is actually non-random:

This decodes to:

On visual inspection, you or I might say that this is very random. Let's ask ent!

We can see that the chi square test identifies this data as decidedly non-random. The Monte Carlo test tells us the same. The other results are misleading, as tests for randomness are more accurate with large volumes of data. For those curious, this sample was generated by Base64 encoding plaintext and using ROT13 to scramble the Base64 string.

A STEP CLOSER

Our next step will be to tamper with the data to determine how the data is handled by the server and whether or not it is tamper-proofed. A useful tool for this is Burp Suite's Intruder. The "Bit Flipper" mode will take input that we give it and modify the input by changing the data one bit at a time. For Base64 encoded data, we will need to do a little bit of work to get Burp to work with it properly.

Here we see the initial request loaded into Intruder:

We first decode it from Base64 and encode it in ASCII hex,as Burp works well with this.

Next, we tell Burp Intruder to use the Bit Flipper mode:

This setting will cause Burp to properly flip the bits of the ciphertext, but, without payload processing, it will not be re-encoded asBase64. We should set the payload processing options to decode as ASCII hex andre-encode as Base64 before submitting the payload:

We set throttling options so as not to overwhelm the webserver, and then fire away.

The original response looks like the following:

Upon bit flipping the first 16 bytes of the ciphertext, we get responses with blank Location headers. When we flip the second 16 bytes, we get server errors:

These responses tell us a lot about what's happening server-side.

1. There is likely no tamper-proofing built into this mechanism, as:
   1. We tampered with the ciphertext and got "normal" responses from the server.
   2. The block size of the message is 16 bytes, or128 bits, as:
      1. Responses were unique to modifications on each 16-bytehalf of the message. This indicates that a block cipher with a block size of128 bits is in use.
   3. The cipher is operating in ECB mode, as:
      1. Modifying the first block did not result in a server error.
      2. Modifying the last block, which contains padding, would corrupt the block (and thus the padding) resulting in a message which was rejected as corrupted and resulted in an error.
      3. None of our modifications of block 1 seemed to result in corruption of the message. If the cipher were operating in CBC mode, flipping bits in block 1 would have resulted in flipped bits in block 2.

Next, we'll try an attack specific to ECB: Block shuffling.

INITIAL ATTACK

Since ECB mode means that the blocks have no relation to one another within an encrypted message, duplicating; deleting; or moving blocks has no effect on the validity of the message decryption except when it interferes with the message being properly padded. Block shuffling is the process of scrambling the blocks of a message around to see what kind of effect it has on the application.

Frequently, application developers assume that encryption is impenetrable and that input validation does not need to be performed on freshly decrypted data. This is a bad assumption.

Burp Suite has an ECB block shuffling mode for Intruder which we'll use to launch the attack:

After configuring Intruder, we fire away and look at the responses. The responses are particularly interesting. One ciphertext generated by duplicating the first block generated the following response:

Note the highlighted portion in the Location header. This is the content of the first block, disclosed to us in plain text. This is a cryptographic variant of the confused deputy problem called a "decryption oracle" that allows us to decrypt data by providing it to a system that will do it for us.

We can now insert blocks from other messages that use the same key and cipher and have them decrypted, possibly resulting in dangerous information disclosure.

POST-MORTEM

It's important to note that this is not a weakness in AES; this attack is made possible by:

1. Key reuse
2. Use of the ECB cipher mode
3. Lack of tamper proofing on the encrypted data
4. Leakage of decrypted data
5. Lack of sanity checks on decrypted data

It seems like there are many stars that needed to align for this attack to be possible, but in reality these conditions are very common because all of these conditions (save for the leakage of decrypted data) have one thing in common: They are the default. In order to prevent these conditions, developers have to be aware of the risks and take steps to mitigate them.

Points to take home:

1. Use randomized initialization vectors (IVs) to prevent attacks which rely on the reuse of crypto variables (key and IV).
2. Do not use ECB mode. CBC is a good alternative which helps prevent leaking data.
3. Apply an HMAC after encrypting data and check it when decrypting to prevent tampering.
4. Avoid disclosing data from cryptographic operations.
5. Apply sanity checks to decrypted data, too.

Remember to check the use of crypto in your applications to ensure that you're doing more than just using a solid algorithm, since there are other ways to create problems.