# [cryptography] A Fault Attack based on Rijmen's Chosen-Text Relations Attack

Alfonso De Gregorio adg at crypto.lo.gy
Tue Jun 15 01:36:46 EDT 2010

```The last Thursday, Vincent Rijmen announced a new clever attack on AES
(and KASUMI) in a
report posted to the Cryptology ePrint Archive: Practical-Titled
Attack on AES-128 Using
Chosen-Text Relations, http://eprint.iacr.org/2010/337

I believe the related-subkey model is an interesting model to look at
and, with this
chosen-text relations
attacks and their implications.

For example, this model might be pretty relevant while attacking white-box
implementations of the target encryption algorithm with embedded
secret key, assuming the
ability to tamper with at least 1bit of the round output (debugging...).

A Fault Attack
In order to further solicit comments, I would like to contribute a fault attack
construction based on chosen-text relations attack.

First, it is worth to note how the zero-query attack provided by
chosen-text-relations-in-the-middle can be transformed into an attack
with a single-query
to both the encryption and decryption oracles. It is possible to do so
by resuming the
interrupted encryption after applying the specific difference delta to
the state (ie, no
rollback anymore) and querying the decryption oracle.

More specifically:
- halt the computer in the middle of execution of an encryption routine;
- apply the specific difference delta to the state;
- resume the encryption and output the ciphertext c*;
- query the decryption oracle with c* and retrieve the modified plaintext p*.

The fault attack below assumes the 1bit flip fault model, requires
only one faulty
ciphertext and, when applied to AES on a 32bit machine, have 2^37 time
complexity for the
key-extraction step.

The construction:
- Being 'delta' any 16-byte string;
- Apply a random 1bit difference 'delta' doing fault injection, let
delta be 2^i where 0
<= i <= word-size (eg. 32);
- For each possible 'delta' compute epsilon = ShiftRows^-1
(MixColumns^-1 (delta));
- For each epsilon, if all bytes are non-zero, solve the equation
looking at the 2^32
possible solutions: SubBytes(p + k) + SubBytes(p* + k) = epsilon;
- The attack will run in 2^37 time complexity on a 32bit machine.