Mercurial > dropbear
comparison notes/tech0002.txt @ 0:d7da3b1e1540 libtomcrypt
put back the 0.95 makefile which was inadvertently merged over
| author | Matt Johnston <matt@ucc.asn.au> |
|---|---|
| date | Mon, 31 May 2004 18:21:40 +0000 |
| parents | |
| children |
comparison
equal
deleted
inserted
replaced
| -1:000000000000 | 0:d7da3b1e1540 |
|---|---|
| 1 Tech Note 0002 | |
| 2 How to avoid non-intrusive timing attacks with online computations | |
| 3 Tom St Denis | |
| 4 | |
| 5 Introduction | |
| 6 ------------ | |
| 7 | |
| 8 A timing attack is when an attacker can observe a side channel of the device (in this case time). In this tech note | |
| 9 we consider only non-intrusive timing attacks with respect to online computations. That is an attacker can | |
| 10 determine when a computation (such as a public key encryption) begins and ends but cannot observe the device | |
| 11 directly. This is specifically important for applications which transmit data via a public network. | |
| 12 | |
| 13 Consider a Diffie-Hellman encryption which requires the sender to make up a public key "y = g^x mod p". Libtomcrypt | |
| 14 uses the MPI bignum library to perform the operation. The time it takes to compute y is controlled by the number | |
| 15 of 1 bits in the exponent 'x'. To a large extent there will be the same number of squaring operations. "1" bits in | |
| 16 the exponent require the sender to perform a multiplication. This means to a certain extent an attacker can | |
| 17 determine not only the magnitude of 'x' but the number of one bits. With this information the attacker cannot directly | |
| 18 learn the key used. However, good cryptography mandates the close scrutiny of any practical side channel. | |
| 19 | |
| 20 Similar logic applies to the other various routines. Fortunately for this case there is a simple solution. First, | |
| 21 determine the maximum time the particular operation can require. For instance, on an Athlon 1.53Ghz XP processor a | |
| 22 DH-768 encryption requires roughly 50 milliseconds. Take that time and round it up. Now place a delay after the call. | |
| 23 | |
| 24 For example, | |
| 25 | |
| 26 void demo(void) { | |
| 27 clock_t t1; | |
| 28 | |
| 29 // get initial clock | |
| 30 t1 = clock(); | |
| 31 | |
| 32 // some PK function | |
| 33 | |
| 34 // now delay | |
| 35 while (clock() < (t1 + 100)); | |
| 36 | |
| 37 // transmit data... | |
| 38 | |
| 39 } | |
| 40 | |
| 41 This code has the effect of taking at least 100 ms always. In effect someone analyzing the traffic will see that the | |
| 42 operations always take a fixed amount of time. Since no two platforms are the same this type of fix has not been | |
| 43 incorporated into libtomcrypt (nor is it desired for many platforms). This requires on the developers part to profile | |
| 44 the code to determine the delays required. | |
| 45 | |
| 46 Note that this "quick" fix has no effect against an intrusive attacker. For example, power consumption will drop | |
| 47 significantly in the loop after the operation. However, this type of fix is more important to secure the user of the | |
| 48 application/device. For example, a user placing an order online won't try to cheat themselves by cracking open their | |
| 49 device and performing side-channel cryptanalysis. An attacker over a network might try to use the timing information | |
| 50 against the user. | |
| 51 | |
| 52 |