Timing attack
Encyclopedia
In cryptography
, a timing attack is a side channel attack
in which the attacker attempts to compromise a cryptosystem
by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, and the time can differ based on the input; with precise measurements of the time for each operation, an attacker can work backwards to the input.
Information can leak from a system through measurement of the time it takes to respond to certain queries. How much such information can help an attacker depends on many variables: crypto system design, the CPU running the system, the algorithms used, assorted implementation details, timing attack countermeasures, the accuracy of the timing measurements, etc.
Timing attacks are often overlooked in the design phase because they are so dependent on the implementation.
of an algorithm
rather than the mathematical properties of the algorithm itself.
Many cryptographic algorithms can be implemented (or masked by a proxy) in a way that reduces or eliminates data dependent timing information: consider an implementation in which every call to a subroutine always returns in exactly x seconds, where x is the maximum time it ever takes to execute that routine on every possible authorised input. In such an implementation, the timing of the algorithm leaks no information about the data supplied to that invocation. The down side of this approach is that the time to execute many invocations increases from the average performance of the function to the worst case performance of the function.
Timing attacks are practical in many cases:
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 trivially easy, 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 measurements often include noise (from such sources as network latency, or disk drive access differences from access to access, and the error correction techniques used to recover from transmission errors). Nevertheless, timing attacks are practical against 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. The actual network distance was small in their experiments, but 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. In this context, blinding is intended to remove correlations between key and encryption time.
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 deliberately and measurably long time: as much as two or three seconds in some cases. 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 proper login name.
Two otherwise securely isolated processes running on a single system with either cache memory or virtual memory
can communicate by deliberately causing page fault
s and/or cache misses in one process, then monitoring the resulting changes in access times from the other. Likewise, if an application is trusted, but its paging/caching is affected by branching logic, it may be possible for a second application to determine the values of the data compared to the branch condition by monitoring access time changes; in extreme examples, this can allow recovery of cryptographic key bits.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a timing attack is a side channel attack
Side channel attack
In cryptography, a side channel attack is any attack based on information gained from the physical implementation of a cryptosystem, rather than brute force or theoretical weaknesses in the algorithms...
in which the attacker attempts to compromise a cryptosystem
Cryptosystem
There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...
by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, and the time can differ based on the input; with precise measurements of the time for each operation, an attacker can work backwards to the input.
Information can leak from a system through measurement of the time it takes to respond to certain queries. How much such information can help an attacker depends on many variables: crypto system design, the CPU running the system, the algorithms used, assorted implementation details, timing attack countermeasures, the accuracy of the timing measurements, etc.
Timing attacks are often overlooked in the design phase because they are so dependent on the implementation.
The idea behind the attack
A timing attack is an example of an attack that exploits the data-dependent behavioral characteristics of the implementationImplementation
Implementation is the realization of an application, or execution of a plan, idea, model, design, specification, standard, algorithm, or policy.-Computer Science:...
of an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
rather than the mathematical properties of the algorithm itself.
Many cryptographic algorithms can be implemented (or masked by a proxy) in a way that reduces or eliminates data dependent timing information: consider an implementation in which every call to a subroutine always returns in exactly x seconds, where x is the maximum time it ever takes to execute that routine on every possible authorised input. In such an implementation, the timing of the algorithm leaks no information about the data supplied to that invocation. The down side of this approach is that the time to execute many invocations increases from the average performance of the function to the worst case performance of the function.
Timing attacks are practical in many cases:
- Timing attacks can be applied to any algorithm that has data-dependent timing variation. Software run on a CPU with a data cache will exhibit data-dependent timing variations as a result of memory looks into the cache. Some operations, such as multiplication may have varied execution time depending on the inputs. Removing timing-dependencies is difficult in some algorithms that use low-level operations that frequently exhibit varied execution time.
- Finding secrets through timing information may be significantly easier than using cryptanalysis of known plaintext, ciphertext pairs. Sometimes timing information is combined with cryptanalysis to improve the rate of information leakage.
Examples
The execution time for the square-and-multiply algorithm used in modular exponentiationModular exponentiation
Modular exponentiation is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography....
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 trivially easy, 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 measurements often include noise (from such sources as network latency, or disk drive access differences from access to access, and the error correction techniques used to recover from transmission errors). Nevertheless, timing attacks are practical against a number of encryption algorithms, including RSA, ElGamal
ElGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...
, and the Digital Signature Algorithm
Digital Signature Algorithm
The Digital Signature Algorithm is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology in August 1991 for use in their Digital Signature Standard , specified in FIPS 186, adopted in 1993. A minor...
.
In 2003, Boneh
Dan Boneh
Dan Boneh is a Professor of Computer Science and Electrical Engineering atStanford University. He is a well-known researcher in the areas of applied cryptographyand computer security.-Education:...
and Brumley
David Brumley
David Brumley is an Assistant Professor at Carnegie Mellon University. He is a well-known researcher in software security, network security, and applied cryptography. Prof...
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
Chinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
optimizations. The actual network distance was small in their experiments, but the attack successfully recovered a server private key in a matter of hours. This demonstration led to the widespread deployment and use of blinding
Blinding (cryptography)
In cryptography, blinding is a technique by which an agent can provide a service to a client in an encoded form without knowing either the real input or the real output. Blinding techniques also have applications to preventing side-channel attacks on encryption devices.More precisely, Alice has...
techniques in SSL implementations. In this context, blinding is intended to remove correlations between key and encryption time.
Some versions of Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
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 deliberately and measurably long time: as much as two or three seconds in some cases. 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 proper login name.
Two otherwise securely isolated processes running on a single system with either cache memory or virtual memory
Virtual memory
In computing, virtual memory is a memory management technique developed for multitasking kernels. This technique virtualizes a computer architecture's various forms of computer data storage , allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which...
can communicate by deliberately causing page fault
Page fault
A page fault is a trap to the software raised by the hardware when a program accesses a page that is mapped in the virtual address space, but not loaded in physical memory. In the typical case the operating system tries to handle the page fault by making the required page accessible at a location...
s and/or cache misses in one process, then monitoring the resulting changes in access times from the other. Likewise, if an application is trusted, but its paging/caching is affected by branching logic, it may be possible for a second application to determine the values of the data compared to the branch condition by monitoring access time changes; in extreme examples, this can allow recovery of cryptographic key bits.