Oracle Padding Attack Challenge

A friend of mine sent me a crypto challenge from an online course he was taking that I had a lot of fun solving. The details are available here. If you’re unfamiliar with how oracle padding attacks work or think they pertain to Oracle (proper noun), you should check out the following references and try to solve the challenge prior to reading the rest of this post.

http://esec-lab.sogeti.com/post/2010/12/03/Padding-Oracle-attack-and-its-applications-on-ASP.NET

http://blog.gdssecurity.com/labs/2010/9/14/automated-padding-oracle-attacks-with-padbuster.html

For this challenge, we’re given web server logs that appear to show an attacker exploiting this vulnerability. Our objective: to capture the secret data.

The logs show someone is brute forcing to determine when their guess results in the correct padding. In oracle padding attacks, the attacker needs to figure out what the indicator for a successful guess is. Sometimes it’s different page response, but in this case, it’s a 404 HTTP error response code. This lets us reduce the amount of log data we need to pay attention to since every 403 is just an incorrect guess and can be ignored.

$ egrep ' 404' proj4-log.txt 
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /202020202020202020202020202020d8cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /2020202020202020202020202020eddbcac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /20202020202020202020202020deecdacac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /202020202020202020202020ffd9ebddcac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /2020202020202020202020fbfed8eadccac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /2020202020202020202089f8fddbe9dfcac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /2020202020202020203c88f9fcdae8decac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /20202020202020207c3387f6f3d5e7d1cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /20202020202020057d3286f7f2d4e6d0cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404
...
...

We’ll come back to this later, but for now we can see the patterns where each byte is progressively, individually brute forced. We also notice the attacker has divided the original 80 byte encrypted string into 5 16-byte blocks and has prepended a starting block of 20’s to target the padding oracle specifically. Most algorithms divide data into 8 or 16 byte blocks, so this makes sense.

To more easily see what’s going on, we can split up the string into 16 byte chunks which show the attackers initial guesses. I’ve deliberately added spaces to the GET snippets throughout the rest of this write up to make visualization easier.

1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /20202020202020202020202020202001 cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 403
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /20202020202020202020202020202000 cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 403
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /20202020202020202020202020202003 cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 403
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /20202020202020202020202020202002 cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 403
…
…
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /202020202020202020202020202020d8 cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404

Though in slightly out of order, the attacker tried 01, 00, 03, 02.. and proceeded to continue incrementing the last byte by one until hitting the 404 response code; the successful padding guess. The first 404 (first line of our egrep) reveals the request that guessed the correct value to supply so that the decrypted last byte would be 0x01:

1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /202020202020202020202020202020d8 cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404

This means that when 0xd8 is supplied in the request and decrypted by the server, it will decrypt to 0x01 and the padding will be correct. So if we XOR 0xd8 and 0x1, we get 0xd9. We can now encrypt and decrypt arbitrary data for just that one byte by XOR-ing whatever we want with 0xd9.

>>> hex(0xd8 ^ 0x01)
'0xd9'

Now that we know 0xd9, we can guess that the attacker moved on to brute forcing the next byte to find out when the padding is correct for two bytes. To do that, the attacker needs to make the decrypted value come out to 0x02 0x02. We can do that only for the last byte ourselves since we know 0xd9:

>>> hex(0xd9 ^ 0x02)
'0xdb'

If we look at the raw logs to the line right after the initial successful guess, we see the attacker changes the last byte from 0xd8 to 0xdb and the brute force attack for the next byte begins:

1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /202020202020202020202020202020d8 cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /202020202020202020202020202002db cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 403

When that byte is discovered, we can move to 0x03, and so on. Since there are 16 bytes in our blocks, and there must be at least one byte of padding, the attack for each of the 5 blocks ends when a full block of padding is identified. After identifying this full block that can be XORed with 0x10’s, the attacker starts over with the next block:

1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /dce6acb565dd951c642b9feeebcdffc9 cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404 <- Got full block
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /20202020202020202020202020202001 084b0199778f14767cbdc989872a1f7d HTTP/1.1" 403 <- Starting over with next block

Looking through the logs is great actually because the attacker did all the work for us. We can ignore all of this byte-by-byte brute forcing and skip straight to the end of each block’s brute force where the full block of padding is identified. This is what the attacker was working towards anyways:

1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /dce6acb565dd951c642b9feeebcdffc9 cac544d7942e50e1a0afa156c803d115 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /afa631b5b91c019dd9dcd464e333b164 084b0199778f14767cbdc989872a1f7d HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /6b2866e615fb39441cccbdfdfe54684d a59da498c81017fd2adc534610b412e4 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /daffd5ebb46574cd5bbe267664c56c93 8f50d05513a440425f5ca434e5cb29c6 HTTP/1.1" 404
1.1.1.1 - [Sat Mar 31 18:20:41 2012] "GET /fa32af307095725b4645bd2dfcd230df b9110412ebeb347ee63a6b1849794f92 HTTP/1.1" 404

With these 5 lines of information, we have enough to decrypt the original string and solve the challenge. If you whip up a script to XOR the bytes of two blocks for you, you can start XORing stuff together. Or just do it interactively:

$ python
>>> 0xFFFFFFFF ^ 0x10101010
4025479151
>>> hex(0xFFFFFFFF ^ 0x10101010)
'0xefefefef'

We’ll build a quick list of intermediary values first, but note that to decrypt a block you XOR the intermediary value with the previous cipher text block (or IV for the first block) to get the clear text. The script used below just outputs the result of the XOR and also the corresponding ASCII.

We’ll XOR the results of the brute force against a full block of 0x10 padding for each of the 5 blocks.

$ python xor.py dce6acb565dd951c642b9feeebcdffc9 10101010101010101010101010101010
ccf6bca575cd850c743b8ffefbddefd9
????uͅ
     t;??????

$ python xor.py afa631b5b91c019dd9dcd464e333b164 10101010101010101010101010101010
bfb621a5a90c118dc9ccc474f323a174
??!??
     ????t?#?t

$ python xor.py 6b2866e615fb39441cccbdfdfe54684d 10101010101010101010101010101010
7b3876f605eb29540cdcadedee44785d
{8v??)T

       ܭ

$ python xor.py daffd5ebb46574cd5bbe267664c56c93 10101010101010101010101010101010
caefc5fba47564dd4bae366674d57c83
?????ud?K?6ft?|?

$ python xor.py fa32af307095725b4645bd2dfcd230df 10101010101010101010101010101010
ea22bf206085624b5655ad3decc220cf
?"? `?bKVU?=?? ?

Now, we start decrypting the original blocks by taking these results and XOR-ing it with the cipher text of the previous block (so we don’t actually need the first result from xor.py above).

$ python xor.py cac544d7942e50e1a0afa156c803d115 bfb621a5a90c118dc9ccc474f323a174
757365723d22416c696365223b207061
user="Alice"; pa

$ python xor.py 084b0199778f14767cbdc989872a1f7d 7b3876f605eb29540cdcadedee44785d
7373776f72643d2270616464696e6720
ssword="padding 

$ python xor.py a59da498c81017fd2adc534610b412e4 caefc5fba47564dd4bae366674d57c83
6f7261636c6573206172652064616e67
oracles are dang

$ python xor.py 8f50d05513a440425f5ca434e5cb29c6 ea22bf206085624b5655ad3decc220cf
65726f75732122999999999
erous!" 

Our decrypted string: user=”Alice”; password=”padding oracles are dangerous!”

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s