leaky crypto

couldn’t hack it during the competition

I failed horribly at solving this during the actual competition, embittered and incensed I was determined to finish it. Here’s the full challenge description.

Hello, fellow space enthusiasts!

I have been tracking a specific satellite and managed to intercept an interesting 
piece of data. Unfortunately, the data is encrypted using an AES-128 key with ECB-Mode.

Encrypted Data: d7e89ca0bae4fc63cea9477f1ab7a721bcc63398172e1979f9cc79496e6b99b2050e5b8ee33c6fdb44c2bfb886dcc16fe57b4820e23b609781c35e7f66b58e8856093026ef3a19d3b05455f68284cf6958f0d93529c90d107349e61823e09030f042701fc238b093e3f79cb7eb1c0067

Using proprietary documentation, I have learned that the process of generating the 
AES key always produces the same first 6 bytes, while the remaining bytes are random:

Key Bytes 0..5: 0944dd756b44

The communication protocol hashes every message into a 128bit digest, which is encrypted
with the satellite key, and sent back as an authenticated ACK. This process fortunately 
happens BEFORE the satellite attempts to decrypt and process my message, which it will
immediately drop my message as I cannot encrypt it properly without the key.

I have read about "side channel attacks" on crypto but don't really understand them, 
so I'm reaching out to you for help. I know timing data could be important so I've 
already used this vulnerability to collect a large data set of encryption times for 
various hash values. Please take a look!

Included with the writeup is a text file with random plaintext hashes and their encryption time in presumably microseconds. Here’s a sample of that file.


The times range from 10512 to 10752 with corresponding time steps being 12 or 16 - never figured out why I presume the devs didn’t actually time anything and instead worked backwards from a 128 bit key to generate the above samples.

The above samples show a high correlation with cache hits, after looking into the details of the first round of AES and using the initial 6 byte key that was given I counted the collisions between the [0] and [4] byte and the [1] and [5] byte to see if there was a linear relationship. The sample below shows the average collisions over each time-step for the given samples, with the exception of the time 10608 samples, there is a clear trend in the data.

('10584.txt', 0.03968253968253968)
('10608.txt', 0.0076045627376425855)
('10632.txt', 0.018404907975460124)
('10656.txt', 0.013914195792612225)
('10680.txt', 0.010468357011759908)
('10704.txt', 0.00864411897931451)
('10728.txt', 0.006277483907972723)

Rather than deal with key-mixing and feeling confident from the above analysis I focused my efforts on only attacking the first round of AES. During the first round, like indexes of the plaintext and key are xor’d together and used as a lookup into one of four T tables. p[0] ^ k[0] is used as a lookup for T0 along with p[4] ^ k[4], p[8] ^ k[8] and p[12] ^ k[12]. Similarly p[1] ^ k[5] is used as a lookup for T1, and so forth…

Lookups that hit the same cache line will lower the execution time of the entire encryption, so correlating low average times with guessed key bytes is a simple strategy to find the key. I wrote the below script to do just that. Rather than find a programmatic way I just entered the two bytes I was testing in the inner loop and reran the program to find the result. This revealed the upper 6 bits on seven unknown key bytes and left 3 bytes to brute force.

import numpy as np

f = open('../test.txt')
fr = f.readlines()
line_ctr = 0

key = [0x09, 0x44, 0xdd, 0x75, 0x6b, 0x44, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]

alltimes = np.zeros(0x100)
allcounts = np.zeros(0x100)
allavgs = np.zeros(0x100)
global_avg = 0.0
global_ctr = 0

for line in fr:
    parts = line.split(',')
    chkint = int(parts[1][:len(parts[1])-1])
    global_avg += float(chkint)
    global_ctr += 1
    hexes = []
    for ii in range(0, 16):
        hexat = int(parts[0][ii*2:ii*2+2], 16)
    # Modify this byte and the one in the inner loop to 
    # determine suitable correlation 
    against = hexes[0] ^ key[0]
    for hextry in range(0, len(alltimes)):
        k8 = (hextry) & 0xFF
        x8 = hexes[12] ^ k8
        if(x8 == against):
            alltimes[hextry] += chkint
            allcounts[hextry] += 1

for hextry in range(0, len(alltimes)):
    if(allcounts[hextry] != 0):
        allavgs[hextry] = float(alltimes[hextry]) / float(allcounts[hextry])
# These keys were found running the program
#k8 = 1,0,2,3
#k9 = 0x4e, 4f, 4c, 4d
#k10 = 0xbc, 0xbd, 0xbf, 0xbe
#k7 = 0xfe, 0xfc, 0xfd, 0xff
#k15 = 0x7c, 0x7d, 0x7f, 0x7e
#k14 = 0x26, 24, 25, 27
#k13 = 0x4d, 4c, 4e 4f

copyavgs = np.copy(allavgs)
allavgs = np.sort(allavgs)
ii = 0
for hextime in range(0, len(allavgs)):
    findit = 0
    if(allavgs[hextime] == 0):

    for hexcheck in range(0, len(copyavgs)):
        if(copyavgs[hexcheck] == allavgs[hextime]):
            findit = hexcheck

    print(hex(findit), allavgs[hextime])

    if(ii > 8):

print("global", global_avg / float(global_ctr))

So it’s a pretty crap script but it worked! I used AES-NI instructions to then bruteforce the remaining (4^7) * (2^24) unknowns to find the flag.

This took me way too long (two weekends) but it was fun to learn a bit about AES internals.