ntype.club

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.

49fd411ea44d35f07adc1dbd79f38ab4,10752
19f6a95f9c5703c4d8fc0f0bb1b11f7a,10752
aad94711aa37274c9ba91ab01de1c7e3,10728
bafc1e9d71d5581195385d7d4a26bfac,10728
fe2e2515e83ba7d48fd43eb984ca615b,10728
13ebe9dda084b5c7da268f4e643d1bb9,10752
7b4017718dc7cd4ecfff114784e2cf2d,10728
94916ee72e41fbea4fac1268a4ca7b33,10752
4b4a332d94e542e1c4a8098989253d00,10728

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()
f.close()
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)
        hexes.append(hexat)
    # 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):
        continue

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

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

    ii+=1
    if(ii > 8):
        break

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.