Timing attacks

If you ask someone a question and they say yes" immediately, that gives you different information than if they pause and slowly say yes." The information you receive is not just the response but also the time it took to generate the response.

Encryption can be analogous. The time it takes to encrypt data can leak information about the data being encrypted. It probably won't reveal the data per se, but it may reveal enough about the data or the encryption process to reduce the effort needed to break the encryption.

There are two ways of thwarting timing attacks. One is to try to make the encryption take the same amount of time, independent of the data. This would prevent an attacker from inferring, for example, which branch of an algorithm was taken if one branch executes faster than the other.

If the encryption process always takes the same amount of time, then the execution time of the encryption process carries no information. But its enough that the execution time carries no useful information.

It may be easier to make execution time uncorrelated with content than to make execution time constant. Also, keeping the execution time of an algorithm constant may require making the program always run as slow as the worst case scenario. You may get faster average execution time by allowing the time to vary in a way that is uncorrelated with any information useful to an attacker.

One example of this would be Garner's algorithm used in decrypting RSA encoded messages.

Suppose you're using RSA encryption with a public key e, private key d, and modulus n. You can decrypt cyphertext c to obtain the cleaertext m by computing

m = c^d mod n.

An alternative would be to compute a random message r and decrypt r^ec:

(r^ec)^d = r^ed c^d =rm mod n

then multiply by the inverse of r mod n to obtain m. Because r is random, the time required to decrypt r^ec is uncorrelated with the time required to decrypt c.

The post Timing attacks first appeared on John D. Cook.