Timing attack
From Free net encyclopedia
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.
Some versions of Unix use a relatively expensive implementation of the crypt library function for hashing an 8-character password into an 11-character string. On older hardware, this computation took a noticably long time: as much as two or three seconds. The login program in early versions of Unix executed the crypt function only when the login name was correct, which leaked information through timing that the login name itself was valid, even though the password was incorrect. Later versions of Unix fixed this leak by always executing the crypt function to avoid revealing the improper login name.
References
- Paul C. Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. CRYPTO 1996: 104–113 (pdf file)
- David Brumley and Dan Boneh: Remote timing attacks are practical. USENIX Security Symposium, August 2003. pdf file
- Colin Percival: Cache Missing for Fun and Profit, May 13, 2005 (pdf file)