Loading...
Blogs & Stories

SpiderLabs Blog

Attracting more than a half-million annual readers, this is the security community's go-to destination for technical breakdowns of the latest threats, critical vulnerability disclosures and cutting-edge research.

Defeating AES without a PhD

"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.

Decoded ciphertext

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 check random

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:

Screen Shot 2013-01-17 at 12.52.16 PM

This decodes to:

Screen Shot 2013-01-17 at 12.52.58 PM

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

Ent check notrandom

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:

Intruder position

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

Positions hex

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

Payloads

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:

Payload processing

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

The original response looks like the following:

Screen Shot 2012-12-10 at 5.25.42 PM

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:

Screen Shot 2012-12-11 at 1.47.54 PM

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

  1. There is likely no tamper-proofing built intothis 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 aserver error.
      2. 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.
      3. 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:

    Ecb_correct

    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:

    Duplicate_block

    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:

    1. Key reuse
    2. Use of the ECB cipher mode
    3. Lack of tamper proofing on the encrypted data
    4. Leakage of decrypteddata
    5. 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:

    1. Use randomized initialization vectors (IVs) to prevent attacks which rely on the reuse of cryptovariables (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.