Proj X4 for CNIT 123: Padding Oracle Attack (15 pts. + 20 pts. extra credit)

What You Need

Any machine with Python 2.7. I used a Mac. The easiest machine to set up is probably Kali or Ubuntu Linux.

Purpose

To learn how the Padding Oracle attack works against AES-CBC.

Background

Encrypting 48 Bytes

Cipher Block Chaining is diagrammed below (image based on one from Wikipedia).

Three blocks of plaintext (green), each 16 bytes long, are encrypted, producing three blocks of ciphertext (yellow).

The first block is XORed with an initialization vector or iv (blue), also 16 bytes long, and then encrypted with the key.

Each subsequent block is XORed with the previous block of ciphertext. Encrypting 47 Bytes

Suppose the plaintext is only 47 bytes long. In that case, a byte of padding (purple) must be added, as shown below. Decryption

Using the same key and iv (blue), the ciphertext (yellow) can be decrypted to find the plaintext (green). The last byte is the padding (purple), as shown below. A common system of padding is Public Key Cryptography Standard #7, or PKCS #7. It works like this:
• If one byte of padding is needed, use 01
• If two bytes of padding are needed, use 0202
• If three bytes of padding are needed, use 030303
• ...
• If fifteen bytes of padding are needed, use 0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
• If no bytes of padding are needed, add an entire block of sixteen chr(16) characters, or 10101010101010101010101010101010
So in the diagram above, this Python condition is true:
plaintext == chr(1)

Modifying a Byte of Ciphertext

Suppose we modify:
ciphertext
That will garble the whole second block of plaintext:
plaintext[16:32]
But it will only change a single byte of the third block:
plaintext
This is shown below, with red indicating changed bytes. Demonstration in Python

Starting Python

Open a Terminal or Command Prompt and execute this command to open Python in interactive mode:
python

Setting Initial Values

Enter these commands to prepare the environment for encryption, as shown below.
from Crypto.Cipher import AES
key = "0000111122223333"
iv = "aaaabbbbccccdddd"
cipher = AES.new(key, AES.MODE_CBC, iv)
a = "This simple sentence is forty-seven bytes long."

Enter these commands to pad the sentence and encrypt it, placing the result in "ciphertext", and make a modified ciphertext string named "mod" with ciphertext changed to chr(255), as shown below.
ciphertext = cipher.encrypt(a + chr(1))
mod = ciphertext[0:31] + chr(255) + ciphertext[32:]

Viewing the Modified Ciphertext

Enter these commands to print the original and modified ciphertext in hexadecimal encoding, so it is eash to see the single byte that is changed, as highlighted in the image below.
print ciphertext.encode("hex")
print mod.encode("hex")

Viewing the Decrypted Text

Enter these commands to decrypt the original and modified ciphertext, printing the results in hexadecimal encoding. As highlighted below, the second block and the padding byte change, but nothing else.
print cipher.decrypt(ciphertext).encode("hex")
print cipher.decrypt(mod).encode("hex") Making a Vulnerable System

This is a simple AES-CBC implementation that encrypts and decrypts. If the decrypted text is not properly padded, it returns an error message. This is the way many encryption implementations have been written.

Use a text editor, such as nano or Notepad, to make this file. Save it as pador.py in your home directory.

from Crypto.Cipher import AES
key = "aaaabbbbccccdddd"
iv = "1111222233334444"

def decr(ciphertext):
cipher = AES.new(key, AES.MODE_CBC, iv)
return ispkcs7(cipher.decrypt(ciphertext))

def ispkcs7(plaintext):
l = len(plaintext)
c = ord(plaintext[l-1])
if (c > 16) or (c < 1):
if plaintext[l-c:] != chr(c)*c:
return plaintext

def encr(plaintext):
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(pkcs7(plaintext))
return ciphertext

def pkcs7(plaintext):
padbytes = 16 - len(plaintext) % 16 Starting Python

Open a Terminal or Command Prompt and execute this command to open Python in interactive mode:
python

Encrypting a 47-Byte Plaintext

Enter these commands to encrypt a sentence, and show the encrypted string in hexadecimal encoding, as shown below.
a = "This simple sentence is forty-seven bytes long."
c = encr(a)
print c.encode("hex")
As shown below, the encrypted string is a long random series of hexadecimal values. Decrypting the Ciphertext

Enter these commands to decrypt the ciphertext, and show the result in ASCII and in hexadecimal encoding, as shown below.
d = decr(c)
print d
print d.encode("hex")
The decrypted string ends in "01", a single byte of padding. It's not printable, so it can't be seen in the ASCII version, but it's visible in the hexadecimal version, as highlighted in the image below. Enter these commands to modify the ciphertext and decrypt the modified ciphertext, as shown below.
mod = c[0:47] + chr(65)
decr(mod)
Enter this command decrypt the original ciphertext, as shown below.
decr(c)
As shown below, an error message appears when the padding is incorrect, but not when it is correct.

This seemingly harmless error message is enough to completely defeat the encryption, because it can be used to leak out information about the encryption process. Problem Statement

Your goal is to create a valid encrypted message including this word:
WIN
You need to encrypt it with AES-CBC, but you don't know the IV or the key.

You have a single example of encrypted text, and a system that will let you test encrypted text and tell you whether the padding is correct or not.

This should be impossible, but it can be done using the padding oracle attack.

Goal: Intermediate State

Consider the intermediate state shown in the figure below, with one block colored orange. This 16-byte value, intermediate[32:48], depends only on the key and the third block of ciphertext.

If we can figure out the intermediate state, we can create ciphertext that decrypts to any plaintext we want in the third block. We do that by modifying the second block.

We don't need to know the key or the iv. Here's how we can find the last byte of the intermediate state.

2. Replace ciphertext[16:32] with any random bytes. This will change the second and third blocks of plaintext, including the last byte of plaintext, plaintext, which is colored red in the figure below.

The padding of the plaintext will now be invalid, unless plaintext is 1. (There's a small chance that it might be valid in other ways, but let's ignore that for now.)

3. Try all possible byte values for ciphertext until a valid padding is found. Now we know that plaintext is 1.

4. The last intermediate byte is the XOR of those values:

ciphertext ^ 1 After 256 guesses, we get one byte of the intermediate value. We can continue in this fashion until we get them all, except for the first block.

Getting a Valid Ciphertext

In your Python session, execute these commands to encrypt a sentence containing "I'M A LOSER", and place the value in a variable named "original".
a = "This sentence cleaarly says I'M A LOSER."
original = encr(a)
print original.encode("hex")
As shown below, the ciphertext is a string of 48 random bytes. Now we are ready to perform the attack in four stages, as detailed below.

Stage 1. Finding Intermediate

Performing 5 Modifications

In your Python session, execute these commands to try five values for ciphertext. Press Enter twice after the last line of text.
for i in range(5):
mod = original[0:31] + chr(i) + original[32:]
print i, decr(mod)

As shown below, all the modifications result in "PADDING ERROR" messages. Finding Valid Values

In your Python session, execute these commands to try all 256 possible values for ciphertext. Press Enter twice after the last line of text.
for i in range(256):
mod = original[0:31] + chr(i) + original[32:]

As shown below, there are two valid values.

One of these is the original byte, which results in a correct string of padding bytes, and the other one results in a final byte of 1, which is interpreted as a correct padding string one byte long. Execute this command to see the original value of ciphertext.

print ord(original)
As shown below, the original byte is 154. So the other value, 147, must result in a plaintext value of 1. This was effective, but it would be better to find the value directly, instead of finding two possibilities and needing to choose between them.

Filling Ciphertext[16:31] with "A"

In your Python session, execute these commands to fill the 15 bytes from c through c with "A" characters, and then test all 256 possible values for ciphertext. Press Enter twice after the last line of text.
prefix = original[0:16] + "AAAAAAAAAAAAAAA"
for i in range(256):
mod = prefix + chr(i) + original[32:]

As shown below, the correct value of 147 is found. This worked because the modified ciphertext creates random bytes of cleartext, which won't end in valid padding unless the final byte is 1. Filling Ciphertext[16:31] with "B"

In your Python session, execute these commands to fill the 15 bytes from c through c with "B" characters, and then test all 256 possible values for ciphertext. Press Enter twice after the last line of text.
prefix = original[0:16] + "BBBBBBBBBBBBBBB"
for i in range(256):
mod = prefix + chr(i) + original[32:]

As shown below, the correct value of 147 is found. Almost any values can be used to fill ciphertext[16:31] and the attack will work. Calculating Intermediate

From the diagram below, we can see that this is how the last byte of the cleartext is calculated:
ciphertext ^ intermediate = plaintext Applying ciphertext ^ to both sides of this equation yields:

ciphertext ^ ciphertext ^ intermediate = ciphertext ^ plaintext
Rearranging terms yields:
intermediate ^ ciphertext ^ ciphertext = ciphertext ^ plaintext
On the left side, intermediate is XORed with a byte, and then XORed again with the same byte. XOR is its own inverse--XORing twice with the same byte gets you back where you started, so:
intermediate = ciphertext ^ plaintext
And we know that plaintext must be 1 to make the padding valid, so, when the padding is valid,
intermediate = ciphertext ^ 1 = 147 ^ 1 = 146
So now we know this:
intermediate = 146

Stage 2. Finding Intermediate

To find intermediate, we can't use the situation with a single padding byte of 1. Instead, we need to set up a situation with two padding bytes of 2 at the end, plaintext and plaintext, as shown below. Making plaintext Equal 2

We know these two values:
intermediate = 146

plaintext = 2

So we need to use this value of ciphertext:
ciphertext = 146 ^ 2 = 144

Trying All Values for ciphertext

In your Python session, execute these commands to fill the 14 bytes from c through c with "B" characters, and then test all 256 possible values for ciphertext, using 144 for ciphertext. Press Enter twice after the last line of text.
prefix = original[0:16] + "BBBBBBBBBBBBBB"
for i in range(256):
mod = prefix + chr(i) + chr(144) + original[32:]

As shown below, the answer is 6. Calculating Intermediate

We know that when ciphertext=6, plaintext=2 (required to make the padding valid).

We can now calculate Intermediate

intermediate = ciphertext ^ plaintext = 6 ^ 2 = 4
So now we know this:
intermediate = 4
intermediate = 146

Stage 3. Finding Intermediate

To find intermediate, we need to set up a situation with three padding bytes of 3 at the end, plaintext, plaintext, and plaintext.

Making plaintext and plaintext Equal 3

We know these values:
intermediate = 4
intermediate = 146

plaintext = 3
plaintext = 3

So we need to use these values for ciphertext and ciphertext:
ciphertext = 4 ^ 3 = 7
ciphertext = 146 ^ 3 = 145

Trying All Values for ciphertext

In your Python session, execute these commands to fill the 13 bytes from c through c with "B" characters, and then test all 256 possible values for ciphertext, using the values found above for ciphertext and ciphertext.

Press Enter twice after the last line of text.

prefix = original[0:16] + "BBBBBBBBBBBBB"
for i in range(256):
mod = prefix + chr(i) + chr(7) + chr(145) + original[32:]

As shown below, the answer is 102. Calculating Intermediate

We know that when ciphertext=102, plaintext=3 (required to make the padding valid).

We can now calculate Intermediate

intermediate = ciphertext ^ plaintext = 102 ^ 3 = 101
So now we know this:
intermediate = 101
intermediate = 4
intermediate = 146

Stage 4. Finding Intermediate

To find intermediate, we need to set up a situation with four padding bytes of 4 at the end, plaintext, plaintext, plaintext, and plaintext.

Making plaintext, plaintext, and plaintext Equal 4

We know these values:
intermediate = 101
intermediate = 4
intermediate = 146

plaintext = 4
plaintext = 4
plaintext = 4

So we need to use these values for ciphertext, ciphertext, and ciphertext:
ciphertext = 101 ^ 4 = 97
ciphertext = 4 ^ 4 = 0
ciphertext = 146 ^ 4 = 150

Trying All Values for ciphertext

In your Python session, execute these commands to fill the 12 bytes from c through c with "B" characters, and then test all 256 possible values for ciphertext, using the values found above for ciphertext, ciphertext and ciphertext.

Press Enter twice after the last line of text.

prefix = original[0:16] + "BBBBBBBBBBBB"
for i in range(256):
mod = prefix + chr(i) + chr(97) + chr(0) + chr(150) + original[32:]

As shown below, the answer is 235. Calculating Intermediate

We know that when ciphertext=235, plaintext=4 (required to make the padding valid).

We can now calculate Intermediate

intermediate = ciphertext ^ plaintext = 235 ^ 4 = 239
So now we know this:
intermediate = 239
intermediate = 101
intermediate = 4
intermediate = 146

Stage 5: Encoding WIN

We know this:
intermediate = 239
intermediate = 101
intermediate = 4
intermediate = 146
We want this plaintext, ending with "WIN" and a correct single byte of 1 for padding:
cleartext = ord("W")
cleartext = ord("I")
cleartext = ord("N")
cleartext = 1
So we choose these ciphertext bytes:
ciphertext = cleartext ^ intermediate = ord("W") ^ 239
ciphertext = cleartext ^ intermediate = ord("I") ^ 101
ciphertext = cleartext ^ intermediate = ord("N") ^ 4
ciphertext = cleartext ^ intermediate = 1 ^ 146
Execute these commands to calculate and insert those bytes (it's a little clumsy because Python doesn't let you assign a byte inside a string):
c28 = ord("W") ^ 239
c29 = ord("I") ^ 101
c30 = ord("N") ^ 4
c31 = 1 ^ 146

ciphertext = original[0:28] + chr(c28) + chr(c29) + chr(c30) + chr(c31) + original[32:]

Decrypting the New Ciphertext

Execute this command to decrypt your crafted cypertext. It should end with "WIN", as shown below.
decr(ciphertext) Saving a Screen Image (Image X4A)

Make sure you can see WIN, as shown above.

Capture a full-screen image.

YOU MUST SUBMIT A FULL-SCREEN IMAGE FOR FULL CREDIT!

Save the image with the filename "YOUR NAME Proj X4a", replacing "YOUR NAME" with your real name.

Challenge: Winners Board (20 pts. extra credit)

Setup

Open a Terminal window and execute these commands:

python
In the Python shell, execute these commands:
a = "3ceafc6720f418f86b937a14fa0703df352b04f7d1e6a1e3bdd2e6f36e3da543800a6b07b3db36b372e934dfeeb2d920"
decr(a)

c="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
decr(c)
The first string should return 'Error: no name included ', and the second one should return 'PADDING ERROR ', as shown below. This ciphertext is valid:

3ceafc6720f418f86b937a14fa0703df352b04f7d1e6a1e3bdd2e6f36e3da543800a6b07b3db36b372e934dfeeb2d920
It decodes to this string:
Put this name on the winners board: EXAMPLE
It gives an error message because a name cannot begin with a space.

To get on the winners board, send ciphertext in hex that decodes to a string ending in :YOURNAME with correct padding.

Use the form below to put your name on the WINNERS PAGE.

 Ciphertext like this: 3ceafc6720f418f86b937a14fa0703df352b04f7d1e6a1e3bdd2e6f36e3da543800a6b07b3db36b372e934dfeeb2d920

Saving a Screen Image (Image X4B)

Save a whole-screen image of the winners page showing your name, as shown below, with the filename "YOUR NAME Proj X4b". 