|
3
|
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
|
