To: cypherpunks@toad.com
Subject: FYI - Biham/Shamir Differential Fault Analysis of DES, etc.
Date: Fri, 18 Oct 1996 15:10:51 -0400
From: Matt Blaze <mab@research.att.com>
------- Forwarded Message
From: Shamir Adi <shamir@wisdom.weizmann.ac.il>
Date: Fri, 18 Oct 1996 16:30:34 +0200
Message-Id: <199610181430.QAA20359@white.wisdom.weizmann.ac.il>
To: benaloh@microsoft.com, brassard@iro.umontreal.ca,
canetti@theory.lcs.mit.edu, crepeau@iro.umontreal.ca,
david@digicash.com, daw@cs.berkeley.edu, mab@research.att.com,
mihir@watson.ibm.com, rogaway@cs.ucdavis.edu, schneier@counterpane.com
Subject: A new attack on DES
Eli Biham , Computer Science Department, The Technion, Israel
Adi Shamir, Applied Math Department, The Weismann Institute, Israel
October 18, 1996
In September 96, Boneh Demillo and Lipton from Bellcore announced an ingenious new type of cryptanalytic attack which received widespread attention (see, e.g., John Markoff's 9/26/96 article in the New York Times). Their full paper had not been published so far, but Bellcore's press release and the authors' FAQ (available at http://www.bellcore.com/PRESS/ADVSRY96/medadv.html) specifically state that the attack is applicable only to public key cryptosystems such as RSA, and not to secret key algorithms such as the Data Encryption Standard (DES). According to Boneh, "The algorithm that we apply to the device's faulty computations works against the algebraic structure used in public key cryptography, and another algorithm will have to be devised to work against the nonalgebraic operations that are used in secret key techniques." In particular, the original Bellcore attack is based on specific algebraic properties of modular arithmetic, and cannot handle the complex bit manipulations which underly most secret key algorithms.
In this research announcement, we describe a related attack (which we call Differential Fault Analysis, or DFA), and show that it is applicable to almost any secret key cryptosystem proposed so far in the open literature. In particular, we have actually implemented DFA in the case of DES, and demonstrated that under the same hardware fault model used by the Bellcore researchers, we can extract the full DES key from a sealed tamperproof DES encryptor by analysing fewer than 200 ciphertexts generated from unknown cleartexts. The power of Differential Fault Analysis is demonstrated by the fact that even if DES is replaced by triple DES (whose 168 bits of key were assumed to make it practically invulnerable), essentially the same attack can break it with essentially the same number of given ciphertexts.
We would like to gratefully acknowledge the pioneering contribution of Boneh Demillo and Lipton, whose ideas were the starting point of our new attack.
In the rest of this research announcement, we provide a short technical summary of our practical implementation of Differential Fault Analysis of DES. Similar attacks against a large number of other secret key cryptosystems will be described in the full version of our paper.
The attack follows the Bellcore fundamental assumption that by exposing a sealed tamperproof device such as a smart card to certain physical effects (e.g., ionizing or microwave radiation), one can induce with reasonable probability a fault at a random bit location in one of the registers at some random intermediate stage in the cryptographic computation. Both the bit location and the round number are unknown to the attacker.
We further assume that the attacker is in physical possesion of the tamperproof-device, so that he can repeat the experiment with the same cleartext and key but without applying the external physical effects. As a result, he obtains two ciphertexts derived from the same (unknown) cleartext and key, where one of the ciphertexts is correct and the other is the result of a computation corrupted by a single bit error during the computation. For the sake of simplicity, we assume that one bit of the right half of the data in one of the 16 rounds of DES is flipped from 0 to 1 or vice versa, and that both the bit position and the round number are uniformly distributed.
In the first step of the attack we identify the round in which the fault occurred. This identification is very simple and effective: If the fault occurred in the right half of round 16, then only one bit in the right half of the ciphertext (before the final permutation) differs between the two ciphertexts. The left half of the ciphertext can differ only in output bits of the S box (or two S boxes) to which this single bit enters, and the difference must be related to non-zero entries in the difference distribution tables of these S boxes. In such a case, we can guess the six key bit of each such S box in the last round, and discard any value which disagree with the expected differences of these S boxes (e.g., differential cryptanalysis). On average, about four possible 6-bit values of the key remain for each active S box.
If the faults occur in round 15, we can gain information on the key bits entering more than two S boxes in the last round: the difference of the right half of the ciphertext equals the output difference of the F function of round 15. We guess the single bit fault in round 15, and verify whether it can cause the expected output difference, and also verify whether the difference of the right half of the ciphertext can cause the expected difference in the output of the F function in the last round (e.g., the difference of the left half of the ciphertext XOR the fault). If successful, we can discard possible key values in the last round, according to the expected differences. We can also analyse the faults in the 14'th round in a similar way. We use counting methods in order to find the key. In this case, we count for each S box separately, and increase the counter by one for any pair which suggest the six-bit key value by at least one of its possible faults in either the 14'th, 15'th, or 16'th round.
We have implemented this attack on a personal computer. Our analysis program found the whole last subkey given less than 200 ciphertexts, with random single-faults in all the rounds.
This attack finds the last subkey. Once this subkey is known, we can proceed in two ways: We can use the fact that this subkey contains 48 out of the 56 key bits in order to guess the missing 8 bits in all the possible 2^8=256 ways. Alternatively, we can use our knowledge of the last subkey to peel up the last round (and remove faults that we already identified), and analyse the preceding rounds with the same data using the same attack. This latter approach makes it possible to attack triple DES (with 168 bit keys), or DES with independent subkeys (with 768 bit keys).
This attack still works even with more general assumptions on the fault locations, such as faults inside the function F, or even faults in the key scheduling algorithm. We also expect that faults in round 13 (or even prior to round 13) might be useful for the analysis, thus reducing the number of required ciphertext for the full analysis.
Differential Fault Analysis can break many additional secret key cryptosystems, including IDEA, RC5 and Feal. Some ciphers, such as Khufu, Khafre and Blowfish compute their S boxes from the key material. In such ciphers, it may be even possible to extract the S boxes themselves, and the keys, using the techniques of Differential Fault Analysis. Differential Fault Analysis can also be applied against stream ciphers, but the implementation might differ by some technical details from the implementation described above.
------- End of Forwarded Message
The Risks Digest Volume 18: Issue 56
Thursday 31 October 1996
The next stage of on Differential Fault Analysis
Adi Shamir <shamir@wisdom.weizmann.ac.il>
Thu, 31 Oct 1996 21:27:44 -0800
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.
[See comments by Kocher and Anderson below.]
Added by jya.com October 24, 1996:
See related October 23 announcement of six researchers at National University of Singapore and another on October 24 by Jean-Jacques Quisquater.
Added by jya.com October 31, 1996:
See subsequent Bellcore report published October 31, 1996, On the Importance of Checking Computations by Boneh, DeMillo and Lipton, on a theoretical model for breaking various cryptographic systems, which expands their smartcard attack. See "context" for this report.
Added by jya.com November 11, 1996:
See comments by Paul Kocher on legacy of fault-induced cryptanalysis.
Added by jya.com November 13, 1996:
See comments by Ross Anderson on DES weakness.
Added by jya.com November 20, 1996:
See Anderson and Kuhn's "Improved DFA" and their new comprehensive paper on tampering.
Added by jya.com December 8, 1996:
See comments by Jean-Jacques Quisquater on Single Event Effect.