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.