Timing analysis attack and cryptosystem

Question

Why is a “Timing Analysis Attack” a problem for a cryptosystem?

I've been trying to learn security, and have a question about timing analysis attack.

Answer 1

Timing attacks are a type of side channel attacks. From a formal point of view, a cryptographic algorithm (let's say an encryption system) takes some input and provides some output, and the attacker sees the two values and tries to work out the key from these values. However, in a realistic system, the algorithm does not happen "magically": it has to run somewhere, on a computer or some other circuitry, and the attacker may try to observe from the outside this operation and deduce some extra information.

A timing analysis (or attack) is about measuring the time taken by the cryptographic algorithm to execute a given operation. Informally, the attacker tries to make "informed guesses" which look like "mmh... the algorithm took 174 nanoseconds to execute, but if that key bit was a 1, it should have taken at least 176 nanoseconds, so the key bit was a 0".

Defence against timing attacks include tweaking the algorithm implementation so that it always executes in a fixed amount of time regardless of the key value and input data; or "randomizing" it so that the attacker can no longer make such guesses. E.g. with the core exponentiation of RSA, instead of computing m^d mod n (n is the modulus, d is the private exponent), the implementation generates a random value r modulo n, then computes r^e mod n and 1/r mod n, and computes ((m*r^e)d) * (1/r) mod n. This is called masking. Since a new r is generated for each RSA computation, this process effectively prevents the timing-based guesses from the attacker.