| 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152 |
- Tech Note 0002
- How to avoid non-intrusive timing attacks with online computations
- Tom St Denis
- Introduction
- ------------
- A timing attack is when an attacker can observe a side channel of the device (in this case time). In this tech note
- we consider only non-intrusive timing attacks with respect to online computations. That is an attacker can
- determine when a computation (such as a public key encryption) begins and ends but cannot observe the device
- directly. This is specifically important for applications which transmit data via a public network.
- Consider a Diffie-Hellman encryption which requires the sender to make up a public key "y = g^x mod p". Libtomcrypt
- uses the MPI bignum library to perform the operation. The time it takes to compute y is controlled by the number
- of 1 bits in the exponent 'x'. To a large extent there will be the same number of squaring operations. "1" bits in
- the exponent require the sender to perform a multiplication. This means to a certain extent an attacker can
- determine not only the magnitude of 'x' but the number of one bits. With this information the attacker cannot directly
- learn the key used. However, good cryptography mandates the close scrutiny of any practical side channel.
- Similar logic applies to the other various routines. Fortunately for this case there is a simple solution. First,
- determine the maximum time the particular operation can require. For instance, on an Athlon 1.53Ghz XP processor a
- DH-768 encryption requires roughly 50 milliseconds. Take that time and round it up. Now place a delay after the call.
- For example,
- void demo(void) {
- clock_t t1;
- // get initial clock
- t1 = clock();
-
- // some PK function
-
- // now delay
- while (clock() < (t1 + 100));
-
- // transmit data...
-
- }
- This code has the effect of taking at least 100 ms always. In effect someone analyzing the traffic will see that the
- operations always take a fixed amount of time. Since no two platforms are the same this type of fix has not been
- incorporated into libtomcrypt (nor is it desired for many platforms). This requires on the developers part to profile
- the code to determine the delays required.
- Note that this "quick" fix has no effect against an intrusive attacker. For example, power consumption will drop
- significantly in the loop after the operation. However, this type of fix is more important to secure the user of the
- application/device. For example, a user placing an order online won't try to cheat themselves by cracking open their
- device and performing side-channel cryptanalysis. An attacker over a network might try to use the timing information
- against the user.
|
