Timing attack

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. The attack exploits the fact that every operation in a computer takes time to execute.

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 generally 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 implementation of an algorithm rather than the algorithm itself. The same algorithm can always be reimplemented in a way that leaks little or no information to a timing attack: 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 the routine. In such an implementation, timing gives an attacker no useful information; it also has the adverse effect of slower response times on average.

The practicality of the attack implies several things:

• It is algorithm-independent. Notice that the theoretical security of such algorithms remains — it is mainly the need for a high-speed implementation of a particular algorithm, that introduces such vulnerabilities.
• Finding timing information is more routine. While finding cryptographic errors in a crypto-primitive such as the DES may require deeper knowledge of mathematics, timing is relatively easy. And measuring response time for a specific query might give away relatively large amounts of information.

A detailed example

A timing attack exists for versions of OpenSSL prior to 0.9.6c. The attack was based on the following idea: in the SSL protocol, a message authentication code (MAC) lies at the end of a message before encryption. If the message is to be encrypted with a block cipher in cipher block chaining (CBC) mode, then padding must be added to the end of all messages after the MAC. This padding is special, in that it is stereotyped: if 2 bytes are added then "1,1", if three then "2,2,2", etc. The entire message, including the MAC and the padding, is then encrypted and sent. The receiver decrypts the message, checks that the padding is correct (i.e. it is 0 or 1,1 or 2,2,2 etc.), and if correct, computes the MAC checking it against the transmitted MAC. If the padding is incorrect, the protocol immediately exits with an error, without computing the (almost certainly incorrect) MAC.

The vulnerability lies in the padding: if the message can be intercepted, the attacker tries to guess the padding, rewrites part of the message, and then sends the message to the intended receiver. If the padding is incorrect the MAC will not be computed at all. Because computing the MAC is a relatively time-consuming operation, it is possible to measure the time it takes to respond and know whether the MAC was computed and whether we guessed the padding correctly.

For this timing attack to work, cipher block chaining (CBC) must be used. This mode has the property that if a ciphertext bit is toggled before decryption, the plaintext of the block it appears in is completely corrupted, but the corresponding bit in the following plaintext block is correspondingly toggled. In this way we can blindly change the next block's bits. However, as we will see, this blindness is removed by the timing information, and we can gain 1 bit of information with every accurate measurement.

Guessing the padding value is relatively simple, so let's say that the end of the message is at the moment ciphertext bytes $x_{1},x_{2},x_{3}...x_{7},x_{8}$ and we know that the pad is one byte long, i.e. decrypt($x_{8}$)= 0. The previous block's ciphertext bytes are similarly $y_{1},y_{2},..y_{8}$. Cracking $x_{7}$ is not hard at all. Just increase decrypt($x_{8}$) from 0 to 1, which is done by $y_{8}=y_{8}$ xor 0 xor 1, then send the message. If the other party computes a MAC on the message, we know the original padding guess was correct, and more importantly, we know that decrypt($x_{7}$)=1 since the end of the decrypted message has the correct padding string. If the other party does not compute the MAC, we know that decrypt($x_{7}$) is not 1, so we can try a different guess for the plaintext of $y(7)$. For example, let's do $y_{7}=y_{7}$ xor 28. If the other party computes the MAC, we know that decrypt($x_{7}$)=1 xor 28. If it does not accept it, continue to try with different xor values.

Using this we can work backward through the trailing bytes of a message that is the same and is sent regularly, such as a password. And the attack can be extended. Consider the secure IMAP protocol. The session is typically initiated several times a day, and the user would typically not suspect anything is amiss if we interrupt one of its connections and guessed at one byte of his password, say, twice a day. The only clue the user might see will be an obscure error message (ie, the MAC will not be OK, the SSL session will need to be restarted, which gives an error message in the email client such as Outlook or Thunderbird). Since the allowed alphabet for passwords on most systems is not more than 40 characters, 20 guesses will, on average, give us one letter of the password. If the password is 10 letters long this is 200 guesses. In 3 months the user's password would be known. In other applications, in which SSL connections are made by machines and on a regular basis, this time may be reduced to minutes, as repeated errors will not come to the notice of a person until system log files are analyzed. Since this is often not done, the burst of errors generated is likely to go unnoticed.

Other examples

The execution time for the square-and-multiply algorithm used in modular exponentiation 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 improper 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 faults 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/cacheing 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. (See Percival, Colin, Cache Missing for Fun and Profit, 2005; Bernstein, Daniel J., Cache-timing attacks on AES, 2005.)

Notes

Timing attacks are easier to mount if the adversary knows the internals of the hardware implementation, and even more so, the crypto system in use. Since cryptographic security should never depend on the obscurity of either (see security through obscurity, specifically both Shannon's Maxim and Kerchoff's Law), resistance to timing attacks should not either. If nothing else, an exemplar can be purchased and reverse engineered. Timing attacks and other side-channel attacks may also be useful in identifying, or possibly reverse-engineering, a cryptographic algorithm used by some device.

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)

External links

• Introduction to Side Channel Attacks (pdf file)