Feng Bao (baofeng@iss.nus.sg)
Robert Deng (deng@iss.nus.sg)
Yongfei Han (yfhan@iss.nus.sg)
Albert Jeng (jeng@iss.nus.sg)
Desai Narasimhalu (desai@iss.nus.sg)
Teow Hin Nagir (teowhin@iss.nus.sg)
Information Security Group
Institute of Systems Science
National University of Singapore
29th October 1996
1. SUMMARY
In September 1996, 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 announcement, it is impossible to perform a meaningful assessment of this attack until more detailed information becomes available. On 18th October 1996,Biham and 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. In Section 2, we first report our attack and then A. K. Lenstra's attack to RSA-like cryptosystems on tamperproof devices. At the time of writing, we have no idea whether our attack is similar to the Bellcore attack. Our attack to RSA and its countermeasures was first posted at the web site of the IEEE Computer Society's Cipher News Letters on the 23rd and 24th October 1996, respectively (see http://www.itd.nrl.navy.mil/ITD/5540/ ieee/cipher/news-items/961022.tampernews.html). Right after that, Lenstra sent us his memo entitled " Memo On RSA Signature Generation In The Presence Of Faults" in a private communication. The memo can be obtained from the author at arjen.lenstra@citicorp.com.
The basic concept of our attack to RSA can be extended to attack discrete logarithm based signature schemes. In Section 3, we show how to attack the ElGamal signature scheme.
Assumption: as in the Bellcore and DFA announcements, we assume 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 faults at random bit locations in a tamperproof device at some random intermediate stage in the cryptographic computation. The faults in the random bit locations do not influence the code itself, i. e., that the program itself does not crash, and that only some of the values it operates upon are affected. It is further assumed that the attacker is in physical possession of the tamperproof device and that he can repeat the experiment with the same private key by applying external physical effects to obtain outputs due to faults.
2. ATTACKING THE RSA SCHEME
Let n = pq be the product of two primes p and q in RSA, e be the public exponent which is publicly known and d be the private exponent which is stored inside the tamperproof device. Let M be a plaintext, then the corresponding ciphertext is C = P^e mod n. Denote the binary representation of the private exponent as d = d(t-1)|d(t-2)| ...|d(i)|...|d(1)|d(0), where d(i), takes value 1 or 0, is the ith bit, t is the number of bits of d, and x|y denotes concatenation of x and y. Further, we denote C(0)= C, C(1) = C^2 mod n, C(2) = C^{2^2} mod n, ..., C(t-1) = C^(2^(t-1)). Given C and d, the corresponding plaintext M can be expressed as M =(C(t-1)^d(t-1))(C(t-2)^d(t- 2))...(C(i)^d(i)) ...(C(1)^d(1))(C(0)^d(0))mod n.
Attack 1:
Suppose that one bit in the binary representation of d is changed from 1 to 0 or vice versa, and that the faulty bit position is randomly located. An attacker arbitrarily chooses a plaintext M and computes the ciphertext C. He then applies external physical effects to the tamperproof device and at the same time asks the device to decrypt C. Assuming that d(i)is changed to its complement d(i)', then the output of the device will be M'= C(t-1)^d(t- 1))(C(t-2)^d(t-2))...(C(i)^d(i)') ...(C(1)^d(1))(C(0)^d(0)) mod n. Since he now possesses both M and M', he can compute M'/M = C(i)^d(i)'/C(i)^d(i) mod n. Obviously, if M'/M = 1/C(i) mod n, then d(i) = 1, and if M'/M = C(i) mod n, then d(i) = 0. The attacker can pre-compute C(i) and 1/C(i) mod n for i = 0, 1, ..., t-1, and compares M'/M mod n to these values in order to determine one bit of d. He repeats the above process using either the same plaintext/ ciphertext pair or using different plaintext/ciphertext pairs until he finds enough information to obtain d.
Attack 2:
For the sake of simplicity, here we assume that in decrypting a ciphertext, the tamperproof device first computes the data sequence C(i) and then computes M =(C(t-1)^d(t-1))(C(t-2)^d(t-2))...(C(i)^d(i)) ...(C(1)^d(1))(C(0)^d(0))mod n. We also assume that one bit error is induced in C(i), i = 0, 1, ..., t-1.
Suppose that the one bit error is in C(i), we denote the corrupted value as C(i)'. Then the output from the tamperproof device is M' =(C(t-1)^d(t-1))(C(t- 2)^d(t-2))...(C(i)'^d(i)) ...(C(1)^d(1))(C(0)^d(0))mod n. The attacker computes M'/M = C(i)'^d(i)/C(i)^d(i) = C(i)'/C(i) mod n (note that d(i) in this ratio must be 1). He can compute all the possible C(i)'/C(i) mod n values in advance (there are a total of t^2 such values) and store them somewhere. Now the attacker compares all these values with M'/M mod n. Once a match is found, he knows i and then knows that d(i) is 1. The above procedure is repeated until enough information is obtained to determine d.
The above two 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 M and C.
It should be noted that our attack also works for multiple bit errors. Assuming two bit faults and consider the scenario of Attack 2. The possible M'/M mod n values now increases from t^2 to t^3. In this case, matching M'/M mod n with one of these values requires more time, while with large possibility one obtain two d(i)s once a match is obtained.
Lenstra's Attack to RSA with Chinese Remainder Algorithm:
The signature S a message M equals M^d mod n and thus S^e mod n is again equal to M mod n. It is well known that S can be computed by computing u = M^d mod p and v = M^d mod q, and by combining u and v using the Chinese Remainder algorithm. If a fault occurs in the course of the computation of the signature, the resulting value, denoted as S', will most likely not satisfy M = S'^d mod n. If, however, the fault occurred only during the computation of say, u, and if v and the Chinese Remainder Algorithm were carried out correctly, then the resulting faulty signature S' satisfies S'^e = M mod q, but the same congruence mod p does not hold. Therefore, q divides S'^e - M but p does not divide S'^e - M, so that a factor of n may be discovered by the recipient of the faulty signature S' by computing the greatest common divisor of n and S'^e - M. This attack is very powerful and it requires only one faulty signature. On the other hand, it applies only to the case when RSA is implemented based on the Chinese Remainder Algorithm; while our attack is independent of the RSA implementation. Lenstra's memo also contains an attack against RSA without Chinese Remainder Algorithm which is slightly different from ours.
Some Possible Countermeasures:
a) The attacks may be avoided by calculating the output 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.
b) In many cases, the encryption key e is usually small. So we can verify the result by checking M^e = C mod n? It is much more efficient than the double computation approach if e is small. This approach has been discovered independently by Lenstra.
c) 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 (M|r)^d mod n. Since r is different each time, the attack does not work in such case.
d) In the case where e is large and where the tamperproof device is required to compute C^d mod n, the following efficient method may be used to counter the attack. The tamperproof device generates a random number r and computes r^d mod n. This can be done in advance, i.e., before C is input and when the device is idle. To compute C^d mod n, the device first computes rC mod n, then (rC)^d mod n, and finally (rC)^d/r^d mod n. If no fault takes place, the output is obviously correct. If any fault takes place, the output is masked by r. Since r is unknown to the attacker and different for every decryption, our attack does not work.
It should be pointed out that a) - d) works against our attacks while only a) - c) works against Lenstra's attack.
3. ATTACKING DISCRETE LOGARITHM BASED SCHEMES
The general concept of attacking RSA scheme can be applied to attack against discrete logarithm based public key cryptosystems. We have successfully worked out procedures to attack DSA, the ElGamal signature scheme and the Schnorr signature scheme. The methods of attacking DSA and the Schnoor scheme are very similar to that used to attack against the ElGamal scheme; therefore, details of the attacks against the Schnorr scheme and DSA will not be shown here but will be included in the final paper. In the following, we will illustrate our idea via the ElGamal signature scheme.
In the ElGamal signature scheme, to generate a private and public key pair, we first choose a prime p, and two random numbers, g and x, such that both g and x are less than p. The private key is x and the public key is (y = g^x mod p, g, p).
To generate a signature on a message m, the signer first picks a random k such that k is relatively prime to p - 1. She then computes a = g^k mod p and b = (m - xa)/k mod (p-1). The signature is the pair a and b. To verify the signature, the verifier confirms that (y^a)(a^b) = g^m mod p.
Denote the binary representation of the private key as x = x(t-1)|x(t-2)| ...|x(i)|...|x(1)|x(0), where x(i)is the ith bit and where t is the number of bits in x. We assume that the attacker is in physical possession of the tamperproof device and that he can apply external physical effects to induce one bit error at a random location in x and then obtain a faulty output.
The attacker applies external physical effects to the tamperproof device and at the same time asks the device to sign a message m. Assuming that x(i) in x is changed to its complement x(i)' and denote the corrupted x as x'. Then the outputs of the device will be a = g^k mod p and b'= (m - x'a)/k mod (p-1). Using a, b', m, and the signer's public key (y, p, g), the attacker can compute g^m mod p and (y^a)(a^b') mod p. It is easy to see that (y^a)(a^b') = (g^m)(g^(xa-x'a)) mod p. The attacker now computes g^m/((y^a)(a^b')) = g^(x'a)/g^(xa) mod p. Let r = g^a mod p, r(0) = r, r(1)= r^2 mod p, ..., r(t- 1) = r^(2^(t-1)) mod p. Then g^(xa) = r^x = (r(t-1)^x(t-1))(r(t-2)^x(t- 2))...(r(i)^x(i)) ...(r(0)^x(0)) mod p and g^(x'a) = r^x' = (r(t-1)^x(t- 1))(r(t-2)^x(t-2))...(r(i)^x(i)') ...(r(0)^x(0)) mod p. Therefore, g^m/ ((y^a)(a^b')) = r(i)^x(i)'/r(i)^x(i) mod p. Obviously, if the ratio is 1/ r(i) mod p, then x(i) = 1, and if it is r(i), then x(i) = 0. The attacker computes r(i) and 1/r(i) for i = 0, 1, ..., t - 1, and compares the ratio to these values in order to determine one bit of x. The attacker repeats the above process until he uncovers the binary representation of x.
The above attack also works for multiple bit errors in x. Assuming j bit faults, then g^m/((y^a)(a^b'))mod p needs to be compared with (2t)^j possible values instead of 2t as in the single fault case.
One countermeasure to the attack we'd like to suggest is that the tamperproof device stores both x and 1/x. Right after computing b'= (m - x'a)/ k mod (p-1), the device verifies the value of b' by comparing a with (m - kb')(1/x) mod (p-1). If these two values are the same, the result is considered correct; otherwise, the device is reset.