Research paper · IIT Kharagpur · 5 min read

Finding exploitable faults in block ciphers without running the attacks

A fault attack deliberately corrupts a cipher while it runs, then compares the faulty output with a correct one to narrow the secret key. Whether the attack is practical depends on where and how the fault occurs. Testing every possibility by building and running a separate attack is too expensive, so we developed a framework that finds exploitable faults from cipher simulations and estimates the work needed to recover the key.

Role: Second author, as an undergraduate
Status: Published: PROOFS 2017; Journal of Cryptographic Engineering, 2019
Systems: AES, PRESENT, differential fault analysis

Problem

Anyone certifying a cipher implementation needs to know which faults are exploitable, across every place a fault could land. The automated tools available then were either too slow for a whole fault space or blind to some known attacks.

Differential fault analysis (DFA) compares a correct ciphertext with a faulty one from the same plaintext and key. An attack needs a distinguisher: a property of the difference between the correct and faulty internal states that holds for the right key guess and fails for wrong ones. It also needs a way to split the key guess into pieces small enough to check exhaustively.

The existing approaches each had a gap. Algebraic fault attacks encode the cipher and the fault for a SAT solver, which works for one fault but is far too expensive across a whole fault space. XFC, a faster framework, tracks which parts of the state a fault reaches and assumes each part can take every possible value. That makes it blind to differences that are restricted in value, such as a byte that can never be zero. Two known attacks rely on exactly that. The impossible-differential attack on AES, with a fault at round 7, recovers the key from an inequation:

\mathrm{MC}^{-1}\big|_b\big(S^{-1}(x_h \oplus k_h)\big) \,\oplus\, \mathrm{MC}^{-1}\big|_b\big(S^{-1}(x'_h \oplus k_h)\big) \;\neq\; 0

where $x_h, x'_h$ are correct and faulty ciphertext bytes and $k_h$ the key bytes. Undoing the last S-box and MixColumns with the right key gives a state byte difference that is never zero, so any key guess that produces zero is wrong. The other is the round-28 attack on PRESENT, where each 4-bit difference takes only 2 of its 16 values.

Context

Sayandeep Saha, Ujjawal Kumar, Debdeep Mukhopadhyay and Pallab Dasgupta. A version appeared at PROOFS 2017 as "An Automated Framework for Exploitable Fault Identification in Block Ciphers – A Data Mining Approach". The extended version is in the Journal of Cryptographic Engineering (2019). The numbers below are from the open-access IACR ePrint version.

Approach

The framework works in three steps.

Simulate

We ran an executable model of the cipher across many plaintexts, keys and fault values, and recorded the difference between each correct run's internal states and the faulty run's. Each state difference becomes a table with one column per word. Collecting it takes a couple of seconds.

Find distinguishers

A state difference of $l$ words of $m$ bits is a distinguisher when its entropy falls below the maximum $l\,m$ bits. A wrong key guess makes the difference look uniform, and the right one shows the deficit. There are two ways a difference can be less random, and each has its own check:

Restricted values. Some words never take certain values, such as zero. A range check finds them, and this is the case XFC can't see.
Correlated words. Some words move together, which is what a cipher's diffusion layer produces. Frequent-itemset data mining over the table finds these groups, and the entropy of each group is $\log_2$ of the number of value combinations it takes.

A distinguisher is only useful if an S-box, the cipher's nonlinear substitution step, sits between it and the ciphertext. Without one there is no equation to solve for the key.

Estimate the cost

A dependency graph of the cipher records which bits of each state and round key every bit depends on. Walking it from each distinguisher to the ciphertext gives the key bits that would have to be guessed. Key sets that overlap are merged into maximum independent key sets $MKS_h$ , which can be searched in parallel, so the search costs

T \;=\; \max_{1 \le h \le M} \, 2^{|MKS_h|}

The remaining keyspace $|R|$ comes from how likely a wrong guess is to pass each check, scaled by the S-box's differential characteristic. An attack costs the larger of $T$ and $|R|$ , and we treated $2^{50}$ as the limit for a practical attack. When one fault leaves too many candidate keys, applying the check once per extra fault estimates how many faults are needed.

Result

The framework takes an executable model of a cipher and reports which faults are exploitable and roughly how much work each attack needs, without building or running any attack. On AES-128 and PRESENT-80, the earliest exploitable faults it found were at round 7 and round 28, matching the published attacks, including the two that XFC can't see.

Fault	Distinguisher	Entropy (bits)	$T$	$\lvert R \rvert$ , one fault
AES, byte, round 8	correlated bytes	31.96 of 128	$2^{32}$	$2^{32}$
AES, byte, round 7	impossible differential	127.90 of 128	$2^{32}$	$\approx 2^{32}$
PRESENT-80, 2-byte, round 28	restricted nibbles	16 of 64	$2^{32}$	$2^{80}$

The round-8 fault reproduces the known single-fault attack. The round-7 fault is the one XFC misses: its bytes show no associations, and its entropy is barely below the maximum because no byte ever takes the value 0. One fault removes only about one key guess in 64 per group, so the attack needs several faults. For PRESENT, one fault cuts the $2^{128}$ guess space to $2^{80}$ , and a second brings it to $2^{32}$ .

The framework estimates attack cost and never recovers a key, and the estimate rests on simplifying assumptions. It also assumes the evaluator knows where faults land, which suits certifying your own implementation but not every attacker. Faults in the key schedule or round counter were left as future work.

All writeups