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:
Skärmavbild 2016-05-01 kl. 19.35.44
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 \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.}!

Advertisements

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

    1. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s