Besides practicing attacks against ciphers, this attack has a special place in our curriculum. It shows that the approach of MAC-then-Encrypt does not always result in CCA security, even with a CPA secure encryption and a strongly unforgeable MAC.
The book describes how to decrypt the last block of a three block ciphertext. Figure out how to extend the attack to decrypt the second block (the first block being the IV and is not encrypted). Having accomplished this, you have the method for decrypting the entire message for an arbitrary length ciphertext.
As an implementation hint, first understand and code the technique shown in the book. Once done, you are in a better position to reason creatively about the rest of the attack.
In order for this attack to work, your implementation of CBC mode encryption must strictly verify the PKCS #5 padding. While one might find the attack unrealistic, as we seem to be implementing the cipher deliberately to enable this attack, the vulnerable implementation is typical of the actual cryptographic codes that secure our communications — from shopping to warfare. After completing the assignment, you will have a clearer understanding of the care needed when implementing crypto and will use cryptography properly.
Δ <-- the attack probe
|
|
IV c0 | c1
| | | |
| (+)---+ |
| | |
| +----+ |
| | | |
| +---+ | +---+
| | | | | |
| |D_k| | |D_k|
| | | | | |
| +---+ | +---+
| | | |
+------(+) +---(+)
| |
m0* m1(+)Δ <-- the effect of the probe
|
+------------+ +-- adjust Δ to
| pad verify | | manipulate padding result
+------------+ |
| V
+------------> accept/reject
**** Decrypt CBC mode and attack on final block ****
The diagram shows that the modified ciphertext (IV, c0⊕Δ, c1) will decrypt to (m0*, m1⊕Δ), where m0* is some unknown garbage. Focusing on m1⊕Δ, the attack first chooses Δ to determine the number of pad bytes, and then reads out the bytes of m1 one by one.
Determine the number of pad bytes by a process of elimination. If m1 is a block entirely of pad bytes, that a Δ that only affects the leftmost bytes will cause a padding error. If that Δ causes a reject, then stop. The number of pad bytes are known. Else try to eliminate the possibility that the number of pad bytes is one less than the block size. And so forth.
Once the padding is known, the bytes of m1 are extracted. The idea is to overwrite the padding bytes with a value numerically one larger, so that the last data byte is now thought to be padding. And then to modify that byte by a delta until it is the correct value for a padding byte. Once that is determined, continue leftwards with the next data byte.
The book does not describe now to continue the attack to read off bytes of m0. You will have to think this through, and decide how the attack can be done, and then do it. This is a second part of the assignment, for the purposes of grading.
NAME
Padding_Oracle
LIBRARY
PYTHONPATH="../../class/modules" python3
SYNOPSIS
from Proj4 import Padding_Oracle
po = Padding_Oracle(
key= [bytearray or None],
zero_padding= [True or False],
norandomness= [True or False])
_ciphertext_ po.encrypt(_plaintext_)
_plaintext_ po.decrypt(_ciphertext_)
_boolean_ po.padding_oracle(_ciphertext_)
CONSTRUCTOR
key= a bytearray key, or None (the default). If none, a random key is created.
zero_padding= True or False. If False (the default) pkcs padding is used.
else a non-standard zero padding is used.
norandomness= True or False (the default). If True, the IV's are always zero; and
the key is 16 bytes of zeros using
METHODS
encrypt([bytearray])
Encrypts plaintext argument,
Returning the ciphertext as a bytearray.
decrypt([bytearray])
Decrypts ciphertext argument,
Returning the plaintext as a bytearray.
padding_oracle([bytearray])
Checks the ciphertext inputfor correct padding.
Returning True if padding is correct, False otherwise.
Encryption is AES-128 in CBC mode with PKCS padding.
HISTORY
Introduced in csc609/507-201 october 2019
BUGS
NAME
padding_attack.py
SYNOPSIS
padding_attack.py [-v] [-m _mode_] key
DESCRIPTION
Implement the padding attack described in section 3.7.2 of Katz and Lindell.
The attack is against an AES-128 encoded message, encoded with CBC and PKCS padding.
The program uses the Padding_Oracle module found in the Proj4 library. Use the
PYTHONPATH environment variable to add the Proj4 library to the library path.
The program has helpful encrypt and decrypt modes, to encrypt or decrypt stdin to
stdout. The attack mode creates a Padding_Oracle object using the get of the argument,
and accepts from stdin an ciphertext encrypted with that key.
The attack mode decrypts stdin using only padding queries to the Padding_Oracle.
The key is used to construct the Padding_Oracle, but the attack code must not
call the decrypt method,
OPTIONS
-v verbose
-m mode of operation. the modes are specified by the argument to -m:
encrypt encrypts stdin to stdout using the key argument
decrypt decrypts stdin to stdout using the key argument
attack decrypts stdin to stdout not using the key argument for decryption.
author: burton rosenberg
created: 6 oct 2019
update: 22 oct 2019