Timing attack

From Wikipedia, the free 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. 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 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.

1 The idea behind the attack
2 A detailed example
3 Other examples
4 Notes
5 References
6 External links

[edit] The idea behind the attack

A timing attack is a practical attack: it attempts to exploit the implementation of the 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 can be used to attack anything, including perfect coding^{[verification needed]}. Notice that the theoretical security of such algorithms remains—the vulnerability, if any, is in the implementation.
It is often simple to find and exploit timing information. While finding cryptographic errors in a crypto-primitive such as the DES requires deep knowledge of mathematics, finding a data leak through timing is relatively easy. Exploiting them can be, in comparison, trivial: measuring response time for a specific query might give away relatively large amounts of information. In the example below, exactly 1 bit of information is leaked with every accurate measurement.

[edit] A detailed example

As an example, a timing attack exists for versions of OpenSSL prior to 0.9.6c.^[1] The attack was based on the following idea: the message authentication code that provides integrity for a message in this SSL protocol is at the end of the message. However, since messages must have a characteristic length (n*8 bytes), 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 bogus) MAC.

The error is, of course, in the last sentence: if we manipulate the message so as to guess the padding structure correctly, the MAC will not be computed at all. Measuring the time it takes to respond and having relatively accurate timing, we can 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. In this mode, if a block's bit is inverted, the following block, when deciphered, will contain that same bit inversion. 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: let's say that the end of the message is at the moment $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 blocks' bytes are similarly $y 1, y 2,.. y 8$ . Cracking $x 7$ is not hard at all. Just increase decrypt( $x 8$ ) from 1 to 2, which is done by $y 8 = y 8$ xor 0 xor 1, then send the message. If the other party accepts the message we know the padding guess was correct, we know that decrypt( $x 7$ )=1 since the end of the decrypted message has the correct padding value. If the other party does not accept it, we know that decrypt( $x 7$ ) is not 1, let's do $y 7 = y 7$ xor 28. If the other party accepts it, we know that decrypt( $x 7$ )=1 xor 28. If it does not accept it, then try to xor another number than 28, and so on.

Using this we can determine a part of a message that is the same and is sent regularly, i.e. 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 the correct key. If the password is 10 characters 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.

[edit] 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.)

[edit] 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.

[edit] References

^ http://www.openssl.org/news/secadv_20030219.txt

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)