Search
Twitter
« New Version of PadBuster Available for Download | Main | Constricting the Web: The GDS Burp API »
Tuesday
Sep142010

Automated Padding Oracle Attacks with PadBuster

There’s been a lot of buzz recently about Padding Oracle Attacks, an attack vector demonstrated by Juliano Rizzo and Thai Duong during their presentation at BlackHat Europe earlier this summer. While padding oracles are relatively easy to exploit, the act of exploiting them can be time consuming if you don’t have a good way of automating the attack. The lack of good tools for identifying and exploiting padding oracles led us to develop our own internal padding oracle exploit script, PadBuster, which we’ve decided to share with the community. The tool can be downloaded here, but I’ll spend a little bit of time discussing how the tool works and the various use cases it supports.

Update 9/28/10: PadBuster v0.2 has been released.

Some Background

Before we discuss using PadBuster, let’s briefly discuss the fundamentals of a classic padding oracle attack. As the term implies, a critical concept behind a padding oracle attack is the notion of cryptographic padding. Plaintext messages come in a variety of lengths; however, block ciphers require that all messages be an exact number of blocks. To satisfy this requirement, padding is used to ensure that a given plaintext message can always be divided into an exact number of blocks.

While several padding schemes exist, one of the most common padding schemes is described in the PKCS#5 standard. With PCKS#5 padding, the final block of plaintext is padded with N bytes (depending on the length of the last plaintext block) of value N. This is best illustrated through the examples below, which show words of varying length (FIG, BANANA, AVOCADO, PLANTAIN, PASSIONFRUIT) and how they would be padded using PKCS#5 padding (the examples below use 8-byte blocks).

Click to Enlarge


Note that at least one padding byte is ALWAYS appended to the end of a string, so a 7-byte value (like AVOCADO) would be padded with 0x01 to fill the block, while an 8-byte value (like PLANTAIN) would have a full block of padding added to it. The value of the padding byte also indicates the number of bytes, so logically final value(s) at the end of the last block of ciphertext must either:

  • A single 0x01 byte (0x01)
  • Two 0x02 bytes (0x02, 0x02)
  • Three 0x03 bytes (0x03, 0x03, 0x03)
  • Four 0x04 bytes (0x04, 0x04, 0x04, 0x04)
  • ...and so on

If the final decrypted block does not end in one of these valid byte sequences, most cryptographic providers will throw an invalid padding exception. The fact that this exception gets thrown is critical for the attacker (us) as it is the basis of the padding oracle attack.

A Basic Padding Oracle Attack Scenario

To provide a concrete example, consider the following scenario:

An application uses a query string parameter to pass the encrypted username, company id, and role id of a user. The parameter is encrypted using CBC mode, and each value uses a unique initialization vector (IV) which is pre-pended to the ciphertext.

When the application is passed an encrypted value, it responds in one of three ways:

  • When a valid ciphertext is received (one that is properly padded and contains valid data) the application responds normally (200 OK)
  • When an invalid ciphertext is received (one that, when decrypted, does not end with valid padding) the application throws a cryptographic exception (500 Internal Server Error)
  • When a valid ciphertext is received (one that is properly padded) but decrypts to an invalid value, the application displays a custom error message (200 OK)

The scenario described above is a classic Padding Oracle, because we can use the behavior of the application to easily determine whether the supplied encrypted value is properly padded or not. The term oracle refers to a mechanism that can be used to determine whether a test has passed or failed.

Now that the scenario has been laid out, let’s take a look at one of the encrypted parameters used by the application. This parameter is used by the application to store a semi-colon delimited series of values that, in our example, include the user’s name (BRIAN), company id (12), and role id (2). The value, in plaintext, can be represented as BRIAN;12;2;. A sample of the encrypted query string parameter is shown below for reference. Note that the encrypted UID parameter value is encoded using ASCII Hex representation.

 

http://sampleapp/home.jsp?UID=7B216A634951170FF851D6CC68FC9537858795A28ED4AAC6

At this point, an attacker would not have any idea what the underlying plaintext is, but for the sake of this example, we already know the plaintext value, the padded plaintext value, and the encrypted value (see diagram below). As we mentioned previously, the initialization vector is pre-pended to the ciphertext, so the first block of 8 bytes is just that.



As for the block size, an attacker would see that the length of the encrypted ciphertext is 24 bytes. Since this number is evenly divisible by 8 and not divisible by 16, one can conclude that you are dealing with a block size of 8 bytes. Now, for reference take a look at what happens internally when this value is encrypted and decrypted. We see the process byte-for-byte in the diagram as this information will be helpful later on when discussing the exploit. Also note that the circled plus sign represents the XOR function.

Encryption Diagram (Click to Enlarge):


Decryption Diagram (Click to Enlarge):

It is also worthwhile to point out that the last block (Block 2 of 2), when decrypted, ends in a proper padding sequence as expected. If this were not the case, the cryptographic provider would throw an invalid padding exception.

The Padding Oracle Decryption Exploit

Let’s now look at how we can decrypt the value by using the padding oracle attack. We operate on a single encrypted block at a time, so we can start by isolating just the first block of ciphertext (the one following the IV) and sending it to the application pre-pended with an IV of all NULL values. The URL and associated response are shown below:

 

Request:  http://sampleapp/home.jsp?UID=0000000000000000F851D6CC68FC9537
Response:  500 - Internal Server Error

A 500 error response makes sense given that this value is not likely to result in anything valid when decrypted. The diagram below shows a closer look at what happens underneath the covers when the application attempts to decrypt this value. You should note that since we are only dealing with a single block of ciphertext (Block 1 of 1), the block MUST end with valid padding in order to avoid an invalid padding exception.

As shown above, the exception is thrown because the block does not end with a valid padding sequence once decrypted. Now, let’s take a look at what happens when we send the exact same value but with the last byte of the initialization vector incremented by one.

 

Request: http://sampleapp/home.jsp?UID=0000000000000001F851D6CC68FC9537
Response: 500 - Internal Server Error

Like before, we also get a 500 exception. This is due to the fact that, like before, the value does not end in a valid padding sequence when decrypted. The difference however, is that if we take a closer look at what happens underneath the covers we will see that the final byte value is different than before (0x3C rather than 0x3D).

If we repeatedly issue the same request and increment just the last byte in the IV each time (up to FF) we will inevitably hit a value that produces a valid padding sequence for a single byte of padding (0x01). Only one value (out of the possible 256 different bytes) will produce the correct padding byte of 0x01. When you hit this value, you should end up with a different response than the other 255 requests.

 

Request: http://sampleapp/home.jsp?UID=000000000000003CF851D6CC68FC9537
Response: 200 OK

Let’s take a look at the same diagram to see what happens this time.

Given this is the case, we can now deduce the intermediary value byte at this position since we know that when XORed with 0x3C, it produces 0x01.

If [Intermediary Byte] ^ 0x3C == 0x01,
then [Intermediary Byte] == 0x3C ^ 0x01,
so [Intermediary Byte] == 0x3D

Taking this one step further, now that we know the intermediary byte value we can deduce what the actual decrypted value is. You'll recall that during the decryption process, each intermediary value byte is XORed with the corresponding byte of the previous block of ciphertext (or the IV in the case of the first block). Since the example above is using the first block from the original sample, then we need to XOR this value with the corresponding byte from the original IV (0x0F) to recover the actual plaintext value. As expected, this gives us 0x32, which is the number "2" (the last plaintext byte in the first block).

Now that we’ve decrypted the 8th byte of the sample block, it’s time to move onto the 7th byte. In order to crack the 8th byte of the sample, we brute forced an IV byte that would produce a last decrypted byte value of 0x01 (valid padding). In order to crack the 7th byte, we need to do the same thing, but this time both the 7th and 8th byte must equal 0x02 (again, valid padding). Since we already know that the last intermediary value byte is 0x3D, we can update the 8th IV byte to 0x3F (which will produce 0x02) and then focus on brute forcing the 7th byte (starting with 0x00 and working our way up through 0xFF).

Once again, we continue to generate padding exceptions until we hit the only value which produces a 7th decrypted byte value of 0x02 (valid padding), which in this case is 0x24.



Using this technique, we can work our way backwards through the entire block until every byte of the intermediary value is cracked, essentially giving us access to the decrypted value (albeit one byte at a time). The final byte is cracked using an IV that produces an entire block of just padding (0x08) as shown below.

The Decryption Exploit with PadBuster

Now let’s discuss how to use PadBuster to perform this exploit, which is fairly straightforward. PadBuster takes three mandatory arguments:

  • URL - This is the URL that you want to exploit, including query string if present. There are optional switches to supply POST data (-post) and Cookies if needed (-cookies)
  • Encrypted Sample - This is the encrypted sample of ciphertext included in the request. This value must also be present in either the URL, post or cookie values and will be replaced automatically on every test request
  • Block Size - Size of the block that the cipher is using. This will normally be either 8 or 16, so if you are not sure you can try both

For this example, we will also use the command switch to specify how the encrypted sample is encoded. By default PadBuster assumes that the sample is Base64 encoded, however in this example the encrypted text is encoded as an uppercase ASCII HEX string. The option for specifying encoding (-encoding) takes one of the following three possible values:

  • 0: Base64 (default)
  • 1: Lowercase HEX ASCII
  • 2: Uppercase HEX ASCII

The actual command we run will look like the following:

 

padBuster.pl http://sampleapp/home.jsp?UID=7B216A634951170FF851D6CC68FC9537858795A28ED4AAC6
7B216A634951170FF851D6CC68FC9537858795A28ED4AAC6 8 -encoding 2

Notice that we never told PadBuster how to recognize a padding error. While there is a command line option (-error) to specify the padding error message, by default PadBuster will analyze the entire first cycle (0-256) of test responses and prompt the user to choose which response pattern matches the padding exception. Typically the padding exception occurs on all but one of the initial test requests, so in most cases there will only be two response patterns to choose from as shown below (and PadBuster will suggest which one to use).



The initial output from PadBuster is shown in the screenshot above. You’ll see that PadBuster re-issues the original request and shows the generated response information before starting its testing. This is useful for authenticated applications to ensure that the authentication cookies provided to PadBuster are working correctly.

Once a response pattern is selected, PadBuster will automatically cycle through each block and brute force each corresponding plaintext byte which will take, at most, 256 requests per byte. After each block, PadBuster will also display the obtained intermediary byte values along with the calculated plaintext. The intermediary values can be useful when performing arbitrary encryption exploits as we will show in the next section.

Encrypting Arbitrary Values

We've just seen how a padding oracle and PadBuster can be used to decrypt the contents of any encrypted sample one block at a time. Now, let’s take a look at how you can encrypt arbitrary payloads using the same vulnerability.

You have probably noticed that once we are able to deduce the intermediary value for a given ciphertext block, we can manipulate the IV value in order to have complete control over the value that the ciphertext is decrypted to. So in the previous example of the first ciphertext block that we brute forced, if you want the block to decrypt to a value of "TEST" you can calculate the required IV needed to produce this value by XORing the desired plaintext against the intermediary value. So the string "TEST" (padded with four 0x04 bytes, of course) would be XORed against the intermediary value to produce the needed IV of 0x6D, 0x36, 0x70, 0x76, 0x03, 0x6E, 0x22, 0x39.

This works great for a single block, but what if we want to generate an arbitrary value that is more than one block long? Let’s look at a real example to make it easier to follow. This time we will generate the encrypted string "ENCRYPT TEST" instead of just "TEST". The first step is to break the sample into blocks and add the necessary padding as shown below:

When constructing more than a single block, we actually start with the last block and move backwards to generate a valid ciphertext. In this example, the last block is the same before, so we already know that the following IV and ciphertext will produce the string "TEST".

 

Request:  http://sampleapp/home.jsp?UID=6D367076036E2239F851D6CC68FC9537

Next, we need to figure out what intermediary value 6D367076036E2239 would decrypt to if it were passed as ciphertext instead of just an IV. We can do this by using the same technique used in the decryption exploit by sending it as the ciphertext block and starting our brute force attack with all nulls.

 

Request:  http://sampleapp/home.jsp?UID=00000000000000006D367076036E2239

Once we brute force the intermediary value, the IV can be manipulated to produce whatever text we want. The new IV can then be pre-pended to the previous sample, which produces the valid two-block ciphertext of our choice. This process can be repeated an unlimited number of times to encrypt data of any length.

Encrypting Arbitrary Values with PadBuster

PadBuster has the option to automate the process of creating arbitrary encrypted values in addition to decrypting them. There are three command line switches related to creating ciphertexts:

  • -plaintext [String]: plaintext to EncryptThis is the plaintext you want to encrypt. This option is mandatory when using PadBuster to encrypt data, and its presence is what tells PadBuster to perform encryption instead of decryption
  • -ciphertext [Bytes]: CipherText for Intermediary Bytes (Hex-Encoded)Optional - can be used to provide the starting ciphertext block for encryption. This option must be used in conjunction with the -intermediary option (see below)
  • -intermediary [Bytes]: Intermediary Bytes for CipherText (Hex-Encoded)Optional - can be used to provide the corresponding intermediary byte values for the cipher text specified with the -ciphertext option.

The purpose of the -ciphertext and -intermediary options is to speed up the exploit process as it reduces the number of ciphertext blocks that must be cracked when generating a forged ciphertext sample. If these options are not provided, PadBuster will start from scratch and brute force all of the necessary blocks for encryption. Let’s take a look at the actual command syntax used to encrypt data with PadBuster:

 

padBuster.pl http://sampleapp/home.jsp?UID=7B216A634951170FF851D6CC68FC9537858795A28ED4AAC6
7B216A634951170FF851D6CC68FC9537858795A28ED4AAC6 8 -encoding 2 -plaintext "ENCRYPT TEST"

The output from PadBuster is shown in the screenshot below:

You’ll notice that just like before, PadBuster will first ask you to choose the correct padding error response signature. This step can be skipped if you manually specify the padding error message using the -error option. Also notice that PadBuster performed a brute force of both full ciphertext blocks, because we didn’t specify a starting ciphertext block and associated intermediary value to use. If we had provided these values to PadBuster, the first block would have been calculated instantly and only the second block would require brute force as shown below.

 

padBuster.pl http://sampleapp/home.jsp?UID=7B216A634951170FF851D6CC68FC9537858795A28ED4AAC6
7B216A634951170FF851D6CC68FC9537858795A28ED4AAC6 8 -encoding 2 -plaintext "ENCRYPT TEST"
-ciphertext F851D6CC68FC9537 -intermediary 39732322076A263D

As you can see, the first block (Block 2) was calculated before prompting for the response signature since this block was calculated using just the data provided with the -ciphertext and -intermediary options. If you are wondering where these two values came from, remember that PadBuster prints these two values to the screen at the conclusion of each round of block processing.

So to wrap things up, we are releasing PadBuster because we think that other pen testers can benefit from a flexible exploit script for detecting and exploit padding oracles. We would be interested in hearing if there are other features that would make the tool more useful or practical from a tester’s perspective, so let us know if you have any feedback.

Reader Comments (46)

@eglasius -
Thanks for the reply. What about 200s? It looked like from the posting, that 200s could signify either:

1. When a valid ciphertext is received (one that is properly padded and contains valid data) the application responds normally (200 OK)

OR

2. When a valid ciphertext is received (one that is properly padded) but decrypts to an invalid value, the application displays a custom error message (200 OK)

Therefore, isn't is possible that you could have the majority of 200 responses in the context of the second case above, instead of a majority of 500s? Or is there some reason you would always have a large number of the 500 server response.

It is helpful to know that 404s are less common btw, but mostly interested in 500s versus 200s...thanks!

September 27, 2010 | Unregistered Commenternemadrias

@Brian, Marcin: I think Pete's right.

While block cipher output is (approximately) uniformly distributed, it's not statistically independent of the plaintext and IV. Let's rearrange the equation:

D_k(ciphertext_block) = plaintext_block ⊕ iv

The IV is known and the plaintext distribution is non-uniform, which means that the conditional probability of individual "intermediate value" bytes are not uniform. So guess plaintext bytes and xor with the known IV to get your "intermediate value" guess.

Commentary:
• People are still using unauthenticated encryption where plaintext+MAC might be more sensible.
• With a known CBC/CFB plaintext/ciphertext pair, *anyone* can forge a 1-block message (and OFB/CTR mode is especially trivial).

September 27, 2010 | Unregistered CommenterT Chan

@Brian: I have added the UrlTokenEncoder / Decoder to Padbuster. I also published a post on our blog to better explain the 404 vs 500 issue in .NET Ajax handlers.

http://blog.mindedsecurity.com/2010/09/investigating-net-padding-oracle.html

Thank you again for the original tool!

September 28, 2010 | Unregistered CommenterGiorgio Fedon

@Jiho: The decrypted FormsAuth token is actually a .NET FormsAuthenticationTicket object, so the framework serializes this object into the HEX-encoded cookie that you are decrypting. This is likely the reason that you can't see the contents as text. You are probably going to need to use some .NET code to view and manipulate its contents.

@nemadrias: The example responses described in this post was just an example for demonstration purposes. I reality, there’s no telling how different applications will respond as it is all dependent on what, if any, error handling logic is present within the vulnerable component. The approach taken with PadBuster allows the user to determine what response behavior looks like a padding error and will perform its tests accordingly.

@Giorgio: Nice work. I figured someone would do this before we decided to release the new version. With that being said, version 0.2 is now up and available for download on our tools page (http://www.gdssecurity.com/l/t.php). There are several new features that I will summarize in a quick blog post later today.

September 28, 2010 | Unregistered CommenterBrian Holyfield

Hi,

I have a few sites but dont have session IDs to test again. If I access a site using /webresource.axd and then /webresource.axd?d=foo I am seeing differences, one is a 404 the other a 500 error.

How can the padbuster be used on a URL without a session ID / encrypted string?

I'm wanting to prove the MS patch fixes the issue so a before and after test is what I'm after here.

Thanks

September 30, 2010 | Unregistered CommenterCP

@CP: If you have <customErrors mode="Off">, then you should be able to use an encoded string of 16 nulls as your test string (AAAAAAAAAAAAAAAAAAAAAA2). This should result in something similar to the following when you do the response analysis:


The following response signatures were returned:
-------------------------------------------------------
ID# Freq Status Length Location
-------------------------------------------------------
1 1 500 3880 N/A
2 ** 255 500 5018 N/A
-------------------------------------------------------

If you get something similar to the above, then you are vulnerable. Note, however, that if Custom Errors are not turned off you will not be able to easily distinguish the padding errors since the NULL string also generates a 500 error. For this scenario, you'll want to use a valid encrypted sample string to use for testing. In general, it should be pretty easy to find one of these strings from any of your application pages if you do a "View Source".

September 30, 2010 | Unregistered CommenterBrian Holyfield

Please correct me if I'm wrong.

My understanding is that for any ciphertext block that we intercept, we can decrypt it by setting the IV to null and repeatedly prompting the oracle for the whole intermediary value. It makes perfect sense as one'd like to know what's been protected. However, when it comes to "using an oracle to encrypt arbitrary messages", I am not sure why we want to do this. Is there a particular case that we want to send forged messages to the server?

October 3, 2010 | Unregistered CommenterKevin Tan

Excellent description of the issue, Thanks!

But I'm having difficulty getting padBuster.pl to execute.
My issue is that I can not find a cipher that is divisible by 8.

[IIS7, VB.NET, Win7] This URL: https://localhost/WebResource.axd?d=OZ9F1ZfWDnaAQQlGsCOW1TqxvpDpHTHodbZG-dTgloxi4u_G1WzrsMWa3UJzctV-LMLHB1kkECmGQqFLcEgPlYKN_qg1 returns a 200

Notice the d parameter is 92 characters.

If I change the d parameter in any why I get a 404 error.

October 7, 2010 | Unregistered CommenterMike S

@Mike S: It looks like your server is patched. Check out http://www.troyhunt.com/2010/09/do-you-trust-your-hosting-provider-and.html for a discussion on how to tell if your server has been patched or not. The length of the decoded "d" parameter is a dead giveaway.

October 7, 2010 | Unregistered CommenterBrian Holyfield

Hi,

Is there a tool or method available to encrypt/decrypt requests once the machinekey has been obtained?

October 13, 2010 | Unregistered CommenterSam Elliot

@Brian,

Was trying to use the proxy for NTLM proxying, but noted that $proxy was evaluating to true rather than string. Fix seems to be:

34 \my $proxy,
34 > "proxy=s" => \my $proxy,

I have successfully used cntlm for NTLM auth by pointing cntlm at an upstream burp proxy. The cntlm config is below for anyone that might find this useful.

Username
Domain
Password # Use hashes instead (-H)
# burp proxy
Proxy localhost:8080
# This is the port number where Cntlm will listen
Listen 3128

December 1, 2010 | Unregistered CommenterCraig Lambert

@Brian,

Noticed that my previous comment didn't render properly because of the inclusion of less than chars :-)

Was trying to use the proxy for NTLM proxying, but noted that $proxy was evaluating to true rather than string. Fix seems to be replacing what's on line 34 with:

“proxy=s” => \my $proxy,

I have successfully used cntlm for NTLM auth by pointing cntlm at an upstream burp proxy. The cntlm config is below for anyone that might find this useful.

Username [username]
Domain [domain]
Password [password] # Use hashes instead (-H)
# burp proxy
Proxy localhost:8080
# This is the port number where Cntlm will listen
Listen 3128

December 1, 2010 | Unregistered CommenterCraig Lambert

i used the following format: padBuster.pl URL_OF_APPLICATION VALUE_OF_VIEWSTATE 8 -encoding 2
In response I received an error message: Access is denied. Is this an indication of vulnerability.

for other values, i get the errors similar to:
ERROR: Encrypted Bytes must be evenly divisible by Block Size (8)
Encrypted sample length is 45. Double check the Encoding and Block Size.

if I give 45 as a block size then it gives- ERROR: Encrypted sample was not found in the test request

Also, could you please let me know what do i have to do for the following suggestion... it may look like a silly question but will wait for your help/suggestiona

December 22, 2010 | Unregistered Commentersourabh

sorry .. forgot to add the suggestion in the above post - "try hard-coding the $post and $sample variables below the @ARGV parsing section (this should then work regardless of what you pass in for the post data and sample arguments). " - how to achieve this.

December 23, 2010 | Unregistered Commentersourabh

@Craig: Good catch. I'll update this in the next release.

January 4, 2011 | Unregistered CommenterBrian Holyfield

@sourabh: You should see a few lines in the script that look like this:

# Hard Coded Inputs
#$post = "";
#$sample = "";

What you'll want to do is un-comment the $post and $sample lines (remove the hash) and plug your post data and sample values in between the quotes. This will override the values you specify on the command line.

January 4, 2011 | Unregistered CommenterBrian Holyfield

The good news is that once you have the correct Validation and Decryption it should only require a couple lines of code.

January 4, 2011 | Unregistered CommenterBrian Holyfield

@Sam: No, you'll need to write some custom dot net code for that. The good news is that once you have the correct Validation and Decryption key from the web.config it should only require a couple lines of code.

January 4, 2011 | Unregistered CommenterBrian Holyfield
Ammonite (http://ammonite.ryscc.com/) can generically detect Padding Oracle vulnerabilities.
April 28, 2012 | Unregistered CommenterTony
Wonderful explanation.
January 31, 2014 | Unregistered CommenterRich
Does ISO10126 prevent this kind of attack? Since the bytes in ISO10126 padding are random, you can't really tell what padding is valid and which is invalid right? Although, I've heard this padding can introduce a subliminal channel.
October 19, 2016 | Unregistered CommenterAnthony

PostPost a New Comment

Enter your information below to add a new comment.

My response is on my own website »
Author Email (optional):
Author URL (optional):
Post:
 
All HTML will be escaped. Hyperlinks will be created for URLs automatically.