Subject: The next stage of on Differential Fault Analysis

  The Next Stage of Differential Fault Analysis:
  How to break completely unknown cryptosystems, 30 October 1996 (draft)

  Eli Biham, Computer Science Dept., The Technion, Israel
  Adi Shamir, Applied Math Dept., The Weizmann Institute, Israel

The idea of using computational faults to break cryptosystems was first
applied by Boneh Demillo and Lipton to public key cryptosystems, and then
extended by Biham and Shamir to most types of secret key cryptosystems.
[See RISKS-18.54.]  In this new research announcement, we introduce a
modified fault model that makes it possible to find the secret key stored in
a tamperproof cryptographic device even when nothing is known about the
structure and operation of the cryptosystem. A prime example of such a
scenario is the Skipjack cryptosystem, which was developed by the NSA, has
unknown design, and is embedded as a tamperproof chip inside the
commercially available Fortezza PC cards. We have not tested this attack on
Skipjack, but we believe that it is a realistic threat against some
smart-card applications that were not specifically designed to counter it.

The main assumption behind the new fault model is that the cryptographic key
is stored in an asymmetric type of memory, in which induced faults are much
more likely to change a 1 bit into a 0 than to change a 0 bit into a 1 (or
the other way around). CMOS registers seem to be quite symmetric, but most
types of nonvolatile memory exhibit some degree of asymmetry. For example, a
1 bit in an EEPROM cell is stored as a small charge on an electrically
isolated gate. If the fault is induced by external radiation (e.g.,
ultraviolet light), then the charges are more likely to leak out of the gate
than to be forced into the gate.

To make the analysis simpler, we assume that we can apply a low-level
physical stress to the tamperproof device when it is disconnected from
power, whose only possible effect is to occasionally flip one of the 1 bits
in the key register to a 0. The plausibility of this assumption depends on
numerous physical and technical considerations, which are beyond the scope
of this note.

We further assume that we are allowed to apply two types of cryptographic
functions to the given tamperproof device: We can supply a cleartext m and
use the current key k stored in the nonvolatile memory of the device to get
a ciphertext c, or we can supply a new n-bit key k' that replaces k in the
nonvolatile memory.

The cryptanalytic attack has two stages:

1. In the first stage of the attack, we keep the original unknown secret key
k stored in the tamperproof device, and use it to repeatedly encrypt a fixed
cleartext m_0. After each encryption, we disconnect the device from power
and apply a gentle physical stress. The resultant stream of ciphertexts is
likely to consist of several copies of c_0, followed by several copies of a
different c_1, followed by several copies of yet another c_2, until the
sequence stabilizes on c_f. Since each change is likely to be the result of
one more key bit flipping from 1 to 0 (thus changing the current key k_i
into a new variant k_i+1), and since there are about n/2 1 bits in the
original unknown key k, we expect f to be about n/2,and c_f to be the result
of encrypting m_0 under the all-zero key k_f.

2. In the second stage of the attack, we work our way backwards from the
known all-zero key k_f to the unknown original key k_0. Assuming that we
already know some intermediate key k_i+1, we assume that k_i differs from
k_i+1 in a single bit position. If we knew the cryptographic algorithm
involved, we could easily try all the possible single bit changes in a
simple software simulation on a personal computer, and find the (almost
certainly unique) change that would give rise to the observed ciphertext
c_i. However, we don't need either a simulator or knowledge of the
cryptographic algorithm, since we are given the real thing in the form of a
tamperproof device into which we can load any key we wish, to test out
whether it produces the desired ciphertext c_i. We can thus proceed
deterministically from the known k_f to the desired k_0 in O(n) stages,
trying O(n) keys at each stage. The attack is guaranteed to succeed if the
fault model is satisfied, and its total complexity is at most O(n^2)
encryptions.

This seems to be the first cryptanalytic attack that makes it possible to
find the secret key of a completely unknown cryptosystem in polynomial time
(quadratic time in our case). It relies on a particular fault model that
seems to be realistic, but requires further study.  In the full version of
this paper, we'll discuss numerous extensions of the attack -- including the
analysis of more complicated fault models in which the sequence of corrupted
keys forms a biased random walk in the space of 2^n possible keys.

------------------------------