In [5]:
import os
import random
from random import randint
import base64

Challenge 14 - Byte-at-a-time ECB decryption (Harder)

Take your oracle function from #12. Now generate a random count of random bytes and prepend this string to every plaintext. You are now doing:

AES-128-ECB(random-prefix || attacker-controlled || target-bytes, random-key)

Same goal: decrypt the target-bytes.

Stop and think for a second: What's harder than challenge #12 about doing this? How would you overcome that obstacle? The hint is: you're using all the tools you already have; no crazy math is required. Think "STIMULUS" and "RESPONSE".

At first I read the instructions understanding that the random-prefix should be changed at every call to the oracle, including its length.

Looking at other people's solutions on the Internet, and reading the instructions again, it seems that it wasn't really what I was supposed to do: the random prefix should be generated once at the instanciation of the oracle, and stay the same accross all calls to the oracle.

Note that at least one person did read the same way I did:

https://github.com/SomMeri/matasano-cryptopals-solutions/blob/master/src/main/java/org/meri/matasano/Set2.java#L104

However I have a solution for when the prefix (and, most importantly, its length) changes every time, and it is much more interesting. So I will do both.

"Official" variant

We will first solve the challenge the way it was probably thought of by the authors, meaning with a constant prefix.

In [6]:
from libmatasano import encrypt_aes_128_ecb

class Oracle:
    def __init__(self):
        self.key = os.urandom(16)
        self.prefix = os.urandom(randint(1,15))
        self.target = base64.b64decode(
            "Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg"
            "aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq"
            "dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg"
            "YnkK"
        )
    
    def encrypt(self, message):
        return encrypt_aes_128_ecb(
            self.prefix + message + self.target,
            self.key
        )

At first we don't know the length of this prefix so we don't know how much padding we must add to have exactly one unknwown character in one block.

Using R to denote the random prefix, X for the input we would give to the oracle (hereafter called the chosen plaintext) and T for target, here is the situation we used to have:

XXXT TTTT

And now we have one of the following (with a block length of 4 for simplicity):

RXXX TTTT T
RRXX XTTT TT
RRRX XXTT TTT
RRRR XXXT TTTT

Here is what we do to tell which situation we are in, that is, what is the size of the unknown prefix:

We give some chosen plaintext of increasing length to the oracle. When we detect a block that does not change with the addition of one more byte of chosen plaintext, this means this block only contains prefix and chosen plaintext. We can reduce the size of chosen plaintext by two to have the kind of block we had in challenge 12. Here are an illustration of the step we go through:

RRTT TT
RRXT TTT
RRXX TTTT
RRXX XTTT T  *detected that first block did not change*
RRXT TTT     back to situation of challenge 12 
In [7]:
oracle = Oracle()

# Finding the block size (again)

previous_length = len(oracle.encrypt(b''))
for i in range(20):
    length = len(oracle.encrypt(b'X'*i))
    if length != previous_length:
        # got it !
        block_size = length - previous_length
        # the following quantities will be useful later to compute target length
        # where "aligned" means a length that is a  multiple of the block size
        size_prefix_plus_target_aligned = previous_length
        min_known_ptxt_size_to_align = i
        break
else:
    raise Exception('did not detect any change in ciphertext length')
    
# just checking we got it right
assert block_size == 16

# Finding the prefix size

from libmatasano import split_bytes_in_blocks

# XXX not ideal as
# this may not work if the prefix is larger than one block
# (cannot be the case the way we wrote our oracle, but just saying)
previous_blocks = None
for i in range(1, block_size+1):
    blocks = split_bytes_in_blocks(oracle.encrypt(b'X'*i), block_size)
    if previous_blocks != None and blocks[0] == previous_blocks[0]:
        # we are in the situation where
        # prefix_size + padding_size - 1 = block_size
        prefix_size = block_size - i + 1
        break
    previous_blocks = blocks
else:
    raise Exception('did not detect constant ciphertext block')
    
# just checking we got it right
assert prefix_size == len(oracle.prefix)

# now that we have the prefix size we can compute the size of the target
target_size = size_prefix_plus_target_aligned - min_known_ptxt_size_to_align - prefix_size

assert target_size == len(oracle.target)

# More or less same thing as in challenge 12

know_target_bytes = b""
for _ in range(target_size):
    # r+p+k+1 = 0 mod B
    r = prefix_size
    k = len(know_target_bytes)
    padding_length = (-k-1-r) % block_size
    padding = b"X" * padding_length

    # target block plaintext contains only known characters except its last character
    target_block_number = (k+r) // block_size
    target_slice = slice(target_block_number*block_size, (target_block_number+1)*block_size)
    target_block = oracle.encrypt(padding)[target_slice]

    # trying every possibility for the last character
    for i in range(2**8):
        message = padding + know_target_bytes + bytes([i])
        block = oracle.encrypt(message)[target_slice]
        if block == target_block:
            know_target_bytes += bytes([i])
            break

print(know_target_bytes.decode())
Rollin' in my 5.0
With my rag-top down so my hair can blow
The girlies on standby waving just to say hi
Did you stop? No, I just drove by

Non-constant Prefix Variant

TODO