Assignment #1 - CBC padding oracles

In his seminal paper from 2002, Serge Vaudenay [1] introduced the padding oracle attack against CBC decryption using the PKCS#7 padding algorithm. In this homework assignment you will mount this attack as well as its extension (CBC-R encryption [2]), to first recover a secret message and then encrypt a message yourself (without having the secret key of course).

CBC mode and PKCS#7 padding

In CBC (Ciphertext Block Chaining) mode of encryption, previous ciphertext block gets XORed into a plaintext block before it is encrypted (see the figure below). Since there is no previous ciphertext block when the first plaintext block is processed, an IV (Initialization Vector) is used instead. This IV is picked uniformly at random during each encryption and is transmitted along with the ciphertext (it forms its first block).

In CBC decryption, this XORing is reversed and so the IV gets XORed to the first block-decryption result, producing the first plaintext block (see the figure below).

Diagram of CBC mode encryption.

Diagram of CBC mode decryption.

In PKCS#7 padding, when $n$ bytes are missing to pad the message to the block length of the underlying block cipher, the byte value of $n$ is added $n$ times at the end. When the message to be padded is already a multiple of the block length a full block of padding is added. This is to ensure that the padding is always removable.

See below for some examples of padding for AES-128, where the block length is 16 bytes. Note they use Python byte string format and \x07 stands for a byte with the hexadecimal value 0x07.

Task

In this homework assignment, you will have access to a ciphertext that contains a secret message encrypted under a secret key using AES-CBC with PKCS7 padding. You will also have access to a function that performs AES-CBC decryption and unpadding using the same secret key that tells you some information about the resulting plaintext. There are two tasks to this homework assignment. You should solve them in the presented order.

1. Decrypt the ciphertext

In task 1, your goal is to decrypt the ciphertext obtained from the first API endpoint, using a CBC decryption padding oracle constructed using the second endpoint.

The secret message consists of 4 English words in ASCII separated by space.

2. Encrypt another message

In task 2, your goal is to use the extension to the CBC padding oracle attack, called CBC-R encryption, to encrypt a message b"I can encrypt <UCO>", with <UCO> replaced with your UCO (Univerzitní Číslo Osoby), using the secret key used by the server for your two endpoints.

API

There are two API endpoints available to you. One that gives you your ciphertext (that you want to decrypt for task 1) and one that does AES-128-CBC decryption of any ciphertext you give it and tells you about its result (you want to use this endpoint for both tasks). The secret key used in both endpoints is the same and it is fixed. However, it and the plaintext message encrypted is unique for each student.

Submission

You should submit a zip-file containing three things:

• A solution.txt file that contains two lines:
  • the secret message you were supposed to obtain (i.e, four space-separated words in ASCII).
    • Do not put the words on separate lines.
    • Do not put tabs or more than one space between the words.
  • the ciphertext which decrypts (using AES-128-CBC with PKCS#7 padding) to the message b"I can encrypt <UCO>" using the secret key used by the server for your two endpoints.
    • The ciphertext should be in hexadecimal and on one line.
• A description.txt file that contains your description of how you solved the task (i.e. what you did in order to obtain the secret message, how you came up with it, etc.). Please keep the descriptions reasonably short and clear (4-5 paragraphs should be enough).
• A code directory that contains any source code used in solving the task.

An example solution.txt could read:

correct horse battery staple
d968e59dbcafd35ecafaa3a460311e012dccdb5a1597d76d30017f2024fc8d54

An example description.txt could read:

I first lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod
tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo
consequat.

Then I at lectus urna duis convallis. Est sit amet facilisis magna etiam tempor
orci eu. Dui nunc mattis enim ut tellus elementum. Urna id volutpat lacus
laoreet non curabitur gravida. Praesent semper feugiat nibh sed pulvinar proin
gravida hendrerit lectus. In metus vulputate eu scelerisque felis imperdiet
proin. Integer quis auctor elit sed vulputate.

Since I knew that, pharetra et ultrices neque ornare aenean euismod elementum.
Non sodales neque sodales ut etiam. Aliquet eget sit amet tellus cras adipiscing
enim eu turpis. Aliquet porttitor lacus luctus accumsan tortor. Ullamcorper
morbi tincidunt ornare massa eget. Iaculis urna id volutpat lacus.

Then finally, the thing returned mauris vitae ultricies leo integer malesuada
nunc vel risus. Faucibus turpis in eu mi bibendum neque egestas congue. Non quam
lacus suspendisse faucibus interdum posuere lorem. Vulputate ut pharetra sit
amet. Congue mauris rhoncus aenean vel elit. Lacinia quis vel eros donec ac.
Pretium viverra suspendisse potenti nullam ac tortor vitae. Risus nec feugiat in
fermentum posuere urna nec tincidunt.

Tips

In order to make solving this assignment easier we provide a Python file mwe.py that implements several functions that will help you. You can use the functions local_encrypt and local_decrypt to experiment with and test your solution as you develop it. These functions are used by the server to implement the API, so the server should behave exactly the same. You can also use the functions get_ciphertext and try_decrypt to interact with the server.

Grading

The recovery of the correct secret message is worth 5 points, the correct encryption of the message b"I can encrypt <UCO>" is worth another 3 points and the description is worth the remaining 2 points. However, a submission with no description is worth 0 points. Not conforming to the above format of the solution leads to a -0.5 point penalty.