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