September 8, 2019

Cryptopals Challenge #12 - Byte-at-a-time ECB decryption

In this post we look at the method for decrypting AES-ECB with a simple byte-at-a-time method.

Cryptopals Challenge #12 - Byte-at-a-time ECB decryption

For this challenge we are asked to emulate a situation in which we can append text to a preset plaintext.  We are given a string and are asked to append it to all submissions to the ECB oracle which was built in previous challenges.  Using this ability to concatenate our own text at the beginning of the appended string, we are asked to decode the string.

The oracle will return the output of AES-128( input || unknown, key).  Since AES-ECB is deterministic, we will exploit this fact by making the least significant byte of our input a byte from the plaintext. How does this work?

  1. Assume the blocksize is 4.
  2. If we feed block = "AAA(Byte)" to the oracle we now know AES-128(block, key)
  3. We can make a dictionary which matches each ciphertext to a block "AAA(Byte)"
  4. Using this dictionary, we send many blocks to the oracle and match them to the dictionary

So our first task is to create a function which will generate the dictionary for us.  After we do that, we will take each byte from the plaintext we are trying to decode and match it to a point in the dictionary.

Creating the Dictionary

The steps for creating the dictionary are as follows:

  1. Create a block consisting of 15 A's.
  2. For each character from 0-127, append to the block
  3. Encrypt using the oracle
  4. Take the last byte of the encryption and match that byte to the character 0-127
def GenerateDictionary(blocksize, key, plaintext):
    byte_dictionary = {}

    for i in range(127):
        #Create the block such as "AAAAAAAAAB"
        plaintext += chr(65).encode() * (blocksize-1) + chr(i).encode()

        #Encrypt the data
        ciphertext = AES_ECB_Encrypt(plaintext, key)

        #Break the data into an array of bytes
        bytes = [ciphertext[i:i+2] for i in range(0,len(ciphertext),2)]

        #Take the last byte and add it to the dictionary
        byte_dictionary[bytes[len(bytes)-1]] = chr(i)

    return (byte_dictionary)

Cracking the Ciphertext

When I solved this problem, I actually interpreted the problem statement incorrectly.  I thought we were allowed to append any number of bytes from the plaintext to our input.  This simplifies the problem because we can just use a simple dictionary lookup for each byte in the plaintext.

def CrackCiphertext(key, blocksize, plaintext, payload):
    dictionary = GenerateDictionary(blocksize, key, payload)
    word = ""
    
    #For each byte in the plaintext, find the letter it corresponds to
    for byte in plaintext:
    
    	#Craft a block with all "A" + the byte we are looking for
        payload += chr(65).encode() * (blocksize-1) + bytes([byte])
        
        #Encrypt with the oracle
        ciphertext = AES_ECB_Encrypt(payload, key)
        
        #Get the bytes
        byte_array = [ciphertext[i:i+2] for i in range(0,len(ciphertext),2)]
        
        #Append the last bytes corresponding plaintext form to the word
        word += (dictionary[byte_array[len(byte_array)-1]])
        
    print(word)

We can then run this by sending:

plaintext = base64.b64decode(GetData("12.txt"))
blocksize = 16
payload = b""

CrackCiphertext(key, blocksize, plaintext, payload)

The Correct Way

However, this approach is not exactly what was meant by the problem.  As I wrote earlier, we are meant to append the full plaintext each time we send an input.  This complicates the process a little bit by forcing the generation of a new dictionary each time we find a known byte.

  1. Say you have a plaintext "Decrypt!" with a blocksize of 4, so there are two blocks
  2. Generate a dictionary using AAA(Byte)
  3. Send "AAADecrypt!" to the oracle and match the first blocks last byte with "D"
  4. Now we need to get the next byte, so we generate a dictionary using AAD(Byte)
  5. We repeat until we have "Decr"
  6. Once we have "Decr", we use this as our offset tool
  7. Generate a dictionary with "ecr(Byte)"
  8. Send a block such that the second block is "ecr(Byte)" --> "AAA"
  9. Match the last byte of the second block to a plaintext form