Timing attack
|
|
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, particularly in asymmetric key algorithms, 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 good deal of noise (such as due to network latency), and error correction techniques are used to increase the throughput. This enables theoretical attacks on a number of encryption algorithms, including RSA, ElGamal, and the Digital Signature Algorithm.
In 2003, Boneh and Brumley demonstrated a practical network-based timing attack on SSL-enabled web servers, based on a different vulnerability having to do with the use of RSA with Chinese Remainder Theorem optimizations. Though the actual network distance was small in their experiments, the attack successfully recovered a server private key in a matter of hours. This demonstration led to the widespread deployment and use of blinding techniques in SSL implementations. Blinding can remove the correlation between key and encryption time.
Most timing attacks require that the adversary know the internals of the implementation. However, timing attacks and other side-channel attacks may also be useful in identifying, or possibly reverse-engineering, a cryptographic algorithm used by some device.
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))
- David Brumley and Dan Boneh: Remote timing attacks are practical. USENIX Security Symposium, August 2003. pdf file (http://www-2.cs.cmu.edu/~dbrumley/pubs/openssltiming.pdf)
- Colin Percival: Cache Missing for Fun and Profit, May 13, 2005 (pdf file (http://www.daemonology.net/papers/htt.pdf))
External link
- Introduction to Side Channel Attacks (http://www.hbarel.com/publications/Introduction_To_Side_Channel_Attacks.pdf) (pdf file)