Padding Oracle Attack with AES-128-CTR and MAC

Question

Assume Alice and Bob are communicating using 'MAC then Encrypt' paradigm. Specifically, they are using HMAC with SHA256 as the hash function and the output is truncated to 40 bits. They are using AES-128 in CTR mode as the blockcipher. Specifically, they do the following:

C=<IV, ENC(M II MAC(M, IV PAD) II PAD)>

I understand this. If we consider the message is 200 bits long. So the first block has 128 bits, the second block has 72 bits of the message, 40 bits of MAC and 16 bits padding. Padding scheme: 16 bits is 2 bytes (0X02). (0X0Z) for all Z bytes.

What I want to know is that if Eve has no idea that the original message is 200 bit long, but Eve knows it's 2 blocks long after 40 bit MAC was added and it is padded.

How will Eve know the length of the message? Will it be done by flipping the last bit and looking for padding error and using the padding algorithm? Or will we try padding oracle attack??

Answer 1

Finding the message size knowing the padding size

With CTR mode the length of the ciphertext is the same as the length of the plaintext, because what you do is XORing bit-by-bit the message with the keystream.

So the length of the second component of C minus the padding length and MAC length is the length of the message.

Quick Python example:

import os

# https://cryptography.io
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes, hmac
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

backend = default_backend()

M = os.urandom(200//8)
MAC_KEY = os.urandom(hashes.SHA256.digest_size)
PAD = bytes([0x02,0x02])
AES_KEY = os.urandom(32)
IV = os.urandom(16)

h = hmac.HMAC(MAC_KEY, hashes.SHA256(), backend=default_backend())
h.update(M + IV + PAD)
# truncated to 40 bits = 5 bytes
MAC = h.finalize()[:5]

cipher = Cipher(algorithms.AES(AES_KEY), modes.CTR(IV), backend=backend)
encryptor = cipher.encryptor()
C = (IV, encryptor.update(M + MAC + PAD) + encryptor.finalize())

print('length of message: %i bits' % (8*(len(C[1]) - len(PAD) - len(MAC))))
# out: length of message: 200 bits

Finding the padding size using the oracle

EDIT: added this question from comment of OP.

Another property of CTR mode is that flipping a bit in the ciphertext flips the corresponding bit in the plaintext.

So if you flip say the last bit of C[1] you will modify the padding and get a "padding error"; while if you flip a bit that correspond to MAC you get a "MAC error".

As a result if flipping the i-th bit gives you a "MAC error" while flipping the i+1-th bit gives you a "padding error" then the padding starts at bit i+1 and you gets the padding length and its value.

Continuing my Python example:

class PaddingError(Exception):
    pass

class MacError(Exception):
    pass

def oracle(ctxt):
    decryptor = cipher.decryptor()
    ptxt = decryptor.update(ctxt) + decryptor.finalize()
    m = ptxt[:25]
    mac = ptxt[25:30]
    pad = ptxt[30:]

    # i'm cheating
    if pad != PAD:
        return PaddingError
    elif mac != MAC:
        return MacError
    elif m != M:
        return 'Message was modified'
    else:
        return 'OK'

def flip(x, i):
    "returns x with its i-th bit flipped (starts at 0)"
    mask = 2**(7-(i%8))
    return bytes([ x[j]^mask if j==(i//8) else x[j] for j in range(len(x)) ])

oracle(flip(C[1], len(C[1])*8-16))
# out: PaddingError

oracle(flip(C[1], len(C[1])*8-17))
# out: MacError

Finding the last byte of the MAC

EDIT added from another comment of OP

When you know the padding length, you know where is the last byte of the MAC, and because of the CTR mode you are able to modify it by XORing it against some byte of your choice.

So you pick a random byte and you XOR it against the last byte of the MAC, and you send the result to the oracle.

Normally you should get a "MAC error", but if the modified MAC byte ends up being the same as the PAD bytes (for instance 0x02 in your example) you should get a "Padding error" instead.

Let B be the byte you used to get this "Padding error", we now know that:

MAC[-1] ^ B = 0x02

(where ^ denotes bit-wise XOR as in Python)

Thus:

MAC[-1] = 0x02 ^ B