Paul Kocher
e-mail: paul@cryptography.com

() Transfer Olga Buksheva, Pavel Semjanov, 1998.
e-mail: psw@ssl.stu.neva.ru? subject=timing attack

Theses. Accurately measuring quantity of time necessary for operations with closed keys, the malefactor can find a constant exponent in the scheme of Diffi-Hellmana, факторизованные keys in RSA, and also crack and others криптосистемы. If the attacked system is vulnerable, attack can be inexpensive in the computing relation and will be frequent for it to be required only a known text in code. Existing systems are potentially vulnerable, including криптомаркеры (tokens), network криптосистемы and other appendices where the attacking is capable to make exact enough gaugings of time. Methods for prevention of attack to systems RSA and Diffi-Hellmana are presented. Some криптосистемы should be reconsidered for protection against such attacks, and new reports and algorithms should include means for prevention of attacks by the time analysis (timing attacks).

Keywords: the time analysis, криптоанализ, RSA, Diffi-Hellman, DSS.

Криптосистемы often use various quantity of time for processing of the various entrance data. The reasons of it include optimisation on time, hits in a cache, processor instructions (multiplication and division type) which have no fixed number of steps, and also many other things. Speed usually depends on a key of enciphering and the entrance data (the open or ciphered text). While it is known that, generally speaking, time channels can pass the data or keys through the protected perimetre of processing, the intuition prompts that time characteristics can open only the insignificant information about криптосистеме (type хэммингского key weight). However the attack presented here, is capable to use time measurements in vulnerable systems for a finding of all confidential key.

In algorithms of Diffi-Hellmana DH [2] and RSA [8] it is necessary to calculate R=y^x mod n where n - it is known, and y can be found by interception. The purpose attacking - to find a confidential key x. For attack realisation it is necessary, that the victim calculated y^x mod n for several values y where y, n and time of calculations are known to the attacking. (If confidential an exhibitor x will vary for each operation, attack will not work). The necessary information and time of calculations can be received passive interception as the attacking can write down the messages sent to the purpose of attack and to measure time of reception of the answer for everyone y.

Attack can be carried out at any realisation of algorithm of modular exponentiation where calculation time is not fixed, but at first it is better to consider usual algorithm of calculation R = y^x mod n, where x - length w bit:

    Let s0 = 1. 
    For k = 0 upto w-1: 
      If (bit k of x) is 1 then 
        Let Rk = (sk Ћ y) mod n. 
      Else 
        Let Rk = sk. 
      Let sk+1 = Rk2 mod n. 
    EndFor. 
    Return (Rw-1). 
:

Attack will allow the one who knows bits 0. (b-1) to find bit b. To receive to an exhibitor entirely, it is necessary to begin with b equal 0 and to repeat attack until all an exhibitor is not becomes known.

Since the first b the bit is known, attacking can calculate the first b iterations of a cycle and find value s_b. The following iteration will demand the first unknown bit. If this bit is established in 1 it will be calculated R_b = (s_bЋy) mod n. If the bit is equal to zero, multiplication will be passed.

Let's consider at first attack in a following hypothetical case. Let the attacked system uses very fast function of modular multiplication but which sometimes consumes much bigger time, than all function of modular exponentiation. Then for some values s_b and y calculations R_b = (s_bЋy) mod n will be extremely slow, and, using knowledge of realisation of the attacked system, attacking can define, what these values. If time of calculation of all function of modular exponentiation is not enough, but thus R_b = (s_b* y) mod n should be calculated slowly the bit b, obviously, is equal 0. On the contrary, if long calculations on time R_b = (s_bЋy) mod n always lead to slow modular exponentiation, it is bit, possibly, is established in 1. As soon as the bit b becomes known, attacking can check up that a total time of operations slowly every time when s_b+1 = R²_b mod n it is expected to be slow. The same assumptions can be used and further to find following bits.

If the bit b is guessed incorrectly, the values calculated for R_{k> = b} also will be incorrect, and further the result will be, in general, casual. Time demanded for multiplication after an error will not be reflected on full exponentiation time. Attack thus has property "error detection"; after the wrong assumption of value of bit it will not be observed any significant correlation.

Property of "error detection" can be used for its correction. For example, attacking can support the list of the most probable intermediate an exhibitor along with the value, corresponding correct probability. Attack proceeds for the unique most probable candidate. If current value is wrong, it will tend to fall in the list of the most probable values whereas the correct should raise. Methods of correction of errors increase necessary memory and processor time, but thus considerably reduce number of necessary values.

Attack can be treated as a problem of recognition of signals. "Signal" consists of variations of measurement of time for known bats, "noise" - from errors of measurement of time and variations of measurement of time for unknown bats. Properties of "signal" and "noise" define quantity of gaugings of time demanded for attack. Let it is received j messages y₀, y₁., y_j-1 and to it corresponding measurements of time T₀, T₁., T_j-1. The probability that the assumption x_b for the first b bit correctly, is proportional, where

t (y_i, x_b) - time demanded for first b the iterations of a cycle вычсиления y_i^x mod n with use bit x_b,

F - expected фунция distributions of probability T-t (y, x_b) on all values y and correct x_b. Since F it is defined as distribution verojatnostiT_i-t (y_i, x_b) if x_b it is correct it it is the best function for prediction T_i-t (y_i, x_b). Pay attention that measurements of time and intermediate values s can be used for improvement of estimation F.

At the correct assumption for x_b-1 there are two possible values for x_b. The probability of that x_b - is correct, and x_b ' - wrong, can be found as

In practice this formula is not so useful, since search F will demand too big efforts.

Fortunately, there is no necessity to calculate F. Each supervision of time consists from where t_i - time demanded for multiplication and exponentiation for bit i, and e includes a measurement error, time on инкремент a cycle, etc. Having the assumption x_b, attacking can calculate for each value y¹. If x_b it is correct, subtracting this time from T, we will receive. Since times of modular multiplication do not depend from each other and on a measurement error, the dispersion on all observable values, is expected, will be equal Var (e) + (w-b) Var (t). However, if only the first c <b the bit is guessed correctly, the expected dispersion will be Var (e) + (w-b+2c) Var (t). Iterations with correct assumptions reduce an expected dispersion on Var (t), each iteration after the wrong assumption increases a dispersion on Var (t). To calculate dispersions it is easy, and it provides a good way of identification of correct bit.

Now probably to estimate number of the values demanded for attack. We will assume that the attacking has j exact times of measurement and two assumptions concerning the first b bits of the w-bit value, one correct and another - wrong with the first error in bit c. For each assumption measurement time can be verified with. If such verification has a smaller dispersion it is the correct assumption. Probably to approximate t_i with use of independent standard normal variables. If Var (e) it is insignificant, expected probability of correctness of the assumption

X and Y - normal casual variables with the law (0, 1). Since j rather big, also are approximately normal with the law (0,). From here, where Z - standard normal casual a variable. Integration for a finding of probability of the correct assumption gives, where - area under a standard normal curve from to x. The demanded number of values j thus is proportional to length exhibitors w. The number of measurements can be reduced, if the attacking can choose such entrance data to have time extrema in those bits exhibitors which it interest.

On fig. 1 distribution of performance of modular multiplication of 10⁶ times is shown. Package RSAREF [10] on 120-MHz computer Pentium from OS MS-DOS was for this purpose used. Distribution has been constructed, measuring time of one million calculations (aЋb mod n) where an and b turned out as result of actual operations of modular exponentiation with the casual entrance data. In quality n the first 512-bit simple number from the demonstration program of a method of Diffi-Hellmana of package RSAREF was used. All most deviated values of measurements (which have occupied more than 1300 мкс) have been rejected. Distribution to fig. 1 has a floor-mat. Expectation Њ = 1167.8 мкс and a standard deviation = 12.01 мкс. The measurement error is small; tests were spent twice and the average difference between measurements has made less than 1 мкс. RSAREF uses the same function for squaring and multiplication; thus squaring and multiplication times have identical distributions.

RSAREF calculates in advance y² mod n and y³ mod n and processes at once two bits. Everything, 512-bit modular exponentiation with a casual exponent from 256 bats demands 128 iterations of a cycle of modular multiplication and total of actions of modular multiplication and squaring approximately 352 since each iteration carries out two actions of squaring and, if any of two bats not 0, one multiplication. Attack can be corrected for this case to add pair of bats and to estimate four values of the candidate in each position exhibitors instead of two.

As modular multiplication consume the greatest quantity of general time, it is expected that time distribution will be approximately normal with the law (Њ,), where Њ> = 1167.8Ћ352 = 411065.6 мкс and = 225 мкс. Drawing 2 shows measurements from 5000 actual actions using the same computer and the module n where distribution with Њ = 419,901 мкс and = 235 мкс has turned out.

At 250 measurements of time probability of that subtraction of time of correct iteration from each value will reduce the general dispersion to the big size, than subtraction of wrong iteration, is estimated by the formula, where j=250, b=1, c=0 and w=127. (There are 128 iterations of a cycle in RSAREF for exhibitors in 256 bits, but the first iteration is ignored). Correct assumptions thus are expected with probability. 5000 values from drawing 2 have been divided into 20 groups on 250 in everyone, and the dispersions received at subtraction of time for wrong and correct iterations of a cycle, for each of 127 pairs bats were compared. From 2450 tests, in 2168 dispersion after subtraction of time of a wrong cycle was more than after subtraction of time correct, having made probability 0.885. The first bits are most difficult for the analysis, but in process of increase b the probability should improve. (Tests did not use this property). It is important to notice that exact measurements of time were used; errors of measurements with rather big deviation in comparison with time of calculation of modular exponentiation, will increase the size of sample.

Attack in the computing relation is rather simple. At use RSAREF, attacking should estimate four variants for each pair of bats. Thus, attacking should make only four times большее number of the actions which are carried out by a victim (not including time spent for nothing on wrong assumptions).

The majority of variations of time in modular multiplication usually causes reduction of modular operations. Multiplication of Montgomery [6] eliminates necessity of reduction mod n and, as a result, tends to reduce the importance of time characteristics. However, some variations nevertheless remain. If remained "signal" is not eclipsed by measurement errors, a dispersion in t_b both a dispersion would be reduced proportionally and attack still would work. However, if a measurement error e big the demanded number of values will increase proportionally.

The Chinese theorem of the rests (WHO) also is often used to optimise operations in RSA. At its use at first are calculated y mod p and y mod q, where y - the message. These initiatory steps can be vulnerable for time attacks. Elementary of them consists that it is necessary to choose values y which are close to p or q, and, using time measurements, to find out, whether prospective value less, than actual value p (or q) is. If y - it is less, than p calculation y mod p is not necessary, while if y more than p for calculation y mod p subtraction p at least once is necessary. Also, if the message slightly more than p, y mod p has the first zero bits that can reduce time demanded for the first step multiplication. Features of time characteristics depend on realisation. Modular function of reduction RSAREF with the 512-bit module on computer Pentium with y, chosen casually between 0 and 2p, occupies on the average 42.1 мкс, if y <p, and 73.9 мкс, if y> p. Time of measurement for many y can be used for successive approximation p.

In certain cases probably to improve attack on RSA with WHO, if to use the known (not chosen) text in code, reducing number of demanded messages and doing possible attacks to digital signatures RSA. Reduction of modular operations is carried out by subtraction of several modules at once, and variations of time which can be used, arise at the expense of different quantity of steps of "comparison-subtraction". For example, the cycle of division RSAREF carries out integer division of the senior two figures y on the senior figure p, multiplies p on private, shifts to the left on corresponding number of figures, and then subtracts result from y. If result more than p (shifted to the left) additional subtraction is carried out. The decision, whether to do additional subtraction in the first cycle of algorithm of division, usually depends only from y (which it is known) and the senior two figures p. The time analysis can be used for definition of the senior figures p. For example, full search on all possible values for the senior two figures p (or more effective methods) can establish value for which observable time correlates most close with expected quantity of actions of subtraction. As well as in case of attack for a method of Diffi-Hellmana as soon as one figure p will be found, time measurements can repeatedly be used to find the subsequent figures.

It is yet known, whether the time analysis can be adapted directly to attack exponentiation on the module p and q, carried out with the help WHO.

The standard of the digital signature (Digital Signature Standart, DSS) calculates s = (k^-1 (H (m) +x Ћ r)) mod q where r and q are known attacking, k^-1 is usually calculated in advance, H (m) - хэш messages, and x - a confidential key. In practice at first it is calculated (H (m) + x Ћ r) mod q, and then it is multiplied on k^-1 (mod q).

If function of modular reduction is not carried out during fixed time, time of the full signature should correlate in due course calculations (x Ћ r mod q). Attacking can calculate and compensate time demanded for calculation H (m). As H (m) has the approximately same size, as q, its addition makes insignificant impact on time of modular reduction. The most significant bits x Ћ r are usually used by the first in modular reduction. They depend from r which is known, and from the most significant bats of confidential value x. Thus, there should be a correlation between values of the senior bits x and the general time of modular reduction. Using the greatest probabilities on the values, attacking can try to identify the senior bits x. The more bit x it becomes known, the it is more and the bit x Ћ r becomes known, allowing attacking to model more and more iterations of a cycle of modular reduction, attacking all new bits x. If k^-1 - it is calculated in advance, signatures DSS demand only 2 operations of the modular multiplication, potentially making time noise which should be filtered.

The most obvious way of prevention of attacks by the time analysis consists in that all actions occupied precisely same временя. Unfortunately, it often happens difficultly. Creation of the software which is especially platformo-independent so that it was carried out during fixed time, is rather difficult, because optimisation of the compiler, hits can bring unexpected fluctuations in a program cache, time of performance of instructions and other factors during execution. If for a delay of returned results till certain time the timer type factors of "the system response" (responsiveness) or power consumption can still serve as signs of the actual termination of operation is used. Also some operating systems show percent of use ЦПУ process. Moreover, realisations with fixed time will be slow; The majority оптимизаций cannot be used, as all actions should occupy time, executions of the slowest operation. (The note: if unessential step R_i = (s_i Ћ y) mod n to carry out always it is impossible to name such realisation carried out in fixed time since attacking can use time characteristics of squaring and the subsequent actions of a cycle).

Other approach consists in making time measurements so inexact that attack became impracticable. The casual delays added to process, will increase necessary quantity of a text in code for attacking, but it can overcome it increase in number of measurements. The demanded number of values is roughly estimated as a noise square. For example, if the modular exponentiation which time characteristics have a standard deviation 10 мс, can be cracked for 1000 measurements of time, addition of the casual normally distributed delay with a standard deviation in 1 second will demand approximately = 10⁷ values. (The note: the delay should be some seconds that its standard deviation would be in 1 second). Though 10⁷ values - more than the safety factor in 10⁷ usually are not considered the greatest possible quantity of values which can be collected, adequate enough.

Fortunately, there is also the best decision. The methods used for concealment of signatures [1], can be adapted to prevent knowledge attacking the entrance data to modular function of exponentiation. Before calculation modular exhibitors, choose casual pair (v_i, v_f), such that v_f^-1 = v_i^x mod n. For a method of Diffi-Hellmana most simply to choose casual v_i, then to calculate v_f = (v_i^-1) ^x mod n. For RSA it is better to choose casual v_f, mutually simple to n, then to calculate v_i = (v_f^-1) ^e mod n, where e - opened an exhibitor. Before modular exponentiation, the entrance data should be increased on v_i (mod n), and later the result is corrected by multiplication on v_f (mod n). Thus the system should reject the messages equal 0 (mod n).

Calculation of inversions mod n slowly, therefore is not practical to choose new casual (v_i, v_f) pair for everyone new exhibitors. Moreover, calculation v_f = (v_i^-1) ^x mod n can be subjected the time analysis. However (v_i, v_f) steams should not be to be used repeatedly as they can be opened the time analysis that does confidential to an exhibitor vulnerable. The effective decision of this problem - modernisation v_i and v_f before each step of modular exponentiation, calculating v_i ' = v_i² and v_f ' = v_f². The general expenses for it will be small (2 modular squarings which can be calculated in advance, plus of 2 modular multiplication). Probably to use and more difficult modernisation of pair, using usages above 2, multiplication to other pair (v_i, v_f), etc., but it will not introduce new advantages.

If (v_i, v_f) it is stored in a secret the attacking has no helpful information concerning the entrance data for function of modular erection about degree. Hence, the maximum of that can learn the attacking, is general distribution of time for exponentiation actions. Practically, these distributions are close to normal and 2^{w an} exhibitor it is impossible to distinguish. However, function of modular exponentiation specially developed by the malefactor could have theoretically distribution with sharp the peaks corresponding to bits exhibitors, and in this case concealment, possibly, will not prevent the time analysis.

Even using concealment, distribution will reflect average time of operation that it is possible to use to find хаммингский weight exhibitors. If anonymity or if the further masking an exhibitor can be increased on casual before each modular exponentiation is required is important. If it becomes, it is necessary to be convinced that process of multiplication has no time characteristics which can open. Such technics can be useful and in prevention of attacks which use information leakage during modular exponentiation because of electromagnetic radiations, fluctuations in productivity of system, changes in energy consumption etc. up to change of bats exhibitors in each operation.

The time analysis can be used basically against others криптосистем, including the symmetric. For example, in program realisation DES [4] 28-bit values With and D often rotate (rotate), using a condition which checks, whether one bit around should be wrapped up. An Extra time demanded to move bits distinct from zero, can affect slightly productivity of enciphering or on preparation time (setup) keys. Productivity of the code number thus can show хаммингский key weight that on the average will give bit of the key information. IDEA [3] uses function $f () $ with multiplication on the module (2¹⁶ + 1) which will usually not be carried out during fixed time. RC5 [7] will be under the threat on platforms where bit rotation is carried out during variable time. Hits in a program cache can give to the malefactor time characteristics Blowfish [11], SEAL [9], DES and others of code numbers if tables in memory are not used equally for everyone зашифровки. Whether additional researches are necessary to define concrete realisations are are vulnerable and, if it so, degree of their vulnerability. For today certain systems have been in detail studied only a few, and attacks against multiplication Montgomeri/who in realisations RSA and DSS meanwhile are purely theoretical. Also the further additions to attacks can be possible. Direct attack on p and q in RSA with use WHO would be especially important.

In general, any channel which can bear the information from the protected area outside should be studied as potentially vulnerable. Time characteristics depending on realisation are one of such channels and can sometimes be used for disclosing of confidential keys. Vulnerable algorithms, reports and systems should be reconsidered to include counteraction measures to the time analysis and the attacks connected with it.

I am grateful Matt Blaze, Joan Feigenbaum, Martin Hellman, Phil Karn, Ron Rivest and Bruce Schneier for their support, useful comments and offers on manuscript improvement.

1. D. Chaum, "Blind Signatures for Untraceable Payments," Advances in Cryptology: Proceedings of Crypto 82, Plenum Press, 1983, pp. 199-203.
2. W. Diffie and M.E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory, IT 22, n. 6, Nov 1976, pp. 644-654.:
3. X. Lai, On the Design and Security of Block Ciphers, ETH Series in Information Processing V. 1, Konstanz: Hartung-Gorre Verlag, 1992.:
4. National Bureau of Standards, "Data Encryption Standard," Federal Information Processing Standards Publication 46, January 1977.:
5. National Institute of Standards and Technology, "Digital Signature Standard," Federal Information Processing Standards Publication 186, May 1994.:
6. P.L. Montgomery, "Modular Multiplication without Trial Division," Mathematics of Computation V. 44, n. 170, 1985, pp. 519-521.:
7. R.L. Rivest, "The RC5 Encryption Algorithm," Fast Software Encryption: Second International Workshop, Leuven, Belgium, December 1994, Proceedings, Springer-Verlag, 1994, pp. 86-96.:
8. R.L. Rivest, A. Shamir, and L.M. Adleman, "A method for obtaining digital signatures and public-key cryptosystems," Communications of the ACM, 21, 1978, pp. 120-126.:
9. P.R. Rogaway and D. Coppersmith, "A Software-Optimized Encryption Algorithm," Fast Software Encryption: Cambridge Security Workshop, Cambridge, U.K., December 1993, Proceedings, Springer-Verlag, 1993, pp. 56-63.:
10. RSA Laboratories, "RSAREF: A Cryptographic Toolkit," Version 2.0, 1994, available via FTP from rsa.com.:
11. B. Schneier, "Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish)," Fast Software Encryption: Second International Workshop, Leuven, Belgium, December 1994, Proceedings, Springer-Verlag, 1994, pp. 191-204.

:

¹. In article anywhere it is not told about the requirements shown to productivity of the computer attacking. From this phrase it is possible to draw a conclusion that it should be same, as at the attacked computer. - a lane comment