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.
R to denote the random prefix,
X for the input we would give to the oracle
(hereafter called the chosen plaintext)
T for target,
here is the situation we used to have:
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 == previous_blocks: # 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