Italian Officers with Enimga

CBC Mode Padding Attack

by: burt rosenberg
at: university of miami
date: oct 2021

Overview

You are to implement the padding attack described in section 3.7.2 of the class text. This is one of a Padding-Oracle Attack which is proved successful in the wild. Theoretically, if the plaintext has some required structure, a randomly created ciphertext will decode to have or not have that structure. This serves as an oracle to extract information, and we show a manner of exploiting this.

There are two very important ways the project supports the instruction given by in this course. First, it provides an example of how a cipher strong in the CPA model can not be strong in the CCA model. Since encryption and decryption are mathematical inverses, it might be a surprise that CPA can differ from CCA. A padding oracle attack is an example to distinguish and motivate two different attack models.

Second, authenticated encryption is a requirement for a practical cipher. Our CPA ciphers have simple weaknesses not related to confidentiality. A practical cipher must address these weaknesses. The result is authentication schemes, which further differentiate encryption from decryption. In this exercise, we use padding to distinguish correct from incorrect ciphertexts. Given authenticated encryption, we cannot dismiss that there will be correct and incorrect ciphertexts. Therefore attacks on padding serve as models for attacks on any authenticated encryption scheme.

The book describes how to decrypt the last block of a three block ciphertext. Your project includes extending the attack to decrypt the remaining blocks in the ciphertext. However, your first goal is to undertake the books's attack, to obtain the first ring of accomplishment for this project.

Challenge One

Implement the attack on the last block of a padded encryption. Prove your method by decrypting the file challenge-one.enc.

Challenge Two

Implement the attack for a multiple block encryption. Prove your method by decrypting the file challenge-two.enc.

The attack

             Δ <-- the attack probe
             | 
             |
IV      c0   |    c1
|       |    |    |
|      (+)---+    |
|       |         |
|       +----+    |
|       |    |    | 
|     +---+  |  +---+
|     |   |  |  |   |
|     |D_k|  |  |D_k|
|     |   |  |  |   |
|     +---+  |  +---+
|       |    |    |
+------(+)   +---(+)
        |         |
        m0*       m1(+)Δ <-- the effect of the probe
                  |
            +------------+        +-- adjust Δ to
            | pad verify |        |   manipulate p
            |            |        |   adding result
            +------------+        |
                  |               V
                  +------------> accept/reject
      
**** Decrypt CBC mode and attack on final block ****
We are given a ciphertext (IV, c0, c1) and we wish to recover (m0, m1).

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.

The Padding Oracle

NAME
    Padding_Oracle

LIBRARY
    PYTHONPATH="../../class/modules:../modules" python3

SYNOPSIS
    from padding_oracle 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 key of type bytearray.
    
    zero_padding=[True|False] False is the default.
         If False pkcs #5 padding is added on encryption and removed on decryption.
         Else on encryption zero padding is used, and on decryption, the padding is retained.
         
    norandomness=[True|False] False is the default.
         If True, the IV is a bytearray of all zero.

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 input for correct padding.
             Returning True if padding is correct, False otherwise.
             
    get_block_size()
             Returns the block size.
        
    Encryption is AES-128 in CBC mode with PKCS padding.

HISTORY
    Introduced in csc609/507-201 october 2019
    Updated 2021 for csc609/507-221 with a change in the meaning -R, and get_block_size
        method added. A static print_bytearray utility method was added.

BUGS

The Assigment

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.
    
    For full credit, the attack is extended to all bytes in the message.
    
    The attack is against an AES-128 encoded message, encoded with CBC and PKCS padding.
    The program uses the Padding_Oracle module. The module has encrypt, decrypt and
    attack modes. See the Makefile for examples of the encrypt and decrypt modes and
    their options.

    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.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 6 oct 2019
update: 15 oct 2021