073
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View 073 as PDF for free.
More details
- Words: 6,921
- Pages: 15
Fault atta ks on RSA with CRT: Con rete Results and Pra ti al Countermeasures
?
C. Aumuller?? P. Bier? ? ? W. Fis hery P. Hofreiterz J.-P. Seifertx In neon Te hnologies Se urity & ChipCard ICs CC TI Con epts & Innovations D-81609 Muni h Germany
Abstra t. This arti le des ribes on rete results and pra ti ally approved ountermeasures
on erning di erential fault atta ks on RSA using the CRT. It espe ially investigates smart ards with a RSA opro essor where any hardware ountermeasure to defeat su h fault atta ks have been swit hed o . This s enario has been hosen in order to ompletely analyze the resulting e e ts and errors o
urring inside the hardware. Using the results of this kind of physi al stress atta k enables the development of ompletely reliable software ountermeasures. Although su
essful RSA atta ks on the investigated hardware have been only possible with an expensive enhan ed laboratory equipment, the e e ts on the unprote ted hardware have been tremendously. This aused lots of analysis e orts to investigate what really happened during the atta k. Indeed, this will be addressed in this paper. We rst report on the nature of the resulting errors within the hardware due to the physi al stress applied to the smart ard. Hereafter, we des ribe the experiments and results with a very eÆ ient and prominent software RSA-CRT DFA ountermeasure. This method ould be shown to be insuÆ ient, i.e., dete ted nearly no error, when we introdu ed stress at the right position during the omputation. Naturally, a detailed error analysis model followed, spe ifying every failure point during the RSA-CRT operation. This model nally allowed to develop and present here new very pra ti ally oriented software ountermeasures hedging the observed and hara terized fault atta ks. Eventually, we present the se urity analysis of our new developed software RSA-CRT DFA ountermeasures. Thanks to their areful spe i ation a
ording to the observed and analyzed errors they resisted all kinds of physi al stress atta ks and were able to dete t any subtle omputation error, thus avoiding to break the smart ard by fault atta ks. Nevertheless, we stress, that although our software ountermeasures have been fully approved by pra ti al experiments, we are onvin ed that only sophisti ated hardware ountermeasures like sensors and lters in ombination with software ountermeasures will be able to provide a se ure and omfortable base to defeat in general any on eivable fault atta ks s enario on smart ards properly.
Fault atta ks, Bell ore atta k, Hardware se urity, Hardware robustness, RSA, Chinese Remainder Theorem, Spike atta ks, Transient fault model, Software ountermeasures. Keywords:
? ?? ???
y z x
Readers should note that In neon Te hnologies Corp. has led an international patent appli ation
ontaining this work.
hristian.aumuellerinfineon. om peter.bierinfineon. om wieland.fis herinfineon. om peter.hofreiterinfineon. om jean-pierre.seifertinfineon. om
1
Introd ution
This paper shows and proves that fault atta ks on RSA with the CRT (also known as Bell ore atta ks) due to [BDL℄ are indeed feasible and devastating if there are no hardware me hanisms (like sensors and lters) nor any appropriate software ountermeasures implemented in the underlying smart ard ICs. However, this does not imply that modern high-se urity smart ard ICs are vulnerable by this kind of atta ks. Instead, it shows that fault tolerant and robust hardware and espe ially sophisti ated hardware ountermeasures are essential for the design of physi al se ure hardware to prevent su h devastating e e ts as investigated in the following. Moreover, we stress that it is impossible in the eld to swit h o these sophisti ated hardware
ountermeasures preventing this kind of atta ks | whi h has been done ex eptionally for our detailed feasibility study on erning the pra ti ality of the Bell ore atta k by a spe i ally designed hardware. In order to provide better se urity for data prote tion under strong en ryption s hemes (e.g., RSA [RSA℄, 3DES [MvOV℄, et .) more and more implementations based on tamper-proof devi es (e.g., smart ard ICs) are proposed. The main reason for this trend is that smart ard ICs provide high reliability and se urity with more memory apa ity and better performan e hara teristi s than onventional magneti stripe ard. The CPU in smart ards ontrols its data input and output and prevents unauthorized a
ess to a smart ard. With spe ial hara teristi s of omputational ability, large memory apa ity and se urity, a large variety of ryptographi appli ations bene t from smart ard ICs. Due to this popular usage of tamper-resistan e, the arising of several new ideas for physi al atta ks against smart ards in 1996 due to [Ko h℄ and [BDL℄ and again 1999 by [KJJ℄, followed by [SQ℄, has attra ted a huge amount of resear h. However, within this vain, most resear h so far fo used on Timing or Power Analysis atta ks. This is surprising as the frauds with smart ards by indu ing faults are reality, f., [A,AK1,AK2℄, whereas no frauds via Timing or Power Analysis atta ks have been reported so far. Moreover, as seen from the s ienti literature, the resear h on faults based ryptanalysis or its pra ti al realization is not very a tive, when ompared with the other side- hannel resear h. Furthermore, no pra ti al investigation of the most interesting and pra ti al s enario, i.e., the so alled Bell ore atta k [BDL℄ on RSA with CRT [RSA,CQ℄ has been reported so far. Indeed, this topi will be for the rst time publi ly addressed within this paper. Thus, it answers a question of Kaliski and Robshaw [KR℄ of how pra ti al these atta ks might be, answered de nitely here by physi ists and the designers and manufa tures of se ure hardware. A tually, the present paper has three main themes. First, we will a tually present a pra ti al
ase study of fault atta ks on smart ards implementations of RSA in CRT mode. We will indeed explain how to realize so alled spike atta ks on smart ards, analyze hereafter their intrinsi omplexity from an atta ker's point of view and reveal an appropriate test equipment to implement su h fault atta ks. Se ond, we will present the resulting errors on ompletely unprote ted hardware and software for RSA in CRT mode. In addition, we will demonstrate the insuÆ ien y of a very prominent and eÆ ient software ountermeasure due to [Sh℄. Third, we will derive from the analysis of the previously obtained resulting errors new software ountermeasures whi h were proved to fully work under extensive spike atta ks. Only very re ently the eld of resear h on fault atta ks and their ountermeasures has been shown some a tivity. For instan e, a series of papers [YJ,YKLM1,YKLM2,JQYY℄ ame up with some new ideas for atta ks s enarios and also new ountermeasures to defeat fault atta ks. The relevan e of this line of resear h to this paper and espe ially its pra ti al relevan e will be dis ussed later within se tion 2. The present paper is organized as follows. Se tion 2 brie y repeats RSA using the CRT and the fault based ryptanalysis of RSA using the CRT a
ording to [BDL,JLQ℄; it also in ludes and dis usses the advantages and limitations of so far publi ly known software ountermeasures to defeat fault atta ks on RSA in CRT mode. Se tion 3 basi ally digs into the real physi s of enfor ing errors during the ryptographi omputation of smart ard ICs. Within se tion 4 we basi ally 2
investigate sophisti ated software ountermeasures derived from our pra ti al observations and our proposed model to ountera t fault atta ks on RSA in CRT mode. We also present pra ti al results whi h were obtained with our ountermeasures. Eventually we will draw some pra ti al
on lusion in se tion 5 on erning software ountermeasures to hedge su h Bell ore atta ks.
2 2.1
Preliminaries The RSA System
Let N = p q be the produ t of two large primes ea h n=2 bits long. To sign a message m 2 ZN using RSA one omputes S := md mod N , where d is the private exponent satisfying e d 1 mod (p 1)(q 1) for the publi exponent e. The omputationally expensive part of signing using RSA is the modular exponentiation of m. For eÆ ien y most implementations exponentiate as follows: using repeated square and multiply they rst ompute Sp := md mod p and hereafter d d Sq := m mod q . They then use the CRT to onstru t the signature S = m mod N . This last CRT step takes negligible time ompared to with the two exponentiations. It is done eÆ iently by
omputing 1 S = Sq + (Sp Sq ) (q mod p) mod p q; (1) using Garner's algorithm, f. [Kn℄. The reason to use the CRT is that the exponentiation using the CRT is mu h faster than square and multiply mod N . To see this, observe that Sp = md mod p = md mod (p 1) mod p. Usually, d is of order N , while d mod (p 1) is of order p. Consequently, omputing Sp requires half as many multipli ations as omputing S dire tly. In addition, intermediate values during the omputation of Sp are only half as big | they are in the range [1; : : : ; p℄, rather than [1; : : : ; N ℄. Clearly, the same arguments are valid for the omputation of Sq . When quadrati time omplexity is used, multiplying two numbers in Zp takes a quarter of the time as multiplying elements in ZN . Hen e,
omputing Sp takes an eight of the time of omputing S dire tly. Thus, omputing Sp and Sq this way takes a quarter of the time of omputing S dire tly. Thus, CRT exponentiation is four times faster than dire t exponentiation. This is why RSA with CRT is the preferred method for generating RSA signatures, f. [CQ,MvOV℄. 2.2
The fault-based ryptanalysis of RSA using CRT
For the sake of ompleteness we brie y re all the fault-based ryptanalysis of RSA using the CRT due to [BDL℄ and assume the above notations. Assume that during the omputation of a RSA signature for a message m via the CRT a random error o
urs during the omputation of Sp , thus yielding the faulty signature part Sp0 , whereas the
omputation of Sq is performed orre tly. Applying now the ombination of Sp0 and Sq via (1) will yield an in orre t signature S 0 di erent from the orre t signature S , i.e., S S 0 6= 0. A
ording to the fault-based ryptanalysis of [BDL,JLQ℄, one obtains the fa torization of N by omputing g d ((m 2.3
(S 0 )e ) mod N; N ) = q:
Simple software ountermeasure to defeat the fault atta k
We will now present some simple ad-ho ountermeasures whi h have been already suggested within [BDL,KR℄ to hedge the faults atta k s enario. One approa h is to perform al ulations twi e and the other approa h suggests to verify the orre tness of the signature by omparing the inverse result with the input. The rst approa h is a very time- onsuming and it annot always provide a satisfa tory solution sin e a permanent error ( aused by a permanenet hardware or software fault implementation bug) may be undete table, even if the fun tion is omputed more than on e. 3
The se ond approa h is to verify the orre tness by omparing the inverse result with the input . A RSA signature S = md mod N an be veri ed by raising S to the eth power and ompare whether m se mod N . Generally, this is not a satisfa tory solution sin e the parameter e ould be a large integer and this he king pro edure be omes time- onsuming. A ompletely di erent but very interesting ountermeasure is the introdu tion of randomness into the RSA signature pro ess. Here, RSA is applied to F (m; r) where F is some formatting fun tion and r is a random string whi h ensures that the user never signs the same message twi e. Furthermore, given en erroneous signature the veri er does not know the full plain-text that was signed. Consequently, the above atta k annot be applied to this modi ed system f. [BDL,BR,KR℄. m
2.4
Shamir's software Countermeasure
Shamir's basi idea, as presented in [Sh℄ is to sele t a random integer t and to do the following
omputations d Spt := m mod p t; d Sqt := m mod q t: In the ase of Spt = Sqt mod t the omputation is de ned to be error free and S is omputed a
ording to the CRT re ombination equation (1). One drawba k in Shamir's method, as pointed out in [JPY℄, is the following. Within the CRT mode of real RSA appli ations the value d is not known, only the values dp = d mod (p 1) and dq = d mod (q 1) are known. Although d an be eÆ iently omputed from dp and dq only, as des ribed in [FS℄, it will de nitely limit the a
eptan e of Shamir's method. Nevertheless, this simple way of he king the omputations orre tness is anyway insuÆ ient as demonstrated later by our pra ti al experiments. But, the new software ountermeasures, as presented later, developed and motivated by our experimental results alleviate the two formerly drawba ks of Shamir's method. 2.5
General remarks on methods to over ome fault atta ks
Only very re ently the eld of resear h on fault atta k ountermeasures has been emerged. For instan e a series of papers [YJ,YKLM1,YKLM2,JQYY℄ assumed that the atta ker has a very pre ise knowledge about the implementation details and espe ially an absolute a
urate ontrol on the timing of his fault indu tion. This possibility, together with an implemented signature
orre tness he k was then used by the above papers to get a
ess to the bits of the private exponent d. However, all the fault atta ks des ribed in [YJ,YKLM1,YKLM1,JQYY℄ an be easily prevented by the various randomization possibilities for the RSA signature algorithm, e.g., randomization of the message m, modul N and the private exponents dp and dq , or simply d. Note that these te hniques must be anyway implemented in a se ure RSA signature algorithm to ountera t other side- hannel atta ks. Moreover, [YKLM1℄ proposed the following very interesting ountermeasure. Their key idea is the assuran e to in uen e the omputation of Sq or the overall omputation of S when an error o
urred during the omputation of Sp , or vi e versa. By the explanation of the ryptanalysis given in se tion 2 it follows, that in this ase no su
essful fault atta k on RSA with CRT is possible. They proposed this idea in order to over ome the problem that an atta ker might simply jump over the spe ial riti al point where the de ision on erning the omputation's orre tness is done. Although su h an atta k seems questionable, it an be simply defeated by a small appropriate software. Unfortunately, re ently it was shown by [BMS℄ that their proposal to perform a so alled infe tive RSA CRT omputation is not se ure, i.e. an be broken ompletely by latti e redu tion methods. 4
3
Physi al fault atta ks realization
First of all, we would like to stress again that modern high-end ryptographi devi es, e.g., smart ards, are usually prote ted by means of various and numerous sophisti ated hardware me hanisms to dete t any intrusion attempt into their system behavior, f. [Ma,NR℄. This is due to the fa t that hardware manufa turers of ryptographi devi es su h as smart ard ICs have been aware of the importan e of prote ting against intrusions by, e.g., external voltage variations, external lo k variations, et . for a long time. However, it should be lear that the design of su h me hanisms is a very diÆ ult engineering task. Su h me hanisms must be able to tolerate natural slight deviations from the standard values of the ele tri al parameter to be safeguarded, in order to ensure proper fun tionality of the underlying devi e within the spe i ed range, as for example des ribed in [ISO℄. And, on the other side they have to dete t very fast and low unnatural deviations from the spe i ed standard range, in order to dete t any atta k attempt by modifying the ele tri al exe ution
onditions to alter a omputation's result. For example, the standard spe i ation for smart ard ICs [ISO℄ allows for the smart ard ICs onta t VCC under normal operating onditions a voltage supply between 4; 5V and 5; 5V. Although there are lots of possibilities to introdu e an error during the ryptographi operation of an unprote ted smart ard hardware, i.e., the CPU working in on ert with a rypto opro essor, we will only explain en detail so alled spikes atta ks. The reason is that spike atta ks are non invasive atta ks, whi h require espe ially no physi al opening and no hemi al preparation of the smart ard IC. Thus, spike atta ks are the most obvious method for atta king smart ard ICs. For further information on various methods how to enfor e erroneous omputations of hips without hardware ountermeasures, we refer to [A,AK1,AK2,Gu1,Gu2,Ko a,Ma℄. Spikes As seen above, a smart ard must be able to tolerate on the onta t VCC a supply voltage between 4; 5V and 5; 5V, where the standard voltage is spe i ed at 5V. Within this range the smart ard will be able to work properly. However, a deviation of the external power supply of mu h more than the spe i ed 10% toleran e ould ause problems for a proper fun tionality of the smart ard IC. Indeed, it ould then lead to a wrong omputation result, provided that the smart ard IC is still able to nish its omputation ompletely. But most often this is not possible, as the spike aused too mu h trouble to the CPU of the smart ard IC. Although a spike seems from the above explanation very simple, a spe i type of a power spike is determined by altogether nine di erent parameters. These nine parameters are determined by a ombination of time and voltage values and as well by the shape of the transition as shown in gure 1. This indi ates the range of di erent parameters whi h must be s anned for penetration atta ks against ryptographi devi es. However, it also reveals the strong requirements for the
orresponding sensor me hanisms. From the former dis ussion of spike atta k, one an envision the diÆ ulties an atta ker is
onfronted with, when he wants to over ome all the a tivated hardware ountermeasures within modern high-se urity smart ard ICs. Amongst them, there a various, numerous and espe ially nely tuned sensors and lters monitoring the frequen y, voltage supply, et ., designed via highest sophisti ated ele troni ally me hanisms. In the eld of PayTV there exist lots of di erent penetration atta ks. For instan e, to lo k old smart ard devi es the TV- hannel is used by the TV ompanies to reprogram the smart ards when onne ted to the de oder. Thus, after their legal usage time the smart ards are exe uting an in nity loop. The following gure 2 shows a lassi al \spike-hardware", whi h is available from the Internet and is used to ra k su h lo ked PayTV smart ards. It does simply spikes on invalidated smart ards in order to leave the programmed in nity loop, whi h was intended to lo k these smart ards. Therefore, these pirate devi es are a tually alled \unlooper"
5
voltage
V3
V2 V1 t1 Fig. 1.
Fig. 2.
t2
t3
t4
time
Spike-parameters de ning the shape of a spe i spike.
\Unlooper" hardware from the internet to ra k PayTV smart ards.
6
3.1
Laboratory setting
In order to systemati ally investigate the e e ts of spikes and espe ially our proposed ountermeasures, we basi ally used the following spike enfor ing hardware set-up, whi h is shown in gure 3. spike generator 1234
trigger
PC spike
Fig. 3.
chip card IC
control/ communication
S hemati of our test equipment.
With su h a test set-up it is indeed possible to enfor e a spike with a very high pre iseness. This is ne essary, if the spike shall enfor e only a tiny random omputation fault rather than a omplete destru tion of the smart ard's omputation, whi h would make the smart ard's omputation result unusable for a su
essful atta k. Through the oupling of the ontrol and ommuni ation of the smart ard with a PC, whi h is running a dedi ated test-software, it is possible to observe and analyze the smart ard's rea tion with respe t to the applied spike-form as dis ussed above, e.g., answering with a orre t/wrong answer sequen e. Now, one has to nd by altering the 9 parameters of the applied spike a set of parameters enabling a tiny random omputation fault, but leaving the smart ard 's main omputation untou hed. 3.2
Results on unprote ted hardware and software
We will now dis uss our results of su
essfully applied spike-atta ks on our spe i ally designed smart ard hardware derived from a typi al low-end smart ard. The design modi ation was basi ally a disenabling of any hardware ountermeasures, to allow fault atta ks on RSA using the CRT. Moreover, for ease of exposition, we have also swit hed o any (hardware and software)
ountermeasures to defeat other lassi al side- hannel atta ks, like Timing Analysis [Ko h℄, Power Analysis [KJJ℄, Ele tromagneti Analysis [SQ℄, et . However, to introdu e a spike at the right position of the RSA with the CRT, one rst must investigate the power pro le of the riti al omputation. Su h a power pro le of our investigated
opro essor is shown in gure 4, whi h we will now explain a little bit more further. The upper line represents the pro le of the smart ard's I =O behavior. The rst I =O a tivity is the start impulse for the smart ard and the se ond peak is the answer sequen e given by the smart ard. Between these two peaks the smart ard is omputing a 2048-bit RSA signature using the CRT. This is shown in the lower line where the main power pro le of the smart ard is depi ted. The RSA-CRT omputation starts at the time blo k 1.5 and ends at the time blo k 9.2. This
an be seen by the fa t that the power onsumption in reases | due to the opro essors a tivity. One immediately re ognizes the two di erent exponentiations, as they are the onsumers whi h need for their whole duration the highest power onsumption. In our ase the rst exponentiation lies in the time frame 1.6 to 5.1, and the se ond exponentiation lies in the time frame 5.3 to 8.8. Between these two exponentiations there is the loading of 7
the new data into the rypto opro essor for the se ond exponentiation and as well the orre tness
he ks of the rst exponentiation. Before the rst exponentiation one re ognizes the loading of the data into the rypto opro essor for the rst exponentiation, after the rst exponentiation the orresponding orre tness he ks and as well the loading of the data into the rypto opro essorand for the se ond exponentiation and after the se ond exponentiation again the orre tness he ks of the se ond exponentiation and nally the CRT ombination of the two partial exponentiations followed eventually by additional orre tness he k for the CRT ombination.
Fig. 4.
Power pro le of RSA with the CRT.
The rst algorithm we atta ked with our spike equipment was the pure RSA signature algorithm using the CRT: input: m; p; q; dp ; dq ; q
:= mdp mod p d Sq := m q mod q S := Sq + ((Sp Sq ) q return(S )
1
mod p
Sp
d
output: m
1
mod p) q
mod N
Before dis ussing the results of our spike atta ks on the above algorithm we note that the inputs p; q; dp ; dq ; q 1 mod p are usually stored in EEPROM, while the message m is stored in RAM. However, to ompute with the data p; q; dp ; dq ; q 1 mod p they must moved during the
omputation from EEPROM into the rypto opro essor. By varying the time when we applied the appropriate spike to the smart ard ICs power supply VCC , we were able to indu e the following di erent error s enarios. 8
Observed error s enarios modi ation of p; q modi ation of dp ; dq modi ation of q 1 mod p wrong answer sequen e of smart ard IC wrong exponentiation mod p wrong exponentiation mod q faulty signature mod p and mod q error during ombination of Sp and Sq Due to the la k of spa e we must refer a omplete dis ussion and interpretation of our observed error s enarios to the full version of the present paper. However, from the above table it learly follows, that an atta ker an enfor e any error he likes, when hitting the orre t time and spike parameters as needed for the underlying unprote ted hardware. Thus, we an on lude that it is absolutely ne essary to have sophisti ated hardware and software ountermeasures to hedge su h kinds of atta ks to break the RSA signature algorithm using the CRT. Within the remaining se tions we will analyze su h already existing software
ountermeasures and also develop new sophisti ated and espe ially more reliable ountermeasures. 3.3
Results on unprote ted hardware with simple software ountermeasures
Motivated by the devastating results obtained within the previous se tion, we hereafter tested the reliability of the software ountermeasures due to [Sh℄ as desribed in se tion 2. Thus, we applied at
arefully hosen time points our formerly hosen spikes parameters to the unprote ted smart ard IC when omputing the following RSA signature algorithm, shown in gure 5. 1 mod p
input: m; p; q; d; q
randomly hoose a short prime r, e.g., 32 bits 0 p := p r 0 dp := d mod (p 1) (r 1) 0 q := q r 0 dq := d mod (q 1) (r 1)
0 := (m mod p0 )dp mod p0 0 0d 0 Sq := (m mod q ) q mod q 0
Sp
0
:= Sp0 mod p 0 Sq := Sq mod q S := Sq + ((Sp
Sp
if
Sq
) q 1 mod p) q
((Sp0 mod r) = (Sq0 mod r)) return(S )
else
then
(error)
return
output: m
d
mod (p q )
Fig. 5.
Shamir's ountermeasure.
We will now brie y summarize in a table the observed errors. But again, due to the la k of spa e we must refer a detailed explanation and dis ussion of the observed errors, their nature 9
and espe ially their se urity onsequen es to the full version of the present paper. But to give an impression of possible problems, onsider the ase that during the omputation of p0 the value of p is hanged to some value p ~, su h that p0 = p~r. Then the orre tness he k mod r will fail. Observed error s enarios re og.? relev.? working? modi ation of p; q time dep. time dep. time dep. modi ation of d; d0p ; d0q time dep. no yes modi ation of q 1 mod p no yes no modi ation of r time dep. time dep. yes wrong exp. mod p prob. 1 1=t yes yes wrong exp. mod q prob. 1 1=t yes yes faulty signature mod p and mod q prob. 1 1=t no no error during omb. of Sp and Sq no yes no modi ation of Sp or Sq time dep. yes no The above table is organized as follows. The rst olumn denotes the kind of error whi h might o
ur. The se ond olumn indi ates whether the ountermeasure re ognizes the indu ed fault, while the se ond indi ates whether the orresponding type of fault reveals the se ret key. Finally, the last olumn says whether the ountermeasure re ognizes the devastating faults.
4
Pra ti al Fault atta ks ountermeasures for unprote ted hardware
Within this se tion we will rst analyze the observed error s enarios from the two former se tions and hereafter propose our new ountermeasures. However, due to the la k of spa e this se tion will be very shortened and we again refer the reader to the full version of our paper. 4.1
Model to understand resulting/possible faults
From the observed error s enario, we have learned by an extensive data analysis the following fa ts. { { {
During the omputation, every input value to the RSA signature algorithm ould be altered to a value di erent from the original value. During the omputation, every variable an be hanged. The only values to trust, are the values whi h are stored in ROM or EEPROM. Armed with this knowledge, we formulated the following he king philosophy: Che k (at least in a probabilisti sense) every omputed intermediate result wrt. its orre tness by relying on trusted values only.
In a rough sense, this he king philosophy is re e ted by gure 6, showing the old and the new
he king philosophy. 4.2
Software ountermeasures derived a
ording to the model
Inspired by the previous se tion and strong eÆ ien y requirements, we developed the following
ountermeasures to hedge the fault atta k s enario on RSA using the CRT. Also it takes into a
ount, that a pra ti al appli ation is given dp and dq only, instead of having a
ess to the full d. Also, it avoids the use of the publi exponent e, whi h is most often not known to the signature algorithm in real appli ations. 10
old checking philosophy d (p)
p
check p RSA
sp
d, p
q
p -1
p * p -1 = 1 (q) ?
m
s
Combine
RSA
sq
d, q
q
d (q)
p
dp
RSA
s pt
dp, pt
mod p
sp
cross
Combine
m check RSA
q
s qt
dq, qt
mod q
sq s
dq
new checking philosophy Fig. 6.
Information ow during he king.
11
check
s
input: m; p; q; dp ; dq ; q
1 mod p
let t be a short prime number, e.g., 16 bits
0 := p t 0 := dp + random1 (p 1) d 0 0 Sp := m p mod p 0 0 if :(p mod p 0 ^ dp mod (p 1) dp )
then return
0 := q t 0 := dq + random2 (q 1) d 0 0 Sq := m q mod q 0 0 if :(q mod q 0 ^ dq mod (q
then return
p
dp
0
(error)
q
dq
0
1) dq )
:= Sp0 mod p 0 Sq := Sq mod q 1 mod p) q S := Sq + ((Sp Sq ) q if :((S mod p = Sp ) ^ (S mod q = Sq ))
(error)
Sp
:= Sp0 mod t := d0p mod (t 1) 0 Sqt := Sq mod t 0 dqt := dq mod (t 1) dqt dpt if (Spt Sqt mod t) return(S )
then return
Spt
dpt
else return
then
(error)
output: m
d
mod (p q )
Fig. 7.
Pra ti ally se ured RSA with CRT.
12
(error)
4.3
Measurement results for enhan ed software ountermeasures
Through extensive penetration tests via spikes on the algorithm shown in gure 6 we obtained the following table proving empiri ally the reliability of our software ountermeasures. Observed error s enarios re og.? relev.? working? 0 0 modi ation of p; p ; q; q yes yes yes modi ation of d0p ; d0q yes yes yes modi ation of q 1 mod p yes yes yes modi ation of t yes yes yes wrong exp. mod p prob. 1 1=t yes yes wrong exp. mod q prob. 1 1=t yes yes faulty signature mod p and mod q prob. 1 1=t no yes error during omb. of Sp and Sq yes yes yes modi ation of Sp or Sq yes yes yes Clearly, the probability that an error is undete ted is equal to 1=t. For t a 64-bit integer, this probability is small enough; t an thus be seen as a se urity parameter.
5
Con lusion
We have shown that the lassi al RSA with CRT fault atta k is in prin ipal feasible when using
ompletely unprote ted mi ro ontrollers and moreover, that also prominent and eÆ ient software
ountermeasures are not always ompletely reliable. Thus, it answers again a question of Kaliski and Robshaw [KR℄ to the aÆrmative, that these atta ks are indeed pra ti al. Moreover, our investigation also reveals that one should test any on eivable ountermeasures in reality against all possible atta k s enarios before trusting them. This was espe ially done with our newly developed software ountermeasures whi h are indeed pra ti al, eÆ ient and fully approved by extensive pra ti al penetration test. We would like to stress again, that our su
essful atta ks have been only possible by swit hing o the whole zoo of implemented hardware ountermeasures. In the eld these me hanisms are always swit hed on to ountera t spike atta ks and lots of other atta ks in order to give the smart ard user a full fun tional tamper-resistant devi e. And indeed, su h me hanisms must be implemented on the ard to prevent other known atta ks rather than
ountera ting the simple (but eÆ ient) atta k on the RSA signature algorithm. So, we lose with an advi e due to Kaliski and Robshaw [KR℄ from the RSA Laboratories that good engineering pra ti es in the design of se ure hardware are essential.
6
A knowledgments
We would like to thank Jorg S hepers for helpful dis ussions.
Referen es [A℄ [AK1℄ [AK2℄ [BDL℄
R. Anderson, Se urity Engineering, John Wiley & Sons, New York, 2001. R. Anderson, M. Kuhn, \Tamper Resistan e { a autionary note", Pro . of 2nd USENIX Workshop on Ele troni Commer e, pp. 1-11, 1996. R. Anderson, M. Kuhn, \Low ost atta ks atta ks on tamper resistant devi es", Pro . of 1997 Se urity Proto ols Workshop, Springer LNCS vol. 1361, pp. 125-136, 1997. D. Boneh, R. A. DeMillo, R. Lipton, \On the Importan e of Eliminating Errors in Cryptographi Computations" Journal of Cryptology 14(2):101-120, 2001.
13
[BDHJ+ ℄ F. Bao, R. H. Deng, Y. Han, A. Jeng, A. D. Narasimbalu, T. Ngair, \Breaking publi key
ryptosystems on tamper resistant dives in the presen e of transient faults", Pro . of 1997 Se urity Proto ols Workshop, Springer LNCS vol. 1361, pp. 115-124, 1997. [BR℄ M. Bellare, P. Rogaway, \The exa t se urity of digital signatures | how to sign with RSA and Rabin", Pro . of EUROCRYPTO '96, Springer LNCS vol. 1070, pp. 399-416, 1996. [BS℄ E. Biham, A. Shamir, \Di erential fault analysis of se ret key ryptosystems", Pro . of CRYPTO '97, Springer LNCS vol. 1294, pp. 513-525, 1997. [BMM℄ I. Biehl, B. Meyer, V. Muller, \Di erential fault atta ks on ellipti urve ryptosystems", Pro . of CRYPTO '00, Springer LNCS vol. 1880, pp. 131-146, 2000. [BMS℄ J. Blomer, A. May, J.-P. Seifert, personal ommuni ation, April 2002. [CQ℄ C. Couvreur, J.-J. Quisquater, \Fast de ipherment algorithm for RSA publi -key ryptosystem", Ele troni s Letters 18(21):905-907, 1982. [FS℄ W. Fis her, J.-P. Seifert, \Note on fast omputation of se ret RSA exponents", Pro . of ACISP '02, Springer LNCS vol. ?, pp. ?-?, 2002. [Gu1℄ P. Gutmann, \Se ure deletion of data from magneti and solid-state memory", Pro . of 6th USENIX Se urity Symposium, pp. 77-89, 1997. [Gu2℄ P. Gutmann, \Data Remanen e in Semi ondu tor Devi es", Pro . of 7th USENIX Se urity Symposium, pp. ?-?, 1998. [HP1℄ H. Hands huh, P. Pailler, \Smart Card Crypto-Copro essors for Publi -Key Cryptography", CryptoBytes 4(1):6-11, 1998. [HP2℄ H. Hands huh, P. Pailler, \Smart Card Crypto-Copro essors for Publi -Key Cryptography", Pro . of CARDIS '98, Springer LNCS vol. 1820, pp. 372-379, 1998. [ISO℄ International Organization for Standardization, \ISO/IEC 7816-3: Ele troni signals and transmission proto ols", http://www.iso. h, 2002. [JLQ℄ M. Joye, A. K. Lenstra, J.-J. Quisquater, \Chinese remaindering based ryptosystem in the presen e of faults", Journal of Cryptology 12(4):241-245, 1999. [JPY℄ M. Joye, P. Pailler, S.-M. Yen, \Se ure Evaluation of Modular Fun tions", Pro . of 2001 International Workshop on Cryptology and Network Se urity, pp. 227-229, 2001. [JQBD℄ M. Joye, J.-J. Quisquater, F. Bao, R. H. Deng, \RSA-type signatures in the presen e of transient faults", Cryptography and Coding , Springer LNCS vol. 1335, pp. 155-160, 1997. [JQYY℄ M. Joye, J.-J. Quisquater, S. M. Yen, M. Yung, \Observability analysis | dete ting when improved ryptosystems fail", Pro . of CT-RSA Conferen e 2002 , Springer LNCS vol. 2271, pp. 17-29, 2002. [KR℄ B. Kaliski, M. J. B. Robshaw, \Comments on some new atta ks on ryptographi devi es", RSA Laboratories Bulletin 5, July 1997. [Kn℄ D. E. Knuth, The Art of Computer Programming, Vol.2: Seminumeri al Algorithms , 3rd ed., Addison-Wesley, Reading MA, 1999. [Ko a℄ O. Ko ar, \Hardwaresi herheit von Mikro hips in Chipkarten", Datens hutz und Datensi herheit 20(7):421-424, 1996. [Ko h℄ P. Ko her, \Timing atta ks on implementations of DiÆe-Hellmann, RSA, DSS and other systems", Pro . of CYRPTO '97, Springer LNCS vol. 1109, pp. 104-113, 1997. [KJJ℄ P. Ko her, J. Ja e, J. Jun, \Di erential Power Analysis", Pro . of CYRPTO '99, Springer LNCS vol. 1666, pp. 388-397, 1999. [Ma℄ D. P. Maher, \Fault indu tion atta ks, tamper resistan e, and hostile reverse engineering in perspe tive", Pro . of Finan ial Cryptography, Springer LNCS vol. 1318, pp. 109-121, 1997. [MvOV℄ A. J. Menezes, P. van Oors hot, S. Vanstone, Handbook of Applied Cryptography, CRC Press, New York, 1997. [NR℄ D. Na
a he, D. M'Raihi, \Cryptographi smart ards", IEEE Mi ro, pp. 14-24, 1996. [Pe℄ I. Petersen, \Chinks in digital armor | Exploiting faults to break smart ard ryptosystems", S ien e News 151(5):78-79, 1997. [RSA℄ R. Rivest, A. Shamir, L. Adleman, \A method for obtaining digital signatures and publi -key
ryptosystems", Comm. of the ACM 21:120-126, 1978. [SQ℄ D. Samyde, J.-J. Quisquater, \Ele troMagneti Analysis (EMA): Measures and Countermeasures for Smart Cards", Pro . of Int. Conf. on Resear h in Smart Cards, E-Smart 2001, Springer LNCS vol. 2140, pp. 200-210, 2001. [Sh℄ A. Shamir, \Method and Apparatus for prote ting publi key s hemes from timing and fault atta ks", U.S. Patent Number 5,991,415, November 1999; also presented at the rump session of EUROCRYPT'97.
14
[YJ℄
S.-M. Yen, M. Joye, \Che king before output may not be enough against fault-based ryptanalysis", IEEE Trans. on Computers 49:967-970, 2000. [YKLM1℄ S.-M. Yen, S.-J. Kim, S.-G. Lim, S.-J. Moon, \RSA Speedup with Residue Number System immune from Hardware fault ryptanalysis", Pro . of the ICISC 2001, Springer LNCS vol. ?, pp. ?-?, 2001. [YKLM2℄ S.-M. Yen, S.-J. Kim, S.-G. Lim, S.-J. Moon, \A ountermeasure against one physi al ryptanalysis may bene t another atta k", Pro . of the ICISC 2001, Springer LNCS vol. ?, pp. ?-?, 2001. [ZM℄ Y. Zheng, T. Matsumoto, \Breaking real-world implementations of ryptosystems by manipulating their random number generation", Pro . of the 1997 Symposium on Cryptography and Information Se urity, Springer LNCS vol. ?, pp. ?-?, 1997.
15
?
C. Aumuller?? P. Bier? ? ? W. Fis hery P. Hofreiterz J.-P. Seifertx In neon Te hnologies Se urity & ChipCard ICs CC TI Con epts & Innovations D-81609 Muni h Germany
Abstra t. This arti le des ribes on rete results and pra ti ally approved ountermeasures
on erning di erential fault atta ks on RSA using the CRT. It espe ially investigates smart ards with a RSA opro essor where any hardware ountermeasure to defeat su h fault atta ks have been swit hed o . This s enario has been hosen in order to ompletely analyze the resulting e e ts and errors o
urring inside the hardware. Using the results of this kind of physi al stress atta k enables the development of ompletely reliable software ountermeasures. Although su
essful RSA atta ks on the investigated hardware have been only possible with an expensive enhan ed laboratory equipment, the e e ts on the unprote ted hardware have been tremendously. This aused lots of analysis e orts to investigate what really happened during the atta k. Indeed, this will be addressed in this paper. We rst report on the nature of the resulting errors within the hardware due to the physi al stress applied to the smart ard. Hereafter, we des ribe the experiments and results with a very eÆ ient and prominent software RSA-CRT DFA ountermeasure. This method ould be shown to be insuÆ ient, i.e., dete ted nearly no error, when we introdu ed stress at the right position during the omputation. Naturally, a detailed error analysis model followed, spe ifying every failure point during the RSA-CRT operation. This model nally allowed to develop and present here new very pra ti ally oriented software ountermeasures hedging the observed and hara terized fault atta ks. Eventually, we present the se urity analysis of our new developed software RSA-CRT DFA ountermeasures. Thanks to their areful spe i ation a
ording to the observed and analyzed errors they resisted all kinds of physi al stress atta ks and were able to dete t any subtle omputation error, thus avoiding to break the smart ard by fault atta ks. Nevertheless, we stress, that although our software ountermeasures have been fully approved by pra ti al experiments, we are onvin ed that only sophisti ated hardware ountermeasures like sensors and lters in ombination with software ountermeasures will be able to provide a se ure and omfortable base to defeat in general any on eivable fault atta ks s enario on smart ards properly.
Fault atta ks, Bell ore atta k, Hardware se urity, Hardware robustness, RSA, Chinese Remainder Theorem, Spike atta ks, Transient fault model, Software ountermeasures. Keywords:
? ?? ???
y z x
Readers should note that In neon Te hnologies Corp. has led an international patent appli ation
ontaining this work.
hristian.aumuellerinfineon. om peter.bierinfineon. om wieland.fis herinfineon. om peter.hofreiterinfineon. om jean-pierre.seifertinfineon. om
1
Introd ution
This paper shows and proves that fault atta ks on RSA with the CRT (also known as Bell ore atta ks) due to [BDL℄ are indeed feasible and devastating if there are no hardware me hanisms (like sensors and lters) nor any appropriate software ountermeasures implemented in the underlying smart ard ICs. However, this does not imply that modern high-se urity smart ard ICs are vulnerable by this kind of atta ks. Instead, it shows that fault tolerant and robust hardware and espe ially sophisti ated hardware ountermeasures are essential for the design of physi al se ure hardware to prevent su h devastating e e ts as investigated in the following. Moreover, we stress that it is impossible in the eld to swit h o these sophisti ated hardware
ountermeasures preventing this kind of atta ks | whi h has been done ex eptionally for our detailed feasibility study on erning the pra ti ality of the Bell ore atta k by a spe i ally designed hardware. In order to provide better se urity for data prote tion under strong en ryption s hemes (e.g., RSA [RSA℄, 3DES [MvOV℄, et .) more and more implementations based on tamper-proof devi es (e.g., smart ard ICs) are proposed. The main reason for this trend is that smart ard ICs provide high reliability and se urity with more memory apa ity and better performan e hara teristi s than onventional magneti stripe ard. The CPU in smart ards ontrols its data input and output and prevents unauthorized a
ess to a smart ard. With spe ial hara teristi s of omputational ability, large memory apa ity and se urity, a large variety of ryptographi appli ations bene t from smart ard ICs. Due to this popular usage of tamper-resistan e, the arising of several new ideas for physi al atta ks against smart ards in 1996 due to [Ko h℄ and [BDL℄ and again 1999 by [KJJ℄, followed by [SQ℄, has attra ted a huge amount of resear h. However, within this vain, most resear h so far fo used on Timing or Power Analysis atta ks. This is surprising as the frauds with smart ards by indu ing faults are reality, f., [A,AK1,AK2℄, whereas no frauds via Timing or Power Analysis atta ks have been reported so far. Moreover, as seen from the s ienti literature, the resear h on faults based ryptanalysis or its pra ti al realization is not very a tive, when ompared with the other side- hannel resear h. Furthermore, no pra ti al investigation of the most interesting and pra ti al s enario, i.e., the so alled Bell ore atta k [BDL℄ on RSA with CRT [RSA,CQ℄ has been reported so far. Indeed, this topi will be for the rst time publi ly addressed within this paper. Thus, it answers a question of Kaliski and Robshaw [KR℄ of how pra ti al these atta ks might be, answered de nitely here by physi ists and the designers and manufa tures of se ure hardware. A tually, the present paper has three main themes. First, we will a tually present a pra ti al
ase study of fault atta ks on smart ards implementations of RSA in CRT mode. We will indeed explain how to realize so alled spike atta ks on smart ards, analyze hereafter their intrinsi omplexity from an atta ker's point of view and reveal an appropriate test equipment to implement su h fault atta ks. Se ond, we will present the resulting errors on ompletely unprote ted hardware and software for RSA in CRT mode. In addition, we will demonstrate the insuÆ ien y of a very prominent and eÆ ient software ountermeasure due to [Sh℄. Third, we will derive from the analysis of the previously obtained resulting errors new software ountermeasures whi h were proved to fully work under extensive spike atta ks. Only very re ently the eld of resear h on fault atta ks and their ountermeasures has been shown some a tivity. For instan e, a series of papers [YJ,YKLM1,YKLM2,JQYY℄ ame up with some new ideas for atta ks s enarios and also new ountermeasures to defeat fault atta ks. The relevan e of this line of resear h to this paper and espe ially its pra ti al relevan e will be dis ussed later within se tion 2. The present paper is organized as follows. Se tion 2 brie y repeats RSA using the CRT and the fault based ryptanalysis of RSA using the CRT a
ording to [BDL,JLQ℄; it also in ludes and dis usses the advantages and limitations of so far publi ly known software ountermeasures to defeat fault atta ks on RSA in CRT mode. Se tion 3 basi ally digs into the real physi s of enfor ing errors during the ryptographi omputation of smart ard ICs. Within se tion 4 we basi ally 2
investigate sophisti ated software ountermeasures derived from our pra ti al observations and our proposed model to ountera t fault atta ks on RSA in CRT mode. We also present pra ti al results whi h were obtained with our ountermeasures. Eventually we will draw some pra ti al
on lusion in se tion 5 on erning software ountermeasures to hedge su h Bell ore atta ks.
2 2.1
Preliminaries The RSA System
Let N = p q be the produ t of two large primes ea h n=2 bits long. To sign a message m 2 ZN using RSA one omputes S := md mod N , where d is the private exponent satisfying e d 1 mod (p 1)(q 1) for the publi exponent e. The omputationally expensive part of signing using RSA is the modular exponentiation of m. For eÆ ien y most implementations exponentiate as follows: using repeated square and multiply they rst ompute Sp := md mod p and hereafter d d Sq := m mod q . They then use the CRT to onstru t the signature S = m mod N . This last CRT step takes negligible time ompared to with the two exponentiations. It is done eÆ iently by
omputing 1 S = Sq + (Sp Sq ) (q mod p) mod p q; (1) using Garner's algorithm, f. [Kn℄. The reason to use the CRT is that the exponentiation using the CRT is mu h faster than square and multiply mod N . To see this, observe that Sp = md mod p = md mod (p 1) mod p. Usually, d is of order N , while d mod (p 1) is of order p. Consequently, omputing Sp requires half as many multipli ations as omputing S dire tly. In addition, intermediate values during the omputation of Sp are only half as big | they are in the range [1; : : : ; p℄, rather than [1; : : : ; N ℄. Clearly, the same arguments are valid for the omputation of Sq . When quadrati time omplexity is used, multiplying two numbers in Zp takes a quarter of the time as multiplying elements in ZN . Hen e,
omputing Sp takes an eight of the time of omputing S dire tly. Thus, omputing Sp and Sq this way takes a quarter of the time of omputing S dire tly. Thus, CRT exponentiation is four times faster than dire t exponentiation. This is why RSA with CRT is the preferred method for generating RSA signatures, f. [CQ,MvOV℄. 2.2
The fault-based ryptanalysis of RSA using CRT
For the sake of ompleteness we brie y re all the fault-based ryptanalysis of RSA using the CRT due to [BDL℄ and assume the above notations. Assume that during the omputation of a RSA signature for a message m via the CRT a random error o
urs during the omputation of Sp , thus yielding the faulty signature part Sp0 , whereas the
omputation of Sq is performed orre tly. Applying now the ombination of Sp0 and Sq via (1) will yield an in orre t signature S 0 di erent from the orre t signature S , i.e., S S 0 6= 0. A
ording to the fault-based ryptanalysis of [BDL,JLQ℄, one obtains the fa torization of N by omputing g d ((m 2.3
(S 0 )e ) mod N; N ) = q:
Simple software ountermeasure to defeat the fault atta k
We will now present some simple ad-ho ountermeasures whi h have been already suggested within [BDL,KR℄ to hedge the faults atta k s enario. One approa h is to perform al ulations twi e and the other approa h suggests to verify the orre tness of the signature by omparing the inverse result with the input. The rst approa h is a very time- onsuming and it annot always provide a satisfa tory solution sin e a permanent error ( aused by a permanenet hardware or software fault implementation bug) may be undete table, even if the fun tion is omputed more than on e. 3
The se ond approa h is to verify the orre tness by omparing the inverse result with the input . A RSA signature S = md mod N an be veri ed by raising S to the eth power and ompare whether m se mod N . Generally, this is not a satisfa tory solution sin e the parameter e ould be a large integer and this he king pro edure be omes time- onsuming. A ompletely di erent but very interesting ountermeasure is the introdu tion of randomness into the RSA signature pro ess. Here, RSA is applied to F (m; r) where F is some formatting fun tion and r is a random string whi h ensures that the user never signs the same message twi e. Furthermore, given en erroneous signature the veri er does not know the full plain-text that was signed. Consequently, the above atta k annot be applied to this modi ed system f. [BDL,BR,KR℄. m
2.4
Shamir's software Countermeasure
Shamir's basi idea, as presented in [Sh℄ is to sele t a random integer t and to do the following
omputations d Spt := m mod p t; d Sqt := m mod q t: In the ase of Spt = Sqt mod t the omputation is de ned to be error free and S is omputed a
ording to the CRT re ombination equation (1). One drawba k in Shamir's method, as pointed out in [JPY℄, is the following. Within the CRT mode of real RSA appli ations the value d is not known, only the values dp = d mod (p 1) and dq = d mod (q 1) are known. Although d an be eÆ iently omputed from dp and dq only, as des ribed in [FS℄, it will de nitely limit the a
eptan e of Shamir's method. Nevertheless, this simple way of he king the omputations orre tness is anyway insuÆ ient as demonstrated later by our pra ti al experiments. But, the new software ountermeasures, as presented later, developed and motivated by our experimental results alleviate the two formerly drawba ks of Shamir's method. 2.5
General remarks on methods to over ome fault atta ks
Only very re ently the eld of resear h on fault atta k ountermeasures has been emerged. For instan e a series of papers [YJ,YKLM1,YKLM2,JQYY℄ assumed that the atta ker has a very pre ise knowledge about the implementation details and espe ially an absolute a
urate ontrol on the timing of his fault indu tion. This possibility, together with an implemented signature
orre tness he k was then used by the above papers to get a
ess to the bits of the private exponent d. However, all the fault atta ks des ribed in [YJ,YKLM1,YKLM1,JQYY℄ an be easily prevented by the various randomization possibilities for the RSA signature algorithm, e.g., randomization of the message m, modul N and the private exponents dp and dq , or simply d. Note that these te hniques must be anyway implemented in a se ure RSA signature algorithm to ountera t other side- hannel atta ks. Moreover, [YKLM1℄ proposed the following very interesting ountermeasure. Their key idea is the assuran e to in uen e the omputation of Sq or the overall omputation of S when an error o
urred during the omputation of Sp , or vi e versa. By the explanation of the ryptanalysis given in se tion 2 it follows, that in this ase no su
essful fault atta k on RSA with CRT is possible. They proposed this idea in order to over ome the problem that an atta ker might simply jump over the spe ial riti al point where the de ision on erning the omputation's orre tness is done. Although su h an atta k seems questionable, it an be simply defeated by a small appropriate software. Unfortunately, re ently it was shown by [BMS℄ that their proposal to perform a so alled infe tive RSA CRT omputation is not se ure, i.e. an be broken ompletely by latti e redu tion methods. 4
3
Physi al fault atta ks realization
First of all, we would like to stress again that modern high-end ryptographi devi es, e.g., smart ards, are usually prote ted by means of various and numerous sophisti ated hardware me hanisms to dete t any intrusion attempt into their system behavior, f. [Ma,NR℄. This is due to the fa t that hardware manufa turers of ryptographi devi es su h as smart ard ICs have been aware of the importan e of prote ting against intrusions by, e.g., external voltage variations, external lo k variations, et . for a long time. However, it should be lear that the design of su h me hanisms is a very diÆ ult engineering task. Su h me hanisms must be able to tolerate natural slight deviations from the standard values of the ele tri al parameter to be safeguarded, in order to ensure proper fun tionality of the underlying devi e within the spe i ed range, as for example des ribed in [ISO℄. And, on the other side they have to dete t very fast and low unnatural deviations from the spe i ed standard range, in order to dete t any atta k attempt by modifying the ele tri al exe ution
onditions to alter a omputation's result. For example, the standard spe i ation for smart ard ICs [ISO℄ allows for the smart ard ICs onta t VCC under normal operating onditions a voltage supply between 4; 5V and 5; 5V. Although there are lots of possibilities to introdu e an error during the ryptographi operation of an unprote ted smart ard hardware, i.e., the CPU working in on ert with a rypto opro essor, we will only explain en detail so alled spikes atta ks. The reason is that spike atta ks are non invasive atta ks, whi h require espe ially no physi al opening and no hemi al preparation of the smart ard IC. Thus, spike atta ks are the most obvious method for atta king smart ard ICs. For further information on various methods how to enfor e erroneous omputations of hips without hardware ountermeasures, we refer to [A,AK1,AK2,Gu1,Gu2,Ko a,Ma℄. Spikes As seen above, a smart ard must be able to tolerate on the onta t VCC a supply voltage between 4; 5V and 5; 5V, where the standard voltage is spe i ed at 5V. Within this range the smart ard will be able to work properly. However, a deviation of the external power supply of mu h more than the spe i ed 10% toleran e ould ause problems for a proper fun tionality of the smart ard IC. Indeed, it ould then lead to a wrong omputation result, provided that the smart ard IC is still able to nish its omputation ompletely. But most often this is not possible, as the spike aused too mu h trouble to the CPU of the smart ard IC. Although a spike seems from the above explanation very simple, a spe i type of a power spike is determined by altogether nine di erent parameters. These nine parameters are determined by a ombination of time and voltage values and as well by the shape of the transition as shown in gure 1. This indi ates the range of di erent parameters whi h must be s anned for penetration atta ks against ryptographi devi es. However, it also reveals the strong requirements for the
orresponding sensor me hanisms. From the former dis ussion of spike atta k, one an envision the diÆ ulties an atta ker is
onfronted with, when he wants to over ome all the a tivated hardware ountermeasures within modern high-se urity smart ard ICs. Amongst them, there a various, numerous and espe ially nely tuned sensors and lters monitoring the frequen y, voltage supply, et ., designed via highest sophisti ated ele troni ally me hanisms. In the eld of PayTV there exist lots of di erent penetration atta ks. For instan e, to lo k old smart ard devi es the TV- hannel is used by the TV ompanies to reprogram the smart ards when onne ted to the de oder. Thus, after their legal usage time the smart ards are exe uting an in nity loop. The following gure 2 shows a lassi al \spike-hardware", whi h is available from the Internet and is used to ra k su h lo ked PayTV smart ards. It does simply spikes on invalidated smart ards in order to leave the programmed in nity loop, whi h was intended to lo k these smart ards. Therefore, these pirate devi es are a tually alled \unlooper"
5
voltage
V3
V2 V1 t1 Fig. 1.
Fig. 2.
t2
t3
t4
time
Spike-parameters de ning the shape of a spe i spike.
\Unlooper" hardware from the internet to ra k PayTV smart ards.
6
3.1
Laboratory setting
In order to systemati ally investigate the e e ts of spikes and espe ially our proposed ountermeasures, we basi ally used the following spike enfor ing hardware set-up, whi h is shown in gure 3. spike generator 1234
trigger
PC spike
Fig. 3.
chip card IC
control/ communication
S hemati of our test equipment.
With su h a test set-up it is indeed possible to enfor e a spike with a very high pre iseness. This is ne essary, if the spike shall enfor e only a tiny random omputation fault rather than a omplete destru tion of the smart ard's omputation, whi h would make the smart ard's omputation result unusable for a su
essful atta k. Through the oupling of the ontrol and ommuni ation of the smart ard with a PC, whi h is running a dedi ated test-software, it is possible to observe and analyze the smart ard's rea tion with respe t to the applied spike-form as dis ussed above, e.g., answering with a orre t/wrong answer sequen e. Now, one has to nd by altering the 9 parameters of the applied spike a set of parameters enabling a tiny random omputation fault, but leaving the smart ard 's main omputation untou hed. 3.2
Results on unprote ted hardware and software
We will now dis uss our results of su
essfully applied spike-atta ks on our spe i ally designed smart ard hardware derived from a typi al low-end smart ard. The design modi ation was basi ally a disenabling of any hardware ountermeasures, to allow fault atta ks on RSA using the CRT. Moreover, for ease of exposition, we have also swit hed o any (hardware and software)
ountermeasures to defeat other lassi al side- hannel atta ks, like Timing Analysis [Ko h℄, Power Analysis [KJJ℄, Ele tromagneti Analysis [SQ℄, et . However, to introdu e a spike at the right position of the RSA with the CRT, one rst must investigate the power pro le of the riti al omputation. Su h a power pro le of our investigated
opro essor is shown in gure 4, whi h we will now explain a little bit more further. The upper line represents the pro le of the smart ard's I =O behavior. The rst I =O a tivity is the start impulse for the smart ard and the se ond peak is the answer sequen e given by the smart ard. Between these two peaks the smart ard is omputing a 2048-bit RSA signature using the CRT. This is shown in the lower line where the main power pro le of the smart ard is depi ted. The RSA-CRT omputation starts at the time blo k 1.5 and ends at the time blo k 9.2. This
an be seen by the fa t that the power onsumption in reases | due to the opro essors a tivity. One immediately re ognizes the two di erent exponentiations, as they are the onsumers whi h need for their whole duration the highest power onsumption. In our ase the rst exponentiation lies in the time frame 1.6 to 5.1, and the se ond exponentiation lies in the time frame 5.3 to 8.8. Between these two exponentiations there is the loading of 7
the new data into the rypto opro essor for the se ond exponentiation and as well the orre tness
he ks of the rst exponentiation. Before the rst exponentiation one re ognizes the loading of the data into the rypto opro essor for the rst exponentiation, after the rst exponentiation the orresponding orre tness he ks and as well the loading of the data into the rypto opro essorand for the se ond exponentiation and after the se ond exponentiation again the orre tness he ks of the se ond exponentiation and nally the CRT ombination of the two partial exponentiations followed eventually by additional orre tness he k for the CRT ombination.
Fig. 4.
Power pro le of RSA with the CRT.
The rst algorithm we atta ked with our spike equipment was the pure RSA signature algorithm using the CRT: input: m; p; q; dp ; dq ; q
:= mdp mod p d Sq := m q mod q S := Sq + ((Sp Sq ) q return(S )
1
mod p
Sp
d
output: m
1
mod p) q
mod N
Before dis ussing the results of our spike atta ks on the above algorithm we note that the inputs p; q; dp ; dq ; q 1 mod p are usually stored in EEPROM, while the message m is stored in RAM. However, to ompute with the data p; q; dp ; dq ; q 1 mod p they must moved during the
omputation from EEPROM into the rypto opro essor. By varying the time when we applied the appropriate spike to the smart ard ICs power supply VCC , we were able to indu e the following di erent error s enarios. 8
Observed error s enarios modi ation of p; q modi ation of dp ; dq modi ation of q 1 mod p wrong answer sequen e of smart ard IC wrong exponentiation mod p wrong exponentiation mod q faulty signature mod p and mod q error during ombination of Sp and Sq Due to the la k of spa e we must refer a omplete dis ussion and interpretation of our observed error s enarios to the full version of the present paper. However, from the above table it learly follows, that an atta ker an enfor e any error he likes, when hitting the orre t time and spike parameters as needed for the underlying unprote ted hardware. Thus, we an on lude that it is absolutely ne essary to have sophisti ated hardware and software ountermeasures to hedge su h kinds of atta ks to break the RSA signature algorithm using the CRT. Within the remaining se tions we will analyze su h already existing software
ountermeasures and also develop new sophisti ated and espe ially more reliable ountermeasures. 3.3
Results on unprote ted hardware with simple software ountermeasures
Motivated by the devastating results obtained within the previous se tion, we hereafter tested the reliability of the software ountermeasures due to [Sh℄ as desribed in se tion 2. Thus, we applied at
arefully hosen time points our formerly hosen spikes parameters to the unprote ted smart ard IC when omputing the following RSA signature algorithm, shown in gure 5. 1 mod p
input: m; p; q; d; q
randomly hoose a short prime r, e.g., 32 bits 0 p := p r 0 dp := d mod (p 1) (r 1) 0 q := q r 0 dq := d mod (q 1) (r 1)
0 := (m mod p0 )dp mod p0 0 0d 0 Sq := (m mod q ) q mod q 0
Sp
0
:= Sp0 mod p 0 Sq := Sq mod q S := Sq + ((Sp
Sp
if
Sq
) q 1 mod p) q
((Sp0 mod r) = (Sq0 mod r)) return(S )
else
then
(error)
return
output: m
d
mod (p q )
Fig. 5.
Shamir's ountermeasure.
We will now brie y summarize in a table the observed errors. But again, due to the la k of spa e we must refer a detailed explanation and dis ussion of the observed errors, their nature 9
and espe ially their se urity onsequen es to the full version of the present paper. But to give an impression of possible problems, onsider the ase that during the omputation of p0 the value of p is hanged to some value p ~, su h that p0 = p~r. Then the orre tness he k mod r will fail. Observed error s enarios re og.? relev.? working? modi ation of p; q time dep. time dep. time dep. modi ation of d; d0p ; d0q time dep. no yes modi ation of q 1 mod p no yes no modi ation of r time dep. time dep. yes wrong exp. mod p prob. 1 1=t yes yes wrong exp. mod q prob. 1 1=t yes yes faulty signature mod p and mod q prob. 1 1=t no no error during omb. of Sp and Sq no yes no modi ation of Sp or Sq time dep. yes no The above table is organized as follows. The rst olumn denotes the kind of error whi h might o
ur. The se ond olumn indi ates whether the ountermeasure re ognizes the indu ed fault, while the se ond indi ates whether the orresponding type of fault reveals the se ret key. Finally, the last olumn says whether the ountermeasure re ognizes the devastating faults.
4
Pra ti al Fault atta ks ountermeasures for unprote ted hardware
Within this se tion we will rst analyze the observed error s enarios from the two former se tions and hereafter propose our new ountermeasures. However, due to the la k of spa e this se tion will be very shortened and we again refer the reader to the full version of our paper. 4.1
Model to understand resulting/possible faults
From the observed error s enario, we have learned by an extensive data analysis the following fa ts. { { {
During the omputation, every input value to the RSA signature algorithm ould be altered to a value di erent from the original value. During the omputation, every variable an be hanged. The only values to trust, are the values whi h are stored in ROM or EEPROM. Armed with this knowledge, we formulated the following he king philosophy: Che k (at least in a probabilisti sense) every omputed intermediate result wrt. its orre tness by relying on trusted values only.
In a rough sense, this he king philosophy is re e ted by gure 6, showing the old and the new
he king philosophy. 4.2
Software ountermeasures derived a
ording to the model
Inspired by the previous se tion and strong eÆ ien y requirements, we developed the following
ountermeasures to hedge the fault atta k s enario on RSA using the CRT. Also it takes into a
ount, that a pra ti al appli ation is given dp and dq only, instead of having a
ess to the full d. Also, it avoids the use of the publi exponent e, whi h is most often not known to the signature algorithm in real appli ations. 10
old checking philosophy d (p)
p
check p RSA
sp
d, p
q
p -1
p * p -1 = 1 (q) ?
m
s
Combine
RSA
sq
d, q
q
d (q)
p
dp
RSA
s pt
dp, pt
mod p
sp
cross
Combine
m check RSA
q
s qt
dq, qt
mod q
sq s
dq
new checking philosophy Fig. 6.
Information ow during he king.
11
check
s
input: m; p; q; dp ; dq ; q
1 mod p
let t be a short prime number, e.g., 16 bits
0 := p t 0 := dp + random1 (p 1) d 0 0 Sp := m p mod p 0 0 if :(p mod p 0 ^ dp mod (p 1) dp )
then return
0 := q t 0 := dq + random2 (q 1) d 0 0 Sq := m q mod q 0 0 if :(q mod q 0 ^ dq mod (q
then return
p
dp
0
(error)
q
dq
0
1) dq )
:= Sp0 mod p 0 Sq := Sq mod q 1 mod p) q S := Sq + ((Sp Sq ) q if :((S mod p = Sp ) ^ (S mod q = Sq ))
(error)
Sp
:= Sp0 mod t := d0p mod (t 1) 0 Sqt := Sq mod t 0 dqt := dq mod (t 1) dqt dpt if (Spt Sqt mod t) return(S )
then return
Spt
dpt
else return
then
(error)
output: m
d
mod (p q )
Fig. 7.
Pra ti ally se ured RSA with CRT.
12
(error)
4.3
Measurement results for enhan ed software ountermeasures
Through extensive penetration tests via spikes on the algorithm shown in gure 6 we obtained the following table proving empiri ally the reliability of our software ountermeasures. Observed error s enarios re og.? relev.? working? 0 0 modi ation of p; p ; q; q yes yes yes modi ation of d0p ; d0q yes yes yes modi ation of q 1 mod p yes yes yes modi ation of t yes yes yes wrong exp. mod p prob. 1 1=t yes yes wrong exp. mod q prob. 1 1=t yes yes faulty signature mod p and mod q prob. 1 1=t no yes error during omb. of Sp and Sq yes yes yes modi ation of Sp or Sq yes yes yes Clearly, the probability that an error is undete ted is equal to 1=t. For t a 64-bit integer, this probability is small enough; t an thus be seen as a se urity parameter.
5
Con lusion
We have shown that the lassi al RSA with CRT fault atta k is in prin ipal feasible when using
ompletely unprote ted mi ro ontrollers and moreover, that also prominent and eÆ ient software
ountermeasures are not always ompletely reliable. Thus, it answers again a question of Kaliski and Robshaw [KR℄ to the aÆrmative, that these atta ks are indeed pra ti al. Moreover, our investigation also reveals that one should test any on eivable ountermeasures in reality against all possible atta k s enarios before trusting them. This was espe ially done with our newly developed software ountermeasures whi h are indeed pra ti al, eÆ ient and fully approved by extensive pra ti al penetration test. We would like to stress again, that our su
essful atta ks have been only possible by swit hing o the whole zoo of implemented hardware ountermeasures. In the eld these me hanisms are always swit hed on to ountera t spike atta ks and lots of other atta ks in order to give the smart ard user a full fun tional tamper-resistant devi e. And indeed, su h me hanisms must be implemented on the ard to prevent other known atta ks rather than
ountera ting the simple (but eÆ ient) atta k on the RSA signature algorithm. So, we lose with an advi e due to Kaliski and Robshaw [KR℄ from the RSA Laboratories that good engineering pra ti es in the design of se ure hardware are essential.
6
A knowledgments
We would like to thank Jorg S hepers for helpful dis ussions.
Referen es [A℄ [AK1℄ [AK2℄ [BDL℄
R. Anderson, Se urity Engineering, John Wiley & Sons, New York, 2001. R. Anderson, M. Kuhn, \Tamper Resistan e { a autionary note", Pro . of 2nd USENIX Workshop on Ele troni Commer e, pp. 1-11, 1996. R. Anderson, M. Kuhn, \Low ost atta ks atta ks on tamper resistant devi es", Pro . of 1997 Se urity Proto ols Workshop, Springer LNCS vol. 1361, pp. 125-136, 1997. D. Boneh, R. A. DeMillo, R. Lipton, \On the Importan e of Eliminating Errors in Cryptographi Computations" Journal of Cryptology 14(2):101-120, 2001.
13
[BDHJ+ ℄ F. Bao, R. H. Deng, Y. Han, A. Jeng, A. D. Narasimbalu, T. Ngair, \Breaking publi key
ryptosystems on tamper resistant dives in the presen e of transient faults", Pro . of 1997 Se urity Proto ols Workshop, Springer LNCS vol. 1361, pp. 115-124, 1997. [BR℄ M. Bellare, P. Rogaway, \The exa t se urity of digital signatures | how to sign with RSA and Rabin", Pro . of EUROCRYPTO '96, Springer LNCS vol. 1070, pp. 399-416, 1996. [BS℄ E. Biham, A. Shamir, \Di erential fault analysis of se ret key ryptosystems", Pro . of CRYPTO '97, Springer LNCS vol. 1294, pp. 513-525, 1997. [BMM℄ I. Biehl, B. Meyer, V. Muller, \Di erential fault atta ks on ellipti urve ryptosystems", Pro . of CRYPTO '00, Springer LNCS vol. 1880, pp. 131-146, 2000. [BMS℄ J. Blomer, A. May, J.-P. Seifert, personal ommuni ation, April 2002. [CQ℄ C. Couvreur, J.-J. Quisquater, \Fast de ipherment algorithm for RSA publi -key ryptosystem", Ele troni s Letters 18(21):905-907, 1982. [FS℄ W. Fis her, J.-P. Seifert, \Note on fast omputation of se ret RSA exponents", Pro . of ACISP '02, Springer LNCS vol. ?, pp. ?-?, 2002. [Gu1℄ P. Gutmann, \Se ure deletion of data from magneti and solid-state memory", Pro . of 6th USENIX Se urity Symposium, pp. 77-89, 1997. [Gu2℄ P. Gutmann, \Data Remanen e in Semi ondu tor Devi es", Pro . of 7th USENIX Se urity Symposium, pp. ?-?, 1998. [HP1℄ H. Hands huh, P. Pailler, \Smart Card Crypto-Copro essors for Publi -Key Cryptography", CryptoBytes 4(1):6-11, 1998. [HP2℄ H. Hands huh, P. Pailler, \Smart Card Crypto-Copro essors for Publi -Key Cryptography", Pro . of CARDIS '98, Springer LNCS vol. 1820, pp. 372-379, 1998. [ISO℄ International Organization for Standardization, \ISO/IEC 7816-3: Ele troni signals and transmission proto ols", http://www.iso. h, 2002. [JLQ℄ M. Joye, A. K. Lenstra, J.-J. Quisquater, \Chinese remaindering based ryptosystem in the presen e of faults", Journal of Cryptology 12(4):241-245, 1999. [JPY℄ M. Joye, P. Pailler, S.-M. Yen, \Se ure Evaluation of Modular Fun tions", Pro . of 2001 International Workshop on Cryptology and Network Se urity, pp. 227-229, 2001. [JQBD℄ M. Joye, J.-J. Quisquater, F. Bao, R. H. Deng, \RSA-type signatures in the presen e of transient faults", Cryptography and Coding , Springer LNCS vol. 1335, pp. 155-160, 1997. [JQYY℄ M. Joye, J.-J. Quisquater, S. M. Yen, M. Yung, \Observability analysis | dete ting when improved ryptosystems fail", Pro . of CT-RSA Conferen e 2002 , Springer LNCS vol. 2271, pp. 17-29, 2002. [KR℄ B. Kaliski, M. J. B. Robshaw, \Comments on some new atta ks on ryptographi devi es", RSA Laboratories Bulletin 5, July 1997. [Kn℄ D. E. Knuth, The Art of Computer Programming, Vol.2: Seminumeri al Algorithms , 3rd ed., Addison-Wesley, Reading MA, 1999. [Ko a℄ O. Ko ar, \Hardwaresi herheit von Mikro hips in Chipkarten", Datens hutz und Datensi herheit 20(7):421-424, 1996. [Ko h℄ P. Ko her, \Timing atta ks on implementations of DiÆe-Hellmann, RSA, DSS and other systems", Pro . of CYRPTO '97, Springer LNCS vol. 1109, pp. 104-113, 1997. [KJJ℄ P. Ko her, J. Ja e, J. Jun, \Di erential Power Analysis", Pro . of CYRPTO '99, Springer LNCS vol. 1666, pp. 388-397, 1999. [Ma℄ D. P. Maher, \Fault indu tion atta ks, tamper resistan e, and hostile reverse engineering in perspe tive", Pro . of Finan ial Cryptography, Springer LNCS vol. 1318, pp. 109-121, 1997. [MvOV℄ A. J. Menezes, P. van Oors hot, S. Vanstone, Handbook of Applied Cryptography, CRC Press, New York, 1997. [NR℄ D. Na
a he, D. M'Raihi, \Cryptographi smart ards", IEEE Mi ro, pp. 14-24, 1996. [Pe℄ I. Petersen, \Chinks in digital armor | Exploiting faults to break smart ard ryptosystems", S ien e News 151(5):78-79, 1997. [RSA℄ R. Rivest, A. Shamir, L. Adleman, \A method for obtaining digital signatures and publi -key
ryptosystems", Comm. of the ACM 21:120-126, 1978. [SQ℄ D. Samyde, J.-J. Quisquater, \Ele troMagneti Analysis (EMA): Measures and Countermeasures for Smart Cards", Pro . of Int. Conf. on Resear h in Smart Cards, E-Smart 2001, Springer LNCS vol. 2140, pp. 200-210, 2001. [Sh℄ A. Shamir, \Method and Apparatus for prote ting publi key s hemes from timing and fault atta ks", U.S. Patent Number 5,991,415, November 1999; also presented at the rump session of EUROCRYPT'97.
14
[YJ℄
S.-M. Yen, M. Joye, \Che king before output may not be enough against fault-based ryptanalysis", IEEE Trans. on Computers 49:967-970, 2000. [YKLM1℄ S.-M. Yen, S.-J. Kim, S.-G. Lim, S.-J. Moon, \RSA Speedup with Residue Number System immune from Hardware fault ryptanalysis", Pro . of the ICISC 2001, Springer LNCS vol. ?, pp. ?-?, 2001. [YKLM2℄ S.-M. Yen, S.-J. Kim, S.-G. Lim, S.-J. Moon, \A ountermeasure against one physi al ryptanalysis may bene t another atta k", Pro . of the ICISC 2001, Springer LNCS vol. ?, pp. ?-?, 2001. [ZM℄ Y. Zheng, T. Matsumoto, \Breaking real-world implementations of ryptosystems by manipulating their random number generation", Pro . of the 1997 Symposium on Cryptography and Information Se urity, Springer LNCS vol. ?, pp. ?-?, 1997.
15
