Timing attacks

The simplest of the side channels to understand is time. If the duration of a computation depends on the value of the secret, then timing that computation already means spying on the secret.

The idea: time speaks

A computer does not always take the same time to perform an operation. A loop that stops earlier, an if branch that skips a step, a memory access already present in the cache: all of this shortens or lengthens the execution. If these variations are correlated with the secret, the attacker exploits them.

The classic example: the naive comparison

Imagine a system that verifies a password (or a signature) by comparing byte by byte, and that stops at the first wrong byte:

comparer(saisie, secret):
    pour i de 0 à longueur - 1:
        si saisie[i] != secret[i]:
            retourner FAUX        <- sortie anticipée !
    retourner VRAI

The flaw: the more correct leading bytes the input has, the longer the function runs before returning FALSE. By measuring this time, the attacker guesses the bytes one by one:

secret = "K7z..."

essai "A???"  -> échec au 1er octet   (rapide)
essai "K???"  -> échec au 2e octet    (un peu plus long)  => 'K' est bon !
essai "K7??"  -> échec au 3e octet    (encore plus long)  => '7' est bon !

We no longer test 256^n combinations, but 256 × n: the secret falls byte by byte. An exponential attack becomes linear.

The same flaw in RSA

The modular exponentiation m = c^d mod n of RSA decryption walks through the bits of the secret exponent d. A naive implementation performs an extra multiplication only when the bit is 1:

bit = 1  ->  élévation au carré + multiplication   (lent)
bit = 0  ->  élévation au carré seulement           (rapide)

The total time then reveals the number — or even the position — of the 1-bits of the private key. Real attacks have recovered TLS keys this way.

The countermeasure: constant time

The countermeasure has a precise name: constant-time code (constant-time). Its rule is strict:

The execution time must depend neither on branches nor on memory accesses that depend on the secret.

Concretely, a constant-time comparison examines all the bytes, without ever stopping along the way:

comparer_ct(saisie, secret):
    diff = 0
    pour i de 0 à longueur - 1:
        diff = diff | (saisie[i] XOR secret[i])   # accumule, ne sort jamais
    retourner (diff == 0)

The result is identical, but the duration is the same whatever the secret: the stopwatch no longer learns anything. Serious libraries provide dedicated functions (for example so-called constant-time comparisons) precisely for this.

In summary

If the computation time depends on the secret — comparison with early exit, branching exponentiation — the stopwatch reveals the secret bit by bit, turning an exponential search into a linear one. The countermeasure is constant-time code: no branch or memory access dependent on the secret, an always identical duration.