## Power Leakage Modelling of DES

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.

## About Norman

Sometimes, I write code. Occasionally, it even works.
This entry was posted in Bards, Computers, Jesting. Bookmark the permalink.

This site uses Akismet to reduce spam. Learn how your comment data is processed.