Timing attack - Definition and Overview

In cryptography, a timing attack is a form of side channel attack where the attacker tries to break a cryptosystem by analyzing the time taken to execute cryptographic algorithms.

The attack exploits the fact that in an asymmetric key algorithm, computation time for a private key operation is dependent on the key in some way. For instance, in the square-and-multiply algorithm for modular exponentiation, execution time depends linearly on the number of '1' bits in the key. While the number of '1' bits alone is not nearly enough information to make finding the key significantly easier, repeated executions with the same key and different inputs can be used to perform statistical correlation analysis of timing information to recover the key completely, even by a passive attacker. Observed timing information usually suffers from a lot of noise (such as due to network latency), and error correction techniques are used to increase the throughput.

The attack requires that the adversary know the internals of the implementation.

Techniques used in blinding can be used to remove the correlation between key and timing, preventing this attack.

Symmetric key algorithms are less susceptible to timing attacks because their timing characteristics are not as key-dependent as for asymmetric key algorithms.

References

• Paul C. Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. CRYPTO 1996: 104–113 (pdf file (http://www.cryptography.com/timingattack/paper.html))

External link

• Introduction to Side Channel Attacks (http://www.hbarel.com/publications/Introduction_To_Side_Channel_Attacks.pdf) (pdf file)