import os
import random
from random import randint
import base64
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:
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.
We will first solve the challenge the way it was probably thought of by the authors, meaning with a constant prefix.
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 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())
TODO