The journey continues. This time, I am looking at AES-CBC. Consider the scenario where we have an encryption oracle such that outputs ciphertexts , where denotes concatenation. The oracle uses PKCS7 padding and encrypts with fixed but unknown key 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): return open('/dev/urandom').read(k) def pkcs7pad(s,blksize=16): 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 , we obtain the encryption of We note the following:

- If the input is a fixed string, say, , with length 15 bytes (blocklength-1), we will include exactly one byte from the (unknown) plaintext . This block will be independent of the subsequent unknown plaintext bytes. For the sake of simplicity, assume that .
- So, if we query the oracle for all 256 strings , where runs over all possible bytes, we can compute a look-up table.
- We may then look at our first encryption and, using the look-up table from before, see which that satisfies the first block of . This determines the first byte of .
- 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.
- 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 !

Advertisements

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

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.