# Byte-wise decryption of AES-CBC

The journey continues. This time, I am looking at AES-CBC. Consider the scenario where we have an encryption oracle such that outputs ciphertexts $\Pi(s) = \textsf{Enc}_\text{AES}(s \| d, k) \rightarrow c$, where $\|$ denotes concatenation. The oracle uses PKCS7 padding and encrypts with fixed but unknown key $k$ and IV. The CBC-mode of operation is defined as follows: Embodied in Python code, the oracle is

from Crypto.Cipher import AES
import base64
import random

plaintext = b'''This is an encrypted message.'''
key = None
cprefix = None
iv = None

def randbytes(k):

missing = abs(len(s) - (len(s)/blksize+1) * blksize)
return s+(chr(missing)*missing)

def encryption_oracle(s):
global key
global iv
if key is None:
key = randbytes(16)
if iv is None:
iv = randbytes(16)
cipher = AES.new(key, AES.MODE_CBC, IV=iv)
s = pkcs7pad(bytes(s) + plaintext, 16)
return cipher.encrypt(s)


So, for instance, when querying the oracle with $\Pi(\texttt{We can break this!})$, we obtain the encryption of $\texttt{We can break this!This is an encrypted message.}$ We note the following:

1. If the input is a fixed string, say, $q = \texttt{aaaaaaaaaaaaaaa}$, with length 15 bytes (blocklength-1), we will include exactly one byte from the (unknown) plaintext $d$. This block will be independent of the subsequent unknown plaintext bytes. For the sake of simplicity, assume that $IV= \texttt{0x0}$.
2. So, if we query the oracle for all 256 strings $\texttt{aaaaaaaaaaaaaaa}\|x$, where $x$ runs over all possible bytes, we can compute a look-up table.
3. We may then look at our first encryption and, using the look-up table from before, see which $x$ that satisfies the first block of $\Pi(q)$. This determines the first byte of $d$.
4. This may repeated in several steps, until we find all bytes in the first block. Let us return to the IV issue implicitly stated earlier. We do not know the IV, but does that really matter? No! The IV will be constant in the first block and, thus, the input string fed into it. Now, as long as we can control the IV in the coming block (keep it constant), it has no effect on the result.
5. Using the same padding methodology as before, we may now compute the bytes of the coming block, but looking at the next block.

Again, with Python as our weapon of choice, we impale the decryption problem as follows

def attack(blocksize, known):
index = len(known) / blocksize
prefix = 'a'*(blocksize-len(known)%blocksize-1)
lookup = {}
for char in range(0, 256):
lookup[encryption_oracle(prefix+known+chr(char))[index*16:index*16+16]] = chr(char)
substring = encryption_oracle(prefix)[16*index:16*index+16]
if lookup.has_key(substring):
return lookup[substring]
else:
return None


Running this until we obtain a None-flag, i.e.,

plain = ''
while attack(16, plain) != None:
plain += attack(16, plain)
print 'Found plaintext:\n', plain


we obtain the sought plaintext $\texttt{This is an encrypted message.}$!

## 2 thoughts on “Byte-wise decryption of AES-CBC”

1. mangom0rot says:

Cool! If I’m not mistaken this would also work for AES-ECB, right?

1. Carl Löndahl says:

Yes, there is a trivial reduction to ECB (by setting IV=0x0 in each round). In fact, the ECB attack is one of the Matasano challenges which I completed a couple of days ago. I was somewhat surprised that this (CBC) was not mentioned there (or maybe I missed it), so therefore I decided to write it down.