July 25, 2019

Cryptopals Challenges: #7-8

In this challenge we are asked to implement and detect the AES-ECB system.

Cryptopals Challenges: #7-8

In this post we will complete Cryptopals challenges 7 and 8.  These challenges ask us to write code to encrypt data in AES-ECB mode and write a detection for AES in ECB mode.   Using crypto libraries, the code for these challenges is quite condensed.  The main focus of this blog post is to understand how AES-ECB is working for future reference.

AES-ECB

AES-ECB Encryption scheme. (From Wikipedia)

The AES-ECB system is a block-cipher encryption scheme.  This means the plaintext bytes are separated into blocksize of a pre-determined blocksize.  Each block is then encrypted under the AES-128 encryption under a static key.  Blocks must align with the blocksize, or be padded with extra bytes to align with the blocksize.  The standard blocksize for AES systems is 16 bytes.  One thing to to note about AES-ECB is that it is deterministic.  A block which is encrypted under a specific key will always result in the same ciphertext block.  By controlling which pieces of the plaintext comprise a block, we can launch many attacks against AES-ECB systems.

AES-ECB Decryption scheme. (From Wikipedia)

Decryption under AES-ECB is identical to the encryption scheme, except the ciphertext is fed to the AES decryptor.  Again, this makes the system deterministic and allows for the launching of many attacks.  For example, you can detect ECB mode easily (challenge 7),  decrypt unknown and inaccessible  texts (challenge 12), or craft ciphertext blocks to trick input validation systems (chalenge 13).  The inner workings of the AES encryption/decryption scheme are irrelevant when launching these attacks.  AES itself is secure, so most attacks are focused on the encryption schemes around the AES system.

The key takeaway from this section is that identical blocks will be encrypted identically.  If you truly understand that concept you will have no trouble with the AES-ECB problems.  To illustrate consider this example:

key:
"abcdefghijklmnop" (16 bytes)

plaintext:
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBB (32 bytes)

ciphertext blocks:
8c155e4e9bf78570ee6300dc5f8a418a
114beb8edd654f4c754c4078e195aca3

Changing the order of the plaintext to have the B's first gives:
114beb8edd654f4c754c4078e195aca3
8c155e4e9bf78570ee6300dc5f8a418a

Notice how the blocks were encrypted the same, but swapped position.  This illustrates the deterministic nature of AES-ECB.

Implementing AES-ECB

Using pycryptodome (Python3) or Crypto (Python2.7) we can easily implement AES-ECB using predefined libraries.  Since I learned Python with Python3, I use pycryptodome.  If you are using Python2.7, check the documentation on the Crypto library to see if any of the code is different.

from Crypto.Cipher import AES

def AES_ECB_Encrypt(plaintext, key):
    cipher = AES.new(key, AES.MODE_ECB)
    return(cipher.encrypt(plaintext))
    
def AES_ECB_Decrypt(key, ciphertext):
    cipher = AES.new(key, AES.MODE_ECB)
    return(cipher.decrypt(ciphertext))

That's it!  Both functions are fed byte strings for the plaintext/ciphertext  and key and they return a bytes object as the encryption.  To handle the bytes data types, here are the most common functions I use:

byte_string = b"This is a byte string we are manipulating"

#Converting to/from base64 bytes
base_64_representation = base64.b64encode(byte_string)
byte_string = base64.b64decode(byte_string)

#Converting to hex string
hex_representation = byte_string.hex()

#Converting back to bytes from hex string
byte_string = bytes.fromhex(hex_representation)

#All-purpose encode/decode for strings to bytes
string = "Convert this to a byte string"
bytes_string = bytes(string, 'utf-8')
bytes_string = string.encode()
string = bytes_string.decode()

Detecting AES-ECB

AES-ECB is detectible if the data encoded has two identical blocks.  If the plaintext does not have two identical blocks, it is not possible to detect ECB mode.  With that being said, we need to implement a duplicate checker.  The general strategy is as follows:

  1. Separate the ciphertext into chunks by taking blocks of 16 bytes
  2. Calculate the duplicates by taking the length of the ciphertext and subtracting the length of the set of unique strings in the ciphertext
  3. If duplicates are 1 or above, return True that ECB is used.

Python's set() command is very useful for this endeavor.  When called on an array, set() will return an array with all the unique values in the array.  For example set([1,2,3,1,2,3]) will return [1,2,3].  This means if we take the length of the original array (6) and subtract the length of the set (3) we get the number of duplicate values (3).  Thus, the code for detecting ECB is fairly simple:

def Is_ECB(ciphertext):
    chunks = [ciphertext[i*16:(i+1)*16] for i in range(int(len(ciphertext)/16))]

    duplicates = len(chunks) - len(set(chunks))


    if(duplicates >= 1):
        return True, duplicates
    else:
        return False

highest_duplicates = 0
line_counter = 0
AES_Cipher = b""

#For each line, attempt to find AES_ECB, if found, break from loop.
with open('8.txt') as fin:
	for line in fin:
    	line_counter += 1
    	ECB, duplicates = Is_ECB(line)
        
    	if(ECB):
        	AES_cipher = cipher
        	highest_duplicates = duplicates
        	line_number = line_counter
            break
    	

And with that, we are done with Set One of Cryptopals!  For the full repository of my solutions go the the Cryptopals repository on my github.