"Cryptography istypically bypassed, not penetrated." – Adi Shamir
FAITH IN THE ARCANE
When I tell a developer that I broke their cryptosystem, there'susually a pregnant pause in the conversation where they take it in, like ayoung child being shown a magic trick. As the initial wonder passes, though,they are not usually elated.
"I thought AES wassafe. What should I use instead?"
Sorry, but AES isn't the issue. AES, despite its very minor known flaws, isn't consideredunsafe 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 andnot 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, itfrequently contains characters that will be interpreted as having specialmeaning by various systems. As such, encrypted data is usually encoded. Ourfirst step is to decode the data. I will use Burp Suite's Decoder tool for thistask.
The first thing to notice after decoding is that the outputis 32 bytes in length. As this is a multiple of 8, 16, and 32, this indicates thata block cipher is likely in use as those are common block sizes. An additionalfew bytes might be present, which could indicate a checksum of some sort. It'spossible to have ciphertext that isn't a multiple of eight bytes, since thereare ciphers that operate on data a byte at a time (stream ciphers). Our biggestclue is randomness. The output from decoding appears random, but humans are badat "seeing" randomness. To get more objective feedback, we will use a toolcalled "ent".
Ent tells us that our decoded data recorded in "/tmp/random",after a number of statistical tests, is apparently random. The items that tipus off are the chi square test and the test involving the application of thedata as input to a Monte Carlo function. The chi square test is very sensitiveto 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 showingsigns of non-randomness. In the Monte Carlo test, the closer the Monte Carlovalue is to Pi, the more randomness is shown in the data.
To contrast, let's analyze a sample that appears random tohumans, but is actually non-random:
This decodes to:
On visual inspection, you or I might say that this is veryrandom. Let's ask ent!
We can see that the chi square test identifies this data asdecidedly non-random. The Monte Carlo test tells us the same. The other resultsare misleading, as tests for randomness are more accurate with large volumes ofdata. For those curious, this sample was generated by Base64 encoding plaintext and using ROT13 to scramble the Base64 string.
A STEP CLOSER
Our nextstep will be to tamper with the data to determine how the data is handled bythe server and whether or not it is tamper-proofed. A useful tool for this isBurp Suite's Intruder. The "Bit Flipper" mode will take input that we give itand modify the input by changing the data one bit at a time. For Base64 encodeddata, we will need to do a little bit of work to get Burp to work with itproperly.
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 ofthe 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, weget responses with blank Location headers. When we flip the second 16 bytes, weget server errors:
These responses tell us a lot about what's happeningserver-side.
- There is likely no tamper-proofing built intothis mechanism, as:
- We tampered with the ciphertext and got "normal"responses from the server.
- The block size of the message is 16 bytes, or128 bits, as:
- 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.
- The cipher is operating in ECB mode, as:
- Modifying the first block did not result in aserver error.
- Modifying the last block, which containspadding, would corrupt the block (and thus the padding) resulting in a message whichwas rejected as corrupted and resulted in an error.
- None of our modifications of block 1 seemed toresult 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 oneanother within an encrypted message, duplicating; deleting; or moving blockshas no effect on the validity of the message decryption except when itinterferes with the message being properly padded. Block shuffling is theprocess of scrambling the blocks of a message around to see what kind of effectit has on the application.
Frequently, application developers assume that encryption isimpenetrable and that input validation does not need to be performed on freshlydecrypted data. This is a bad assumption.
Burp Suite has an ECB block shuffling mode for Intruderwhich we'll use to launch the attack:
After configuring Intruder, we fire away and look at theresponses. The responses are particularly interesting. One ciphertext generatedby duplicating the first block generated the following response:
Note the highlighted portion in the Location header. This isthe content of the first block, disclosed to us in plain text. This is acryptographic variant of the confused deputy problem called a "decryptionoracle" that allows us to decrypt data by providing it to a system that will doit for us.
We can now insert blocks from other messages that use thesame key and cipher and have them decrypted, possibly resulting in dangerous informationdisclosure.
POST-MORTEM
It's important to note that this is not a weakness in AES;this attack is made possible by:
- Key reuse
- Use of the ECB cipher mode
- Lack of tamper proofing on the encrypted data
- Leakage of decrypteddata
- Lack of sanity checks on decrypted data
It seems like there are many stars that needed to align for this attackto be possible, but in reality these conditions are very common because all ofthese conditions (save for the leakage of decrypted data) have one thing incommon: They are the default. In order to prevent these conditions, developershave to be aware of the risks and take steps to mitigate them.
Points to take home:
- Use randomized initialization vectors (IVs) to prevent attacks which rely on the reuse of cryptovariables (key and IV).
- Do not use ECB mode. CBC is a good alternative which helps prevent leaking data.
- Apply an HMAC after encrypting data and check it when decrypting to prevent tampering.
- Avoid disclosing data from cryptographic operations.
- 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.