Understanding Padding Oracle Attack - Attack on Encryption in CBC mode

Before we begin , a few terminologies that we should be familiar with. An Oracle is just a theoritical black box in Cryptography which responds to queries that an Adversary sends. For Example , a random Oracle would select and send a truly random value from a uniform distribution for each query that the Adversary sends to it. Propery implemented Crypto primitives behave like random Oracles ie even though the attacker intercepts any number of ciphertexts, he wont be able to derive any information whatsoever about the plain text. CBC (Cipher Block Chaining) is a mode that is secure against a adversary that can launch a chosen plaintext attack. CPA(Chosen Plaintext Attack) is where you can query the oracle with plaintexts(two at a time) of your choice and the Oracle will return the ciphertexts of either one and still the attacker wont be able to predict as to which plaintext the ciphertext belongs to.

Take a look at the following image(thanks to Wikipedia):



Basically what it means is that, at first a IV also called the Initialization Vector is chosen from a random distribution and xor'ed with the Plain Text and then subject to the Encryption function 'E' and the resulting CipherText is used as the IV for the next PlainText block.

Writing it as equation,

Co=E(k,m^IV) where '^' refers to the xor operation. Now we can see xor a lot in cryptographic primitives, the reason for that is , when we xor a value from any distribution with another value from a uniform random distribution, then the resulting distribution is also a uniform random distribution. From above, message does not belong to a uniform distribution whereas an IV belongs a uniform distribution but the resulting "m ^ IV" belongs to a uniform distribution.

Take a look at the following image(thanks again to Wikipedia) for the decryption:




Writing it again as equation,

As we know, Co=E(k,m^IV)
Applying decryption wrt 'k' on both sides,we have

D(k,Co)=m^IV

xor with IV on both sides (note that "A" ^ "A" == 0), so we have

m=D(k,Co) ^ IV

One of the caveats to remember here is that, if we modify IV as IV' such that IV'=IV ^ G, then the resulting plaintext message 'm' also gets xor'ed by G. Keep this mind as we proceed.
Now let's discuss about the padding in CBC assuming we use AES for encryption. Note that AES block size is 16 bytes. So if we have a block that is not a multiple of block size, say "abcdefghij" which is of size 10 bytes, we need to pad it to 16 bytes. The padding scheme that is generally used is to pad all the remaining bytes with the number of bytes missing. so it will be "abcdefhjij" + 0x6 0x6 0x6 0x6 0x6 0x6 (Notice that 0x6 is different from '6' tats why i made it this way). On decryption, we will look at the last byte , in this case it is 0x6, remove 6 bytes starting from the last byte to get out original message without the pad. Naturally, if we have a block that is a multiple of blocksize, we need to add a dummy padding block ' 0x16' repeated 16 times. See the image below to understand the padding scheme.(thanks to GDS Blog) Notice that they are using 3-DES for the encryption so block size is 8 bytes.




So what is padding oracle ?
The vulnerability occurs because of the types of error that previous implementations of SSL/TLS returned to the user, one is if the pad is invalid, it returned a Invalid Pad Error, if the pad is valid but the CT is not valid then it returns a Invalid Message Error. The attacker can query the pad and completely decrypt the Plain text. The following images from GDS blog does a great job of explaining it.Thanks guys!








What we need to do is , take the last byte of the IV, xor it with a value (G ^ 0x1),then it means that the message also will get xored by (G ^ 0x1) [remember the caveat i told you to keep in mind] , so if the PT's last byte too happens to be 'G' which can take any value from 0-255(a byte's possible values) , then we get a valid pad, since 0x1 is a valid 1-byte pad. To get the previous byte of the plaintext, we take the correct value of the last byte of the plaintext (lets call it 'P') and xor it with 0x2, and xor the last but previous byte of the IV with 'G' xor 0x2 because a valid 2-byte padding is '0x2 0x2' ie we fix the last byte and bruteforce the last but before byte till we get a valid pad.

There is a programming assignment @ Coursera's crypto class which deals with Padding Oracles,http://crypto-class.appspot.com/po?e...7dbf7035d5eeb4 . Our goal is to decrypt the ciphertext, the first 16 bytes are the IV (no need to decrypt them ofcourse). Below is a program I wrote in Python (I am kinda new to python so excuse the sloppiness) that decrypts the first 16 bytes of the message, the rest you can do if you are interested. Basically, if the pad is valid then the server responds with a 404 HTTP Error, else it responds with a 403 HTTP Error

This is the following link to the code : http://pastebin.com/kcN5i4Ze Not able to post the code here . am getting a .htaccess error for some reason! Mods can you look up the issue.


Comments are Welcome.

Best Regards and Peace