So after procrastinating a lot solving some of the hard problems from CyLab (f.k.a PicoCTF), I decided to go back and try my hand at the last challenges from its cryptography path. This is the first one of said series.
Description
This encryption algorithm leaks a "bit" of data every time it does a computation. Use this to figure out the encryption key.
Code
1#!/usr/bin/env python3
2import random, sys, time
3
4with open("key.txt", "r") as f:
5 SECRET_KEY = bytes.fromhex(f.read().strip())
6
7Sbox = (
8 0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
9 0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
10 0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
11 0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
12 0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
13 0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
14 0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
15 0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
16 0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
17 0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
18 0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
19 0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
20 0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
21 0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
22 0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
23 0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
24)
25
26# Leaks one bit of information every operation
27leak_buf = []
28def leaky_aes_secret(data_byte, key_byte):
29 out = Sbox[data_byte ^ key_byte]
30 leak_buf.append(out & 0x01)
31 return out
32
33# Simplified version of AES with only a single encryption stage
34def encrypt(plaintext, key):
35 global leak_buf
36 leak_buf = []
37 ciphertext = [leaky_aes_secret(plaintext[i], key[i]) for i in range(16)]
38 return ciphertext
39
40# Leak the number of 1 bits in the lowest bit of every SBox output
41def encrypt_and_leak(plaintext):
42 ciphertext = encrypt(plaintext, SECRET_KEY)
43 ciphertext = None # throw away result
44 time.sleep(0.01)
45 return leak_buf.count(1)
46
47pt = input("Please provide 16 bytes of plaintext encoded as hex: ")
48if len(pt) != 32:
49 print("Invalid length")
50 sys.exit(0)
51
52pt = bytes.fromhex(pt)
53print("leakage result:", encrypt_and_leak(pt))
Writeup
So what the code gives you is the sum of all elements of the resulting array leaky_buf. This leaky_buf array is the last bit of Sbox[data_byte ^ key_byte] for the first 16 bytes of the plaintext and the key. In other words, given a plaintext of 16 bytes, we obtain the counts of first turned-on bits of the array [Sbox[data_byte[0] ^ key_byte[0]], Sbox[data_byte[1] ^ key_byte[1]], Sbox[data_byte[2] ^ key_byte[2]] ... Sbox[data_byte[15] ^ key_byte[15]]]. Clearly, a headache to crack.
What we can do is to try to bruteforce the key. Let’s focus on the last byte that gets processed and set all the others to 0x00 in the plaintext. We iterate through all the possible values for the last byte, 0x00 to 0xFF, and send them to the oracle. We will get an array of integers like [8, 3, 4, 0, 6...]. Clearly, there’s only one possible last byte of the key that will get you this result. So, again, we try to iterate all values of possible keys with all values of possible plaintext. That is, we derive all possible arrays of integers of plaintexts that end with 0x00 to keys that end with 0x00, then 0x01, then 0x02, … Then, we do the same with a plaintext that ends with 0x01 and a key that ends with 0x00, then 0x01, then 0x02, and so on and so forth. There’s only one pair of ((iteration_of_last_plaintext_bytes), last_key_byte) that will get you the exact same array that produced the array the oracle gave you. We do this for each byte and we get the whole key.
What about the time?
Alright, that’s great, but if you try this solution straight away the server will close before you reach the 10th key byte. You’d be iterating 256 times remotely and 256*256 locally a total 16 times.
Luckily, we don’t really have to do remote requests and all local calculations. If we think about it, if a remote array and a local array have a match for the first, say, 30 or so values of a specific byte of a plaintext, then it will be almost certain the guessed key byte will be the same as the secret key byte. So we reduce the amounts of oracle requests to 30 and local calculations to 30*256 a total of 16 times.
solve.py
1
2# Should have SBox and query_oracle() defined before all this
3
4def attack():
5 recovered_key = bytearray()
6
7 NUM_QUERIES = 30 # If something goes wrong, increase slightly
8
9 for byte_idx in range(16): # 16 key bytes
10 observed_leakages = []
11
12 for c in range(NUM_QUERIES): # from 0x00 to NUM_QUERIES
13 pt = bytearray(16)
14 pt[byte_idx] = c # Going byte by byte. The rest will be 0x00
15
16 leakage = query_oracle(pt.hex())
17 observed_leakages.append(leakage) # Save the result for specific byte_idx
18
19 possible_guesses = []
20 for guess in range(256): # Trying to guess key byte now
21 match = True
22
23 # All other bytes will be 0x00, so we consider it a base that we substract of the observed leakages
24 # and expected values to isolate the effect of the byte we are trying to guess
25 base_expected = Sbox[0 ^ guess] & 1
26 base_observed = observed_leakages[0] # First value is all plaintext bytes to 0x00
27
28 for c in range(NUM_QUERIES):
29 expected = Sbox[c ^ guess] & 1
30 # All of them, up to NUM_QUERIES, must match the observed leakages. If not, we discard this guess
31 if (expected - base_expected) != (observed_leakages[c] - base_observed):
32 match = False
33 break
34
35 if match:
36 # If we reach this point, it means that the guess is a possible key byte for the current byte index
37 # Should only be reached once
38 possible_guesses.append(guess)
39
40 if len(possible_guesses) == 1:
41 found_guess = possible_guesses[0]
42 recovered_key.append(found_guess)
43 info(f"Recovered byte {byte_idx:02}: {hex(found_guess)}")
44 elif len(possible_guesses) > 1:
45 # If there's more than one possible guess, it means that the number of queries wasn't enough to isolate the byte
46 info("More than one match found. Increase NUM_QUERIES")
47 return
48 else:
49 info("Something went terribly, terribly wrong!")
50 return
51 info(f"Recovered key: {recovered_key.hex()}")