This weekend, as part of my efforts to advance my learning of power analysis, I attempted to create my own power leakage model of DES and recover a key without referring to previous work. My targets were the ATMega328p board, used for previous experiments, as well as a PIC24F target board. Both ran with DES code from avr-crypto-lib.
I must admit that I cheated somewhat, by using triggers at the start of DES round 1. Unfortunately, I haven’t yet been able to compensate for some high-amplitude, low-frequency noise I’m seeing in one target (I’ve eliminated the power supply as a cause, I’ve yet to try with a magnetic probe) – without this, I am almost certain trace alignment would be meaningless.
While conceptually trivial, implementing this was a good exercise in selecting and writing my own leakage model.
Recovering Key Fragments
We begin our analysis by looking at avr-crypto-lib’s implementation of the DES algorithm. In diagram form, it looks like this (only the bits we need, half the round function is omitted):
The key is split into 8 6-bit key fragments for each round, and there are 16 xor-sbox-mix operations (8 against each half of the plaintext) for each round of DES (i.e. 16 sub-rounds per round). This comes up clearly in a power trace (from memory, 64MS/s, 16100 samples), which shows the first 8 rounds, which is more than enough for this attack:
We perform a correlation attack, by choosing the 6 bits of key material XOR’ed with the permuted plaintext, and then correlating against the expected Hamming weight of sbox[out] & 0x0F OR sbox[out] >> 4. If our key guess is correct, we should get an extremely strong correlation.
In order to do this, we need to implement:
- the first part of the DES algorithm up to the first round, allowing us to permute the plaintext via the initial permute (ip_permtab) and expand permute (e_permtab)
- the “guess” part of the DES algorithm: for each guessed key fragment, we must be able to compute the SBOX output (keeping in mind the 8 separate SBoxes, depending on the key fragment used.
A bit of quick testing shows us the leak actually works, showing a strong correlation against a single key fragment:
We then complete the rest of the attack, including the multiple SBox mechanic, leaving us with the following overview:
Strangely, only 4 of the 8 key guesses were recovered. I slowly walked through my code, until I realized that I had only guessed key bits up to 48, instead of up to 64 (2 ^ 6) as it should have been. one quick fix later:
Key Recombination and Recovery
To recover the key fragments into a useful key, we need to perform the following steps, in order:
- Invert the PC2 permutation (which takes 48 bits of input, and generates 56 bits of output, including 8 bits which we know are useful, but don’t know the value of)
- Invert the shiftkeys operation (which takes 56 bits of input and gives 56 bits of output)
- Invert the PC1 permutation (which takes 56 bits of input, and generates 64 bits of output, including 8 bits which we know are ignored)
Unfortunately, the PC2 permutation applied to the key only keeps 48 / 56 bits of usable key material – we can use a brute force attack to recover the final 8 bits of useful key material.
To allow this, I used a flexible inverse permutation, which allowed marking bits as “don’t know but care (2)” and “don’t know, don’t care (3)”:
def inv_permute(table,blk,default_char=2): pt = [default_char] * (max(table) + 1) for index in range(0,len(blk)): if pt[table[index]] == 2 or pt[table[index]] == 3: pt[table[index]] = int(blk[index]) else: if pt[table[index]] != int(blk[index]): print "fail - mismatch in inv_permute" sys.exit(0) return pt
This ended up providing a template like the following (based off the recovered fragments above):
[0, 0, 1, 0, 1, 2, 2, 3, 0, 1, 2, 2, 1, 1, 1, 3, 0, 0, 0, 1, 0, 1, 0, 3, 0, 0, 0, 1, 0, 1, 1, 3, 0, 0, 1, 0, 1, 0, 0, 3, 1, 0, 2, 0, 1, 2, 1, 3, 1, 2, 0, 2, 0, 0, 1, 3, 1, 0, 1, 0, 0, 1, 1, 3]
We can then brute force a single byte of key material, substituting it into the bits marked ‘2’, and replacing the ‘3”s with 0’s. Testing this against a single known plaintext and ciphertext is enough to recover an equivalent key, which works just as well as the original key:
Original: 2b7e151628aed2a6 Equivalent: 2a7e141628aed2a6
Alternatively, using the second and third rounds of DES to recover this material is also feasible, but tremendously time-consuming in terms of code.
All the code is in github.com/CreateRemoteThread/fuckshitfuck – most of the DES-specific code is in dessupport.py.