Attacking Block Ciphers - Fault Analysis in Cryptography - page 22

2.2.4.1 Attacking the First AddRoundKey

A simple CFA attack on AES consists of an adaptation of the attack described in
Sect. 2.2.2 to a byte-oriented fault model. Given the faulty ciphertext C produced
by encrypting M 0 , and producing a fault which forces to zero the output of the i th
XOR operation in the first AddRoundKey , the attacker exhaustively encrypts all
256 plaintexts M which coincide with M 0 , except for the byte

m i , until one of the ciphertexts collides with C . The plaintext byte m i leading to
a collision verifies that m i ⊕

= ( m 0 ,..., m 15 )

0, so the attacker decides that k i is equal to this
particular m i . By scanning all 16 XOR operations, this attack allows a key to be
completely recovered with only 16 faulty executions.
While quite efficient, this attack does not apply when the implementation is pro-
tected against first-order DPA by a Boolean masking scheme. In such implementa-
tions, all intermediate bytes are masked by an XOR with a random value R which
is different from one execution to another, but which is the same from one byte
to another. During the first AddRoundKey , each byte m i of the plaintext is thus
XORed with a masked key byte

k i =

k i

=

k i ⊕ R . When one tries to apply the above

CFA on the result of the i th iteration of the AddRoundKey , the physical zero value
forced on the XOR output actually corresponds to a logical value equal to R . While
exhausting all m i , the collision occurs when the logical XOR output is also equal to
the random mask R of the faulty execution. This occurs for m i such that m i ⊕ k i = R ,

so the attacker erroneously decides that the key byte is equal to k i ⊕ R instead of k i .

As the value R is unknown to the attacker, and different from one faulty execution
to another, the attack fails.
Amiel et al. [12] devised a variant of the CFA that can break such DPA-resistant
implementations of AES. The method is based on the observation from [21, 300]
that a fault may allow an attacker to prematurely terminate a for loop before it has
gone through all its iterations. If the memory location where the result of the XOR
between the plaintext and the key is stored has not been used previously, then there
are good odds that it is in an uninitialized state and contains bits all set to 0. 9 Now,
suppose that one produces a fault two iterations before the end of the loop of the
AddRoundKey . Then all 14 first result bytes are correct, but the last two are both
have a physical value equal to zero, meaning a logical value equal to some random
mask R that is identical for these two bytes. Encrypting all 2 16 plaintexts where m 14
and m 15 take all possibilities will produce a collision for ( m 14 , m 15 ) , verifying that

m 14 ⊕ k 14 = R and m 15 ⊕ k 15 = R .

An attacker will not know R but can nevertheless infer that

k 14 ⊕ k 15 = m 14 ⊕ m 15 .

The size of the key space is thus reduced from 2 128 to 2 120 .

9

Or all set to 1 depending on the logical representation of the physical state.