Wiki / Concepts

Differential Fault Analysis

Encrypt the same plaintext twice, once correctly and once with a fault, then read the key out of the difference between the two ciphertexts. The active counterpart to power analysis, and on AES it takes a handful of faults, not thousands of traces.

dfa fault attack aes piret quisquater bellcore rsa-crt glitch faulty ciphertext phoenixaes key schedule
How one faulted byte becomes a key
One byte corrupted at the input of round 9
Round 9 MixColumns spreads it over 4 bytes of one column
Round 10 ShiftRows scatters those 4 bytes across 4 columns
You never need to know what value the fault wrote. Which four ciphertext bytes changed already tells you which diagonal was hit, and the algebra between the correct and faulty pair does the rest. Recovering the round 10 key is enough: the AES key schedule is invertible, so it gives back the master key.

Differential fault analysis (DFA) recovers a key by comparing a correct output with a faulty one. You run the same computation twice on the same input, disturb the device during the second run, and treat the difference between the two results as an equation in the key. It is the active half of Wiki: side-channel work, and unlike Wiki: power-analysis it needs no measurement of the device at all, only its output.

The idea

A block cipher is a chain of invertible steps. If you corrupt the state near the end of the chain, the corruption only has a few steps left to diffuse, so it reaches the output in a pattern that is structured rather than random. That pattern is a function of the key, and comparing the correct and the faulty ciphertext lets you solve for it.

Two things make this cheaper than it sounds:

  • The value written by the fault is irrelevant. Random is fine, which matches what a voltage glitch or a clock glitch actually does.
  • The location does not have to be known in advance. It is recoverable after the fact from which output bytes changed.

What you do need is repeatability: the same plaintext encrypted correctly once and faultily once, with the fault landing in roughly the right round.

On AES-128

AES has ten rounds, and the tenth has no MixColumns, which is exactly why the attack works so well. Inject a single byte fault at the input of round 9:

  1. SubBytes and ShiftRows keep it one byte.
  2. The MixColumns of round 9 spreads it across four bytes of one column, in the fixed ratios of the MixColumns matrix.
  3. Round 10 substitutes and shifts those four bytes into four different columns, then adds the last round key.

The ciphertext therefore differs from the correct one in exactly four byte positions, and those positions identify which of the four diagonals took the hit. For each of those four bytes you can write the difference in terms of the last round key and the unknown fault, and the MixColumns ratios tie the four equations together. Piret and Quisquater (CHES 2003) showed that two faulty ciphertexts of the same plaintext recover the whole last round key; the later single-fault variant of Tunstall, Mukhopadhyay and Ali (2011) narrows one fault to about 2^32 candidates, and to roughly 2^8 once the key schedule relations are folded in.

Recovering K10 is recovering the key: the AES key schedule is invertible, so running it backwards ten rounds gives the master key.

A fault one round earlier diffuses through two MixColumns and reaches every byte of the output, which tells you nothing. A fault in round 10 changes one byte and leaks only one byte of key. The round matters.

Doing it in practice

The standard tool is phoenixAES (from the SideChannelMarvels toolbox), which implements exactly the attack above. Give it the correct ciphertext followed by faulty ones and it returns the last round key:

import phoenixAES
# tracefile: correct ciphertext on line 1 in hex, one faulty ciphertext per line after.
phoenixAES.crack_file("faults.txt")
# -> Last round key #N found: ...

It wants faults spread over all four diagonals, so collect more pairs than the theoretical minimum and let the tool discard the ones that are not exploitable (a glitch that hit the wrong round produces a ciphertext differing in far more than four bytes, which is itself the cheapest sanity check you have). Then invert the key schedule from the round key back to the master key.

Getting the faults is the Wiki: side-channel side of the job: a voltage or clock glitch on a ChipWhisperer, an EM pulse, or an under-volted supply, swept over an offset window until the output changes without the device crashing. The useful signal during the sweep is the shape of the corruption, not just "it changed": four differing bytes means you are in the right round.

Beyond AES: one fault breaks RSA-CRT

The most dramatic instance is the Bellcore attack (Boneh, DeMillo and Lipton, 1997) on RSA signatures computed with the Chinese Remainder Theorem. The signer computes one half modulo p and the other modulo q, then recombines. Corrupt exactly one of those halves and the faulty signature s' is correct modulo one prime and wrong modulo the other, so

gcd(s - s', N) = one of the prime factors of N

One fault, one gcd, and the private key is gone. This is why any serious RSA-CRT implementation verifies its own signature before releasing it.

Countermeasures, and why they are layered

  • Compute twice and compare is the obvious answer, and it moves the attack rather than ending it: the new target is the comparison itself, where a single skipped instruction returns "equal". Countermeasures against fault injection are stacked precisely because each one has a fault of its own.
  • Verify the inverse (decrypt the ciphertext you are about to return, sign then check) costs a full operation but detects a corrupted state rather than a corrupted comparison.
  • Infective computation spreads any fault over the whole output instead of detecting it, so the attacker gets randomness rather than four structured bytes.
  • Sensors and randomised timing (voltage and clock monitors, random delays) attack the injection rather than the algebra.

Pitfalls

  • Same plaintext, or nothing. The whole method is a difference. A faulty ciphertext without its correct counterpart on the same input is unusable.
  • Confirm the fault model before blaming the maths. Count the differing bytes: 1 means round 10, 4 means round 9 and is what you want, 16 means too early. Do not feed a 16-byte difference into a round 9 solver.
  • A crash is not a fault. Most glitch parameters reset the target or produce garbage. Only the narrow band that leaves the device running and the output structured is useful.
  • Deterministic outputs only. A padding scheme or a signature that randomises each run destroys the pairing unless you can fix the randomness.
  • Bricking is real. Repeated over-glitching damages parts. Work on a target you can replace.

Further reading

Related tools

CWChipWhisperer