Date: Wed, 23 Oct 1996 09:38:15 --800
From: deng@iss.nus.sg (Robert Deng)
To: cypherpunks@toad.com, mab@research.att.com, shamir@wisdom.weizmann.ac.il, benaloh@microsoft.com, brassard@iro.umontreal.ca, yiqun@rsa.com
Subject: A new attack to RSA on tamperproof devices
Cc: baofeng@iss.nus.sg, deng@iss.nus.sg, yfhan@iss.nus.sg, jeng@iss.nus.sg, teowhin@iss.nus.sg, desai@iss.nus.sg
Feng Bao (baofeng@iss.nus.sg)
Robert Deng (deng@iss.nus.sg)
Yongfei Han (yfhan@iss.nus.sg)
Albert Jeng (jeng@iss.nus.sg)
Teow Hin Nagir (teowhin@iss.nus.sg)
Desai Narasimhalu (desai@iss.nus.sg)
Information Security Group
Institute of Systems Science
National University of Singapore
23rd October 1996
In September 96, Boneh Demillo and Lipton from Bellcore announced a new type of cryptanalytic attack against RSA-like public key cryptosystems on tamperproof devices such as smart card (see, e.g., http://www.bellcore.com/PRESS/ADVSRY96/ medadv.html). However, due to the sketchiness of the Bellcore attack, it is impossible to perform a meaningful assessment of this attack until more detailed information becomes available.
On October 18, Eli Biham and Adi Shamir published their new attack, called Differential Fault Analysis (DFA), to secret key cryptosystems, such as DES. Some concrete ideas on how this attack works were revealed in their announcement (see, e.g., http://jya.com/dfa.htm).
Our work here was motivated first by the Bellcore announcement and then by the DFA announcement. We present an attack to RSA on tamperproof devices. At the time of writing, we have no idea whether our attack is similar to the Bellcore attack.
We make the following assumption as in the Bellcore and DFA announcements.
Assumption: 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. (We will explain later that our attack also works against multiple bit faults).
Without loss of generality, assume that n=pq in RSA is a 512 bit number. Let e be the public exponent which is publicly known and d be the secret exponent which is stored inside the tamperproof device. Let P be a plaintext, then the corresponding ciphertext is
C = P^e (1)
(In the following, only residues modulo n are shown, e.g., we use P^e instead of P^e mod n).
We denote the binary representation of the secret exponent as
d = d511|d510| ...|di|...|d1|d0 (2)
where di, takes value 1 or 0, is the ith bit and where x|y denotes concatenation of x and y. Further, we denote
C0=C, C1=C^2, C2=C^{2^2}, ..., C511=C^{2^511} (3)
Given C and d, we can express the corresponding plaintext P as
P=(C511^d511)(C510^d510)...(Ci^di) ...(C1^d1)(C0^d0) (4)
We assume that the attacker is in physical possession of the tamperproof device and that he can repeat the experiment with the same key by applying external physical effects to obtain outputs due to single bit errors.
To simplify the description, we illustrate our attack by two examples.
EXAMPLE 1:
Suppose that one bit in the binary representation of d in equation (2) is changed from 1 to 0 or vice versa, and that the fault bit position is randomly located.
An attacker arbitrarily chooses a plaintext P and computes the ciphertext C using (1). He then applies external physical effects to the tamperproof device and at the same time asks the device to decrypt C. Assuming that di in (2) is changed to its complement di', then the output of the device will be
P'=(C511^d511)(C510^d510)...(Ci^di') ...(C1^d1)(C0^d0) (5)
Since the attacker possesses P, he can compute
P'/P = Ci^di'/Ci^di (6)
Obviously, if P'/P = 1/Ci, then di = 1, and if P'/P = Ci, then di = 0. The attacker can re-compute Ci and 1/Ci for i = 0, 1, ..., 511, and compares (6) to these values in order to determine one bit of d. The attacker can repeat the above process using either the same plaintext/ciphertext pair or using different plaintext/ ciphertext pairs until he obtains enough information to uncover the binary representation of the secret exponent d.
EXAMPLE 2:
For the sake of simplicity, here we assume that in decrypting a ciphertext, the tamperproof device first computes the data sequence in (3) and then computes (4). We also assume that the attacker applies external physical effects to the tamperproof device to induce an one bit error in Ci, i = 0, 1, ..., 511.
Suppose that the one bit error is in Ci, we denote the corrupted value as Ci'. Then the output from the tamperproof device is
P'=(C511^d511)(C510^d510)...(Ci'^di) ...(C1^d1)(C0^d0) (7)
The attacker can then compute
P'/P = Ci'^di/Ci^di = Ci'/Ci (8)
(Note that di in (8) must be 1.) Suppose that the attacker has computed all the possible Ci'/Ci values in advance (there are a total of 512x512 such values) and stored them somewhere. Now the attacker can compare all these values with P'/P. Once a match is found, the attacker knows i then knows that di is 1. The attacker repeats the above process until he has enough information to determine d.
The above examples are just meant to illustrate the basic ideas of our attack. Anyway, by the two examples we showed that: One bit fault at certain location and time can cause fatal leakage of the secret key. Such leakage gradually increases as the above procedures are repeated using one or multiple pairs of P and C.
It should be noted that our attack also works for multiple bit errors. Assuming two bit faults and consider the scenario of EXAMPLE 2. The possible Ci'/Ci values now increases from 512 x 512 to 512 x 512 x 512. In this case, matching P'/P requires more time, while with large possibility you obtain 2 di's once a match is obtained.
To conclude this research note, we would like to say a few words on how to resist this kind of attacks.
1. The attack may be avoided by calculating values 2 times and checking the two results. However, this approach doubles the computational time. As pointed out by Bellcore, this double computation method also avoids their attack.
2. In many cases, the encryption key e is usually small. So we can verify the result by checking
P^e= C ?
This approach is much more efficient than the double computation approach if e is small.
3. In some protocols for digital signature, a random string is chosen by the smart card and concatenated to a message m which is to be signed by the smart card. For example, m is a 412 binary string given to the smart card. The smart card randomly chooses a 100 bit number r and the output is (C|r)^d. Since r is different each time, the attack does not work in such case.
Added by jya.com October 24, 1996:
See related October 24 announcement 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.
Added by jya.com November 11, 1996:
See comments by Paul Kocher on legacy of fault-induced cryptanalysis.
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.