Differential Fault Attacks on AES

Assuming you have a program with an unknown key that performs AES decryptions. Your goal is to retrieve the AES key.

We have a binary that performs the AES decryptions (no access to the key, only regular executions) and a simulator that performs a bitflip on a certain memory address at a certail RIP.

AES Decryption Algorithm: 

static void InvCipher(state_t* state, const uint8_t* RoundKey)
{
  uint8_t round = 0;

  // Add the First round key to the state before starting the rounds.
  AddRoundKey(Nr, state, RoundKey);

  // There will be Nr rounds.
  // The first Nr-1 rounds are identical.
  // These Nr-1 rounds are executed in the loop below.
  for (round = (Nr - 1); round > 0; --round)
  {
    InvShiftRows(state);
    InvSubBytes(state);
    AddRoundKey(round, state, RoundKey);
    InvMixColumns(state); pos
  }

  // The last round is given below.
  // The MixColumns function is not here in the last round.
  InvShiftRows(state);
  InvSubBytes(state);
  AddRoundKey(0, state, RoundKey);
}

iHrdxO.png

You can execute a normal decryption, get the generated plaintext, and then perform another execution but with faults (bitflips) on each byte of the key just before last InvSubBytes.

That would leave us with a controlled input differential original \xor bitfliped_original == bitflipvalue and an output differential also known, as XOR-ing the same key value does not alter the differential:

  1. c1 \xor k = m1
  2. c2 \xor k = m2
  3. m1 \xor m2 = c1 \xor c2 \xor k \xor k
  4. m1 \xor m2 = c1 \xor c2

With a known input-output differential to the InvSubBytes (S-1 inverse “S-Box”), we can “bruteforce which input pairs have the same differential as us AND also the same output differential after applying the inverse S-Box. 

if ((diff_X_i == diff_out[ki]) and (diff_X == diff_in[ki])):
    k1 = x1_i ^ real_pt[ki]
    k2 = x2_i ^ real_pt[ki]
    print(f"\t- {k1}, {k2} are candidates for for key byte {ki}")

With a good bitflip setup, we can reduce the keyspace from 2128 to just 216.

For example: 

Input  differential: 01 01 01 01 02 02 02 08 01 01 01 01 04 02 02 01
Output differential: 28 4c 75 30 84 1f c7 2c 3e 84 69 ff b7 b5 ce 63
Differential cryptanalysis:
    - 5, 45 are candidates for for key byte 0
    - 254, 178 are candidates for for key byte 1
    - 205, 184 are candidates for for key byte 2
    - 45, 29 are candidates for for key byte 3
    - 61, 185 are candidates for for key byte 4
    - 223, 192 are candidates for for key byte 5
    - 176, 119 are candidates for for key byte 6
    - 163, 143 are candidates for for key byte 7
    - 55, 9 are candidates for for key byte 8
    - 191, 59 are candidates for for key byte 9
    - 170, 195 are candidates for for key byte 10
    - 242, 13 are candidates for for key byte 11
    - 62, 137 are candidates for for key byte 12
    - 220, 105 are candidates for for key byte 13
    - 133, 75 are candidates for for key byte 14
    - 148, 247 are candidates for for key byte 15
Reduced key space from 128 bits to 16
[◣] Bruteforcing the key: candidate 13875 of 65536
Found the key!!! k = bytearray(b'\x05\xfe\xb8\x1d=\xc0w\xa37\xbf\xc3\r>\xdcK\xf7')

Note: Attacking the decryption means that the key that we found is the “master key”, if we do exactly the same on decryption we would get the round key, which we can use to derive the master key “unrolling” de encryption process.

Note: This is done in a simulated (and perfect) enviroment for faults. Real word scenarios don’t have perfect timed, reliable and precise faults.