 # Timing Attack

Created: 2022-04-23
Updated: 2022-04-23

## Variance Recap

The variance of an aleatory variable `X` is a statistical measure of the spread (or dispersion) of a set of values of a random variable. It is defined as the squared deviations of the values from the mean `μ`. In other words, it measures how far the values of a random variable are spread out from its average or expected value.

``````Var[X] := E[(X - μ)^2] = ∑(xi - μ)^2 * Pr(X = x_i)
``````

The formula can be further expanded as:

``````Var[X] := E[(X - E[X])^2]
= E[X^2 - 2·X·E[X] + E[X]^2]
= E[X^2] - 2·E[X]·E[X] + E[X]^2
= E[X^2] - E[X]^2
``````

If `X` and `Y` are independent variables:

``````Var[X + Y] = Var[X] + Var[Y]
Var[X - Y] = Var[X] + Var[-Y] = Var[X] + Var[Y]
``````

Because `Var[Y] = Var[-Y]`.

## Fast Exponentiation Algorithm Recap

Algorithm for fast exponentiation `m^e`

``````k = bitlen(e)
A = 1
for i in k-1..0:
A = A^2 mod n
if is_bit_set(e, i):
A = m·A mod n
return A
``````

The total time is given by the sum of the times of each of the `k` iterations.

## Preamble

Fixed the exponent `k`, is not true that each iteration takes the same time, it also depends on the current value of `A`, and thus depends on the base `m`.

``````T = T(k-1) + T(k-2) + ... + T(0)
``````

`T` behaves like an aleatory variable.

The attacker choose many messages `mi` and to observe the relative execution times, that are independent extractions of `T`.

Also, the partial times `T(i)` are aleatory variables that follow an unknown probability distribution.

We can check the values by feeding random `mi` values and observing the results.

``````T_mi(j)
``````

The attacker determines the exponent bits one after the other, staring from the first.

The attack is based on the observation of the variance of `T`.

## Attack

The secret exponent `d` is a vector of `k` bits.

Assume that we already determined the bits from `k-1` down to `i+1`. The current target is the `i-th` bit.

An assumption is that the attacker has a local device that can emulate the device under attack and that he can stop its execution while processing a chosen bit.

Since the attacker knows the bits from `k-1` to `i+1`, he can correctly emulate the device under attack until the exponentiation iteration `k-(i+1)` (included).

Tries with both `d[i] = 0` and `d[i] = 1`.

The attacker ends up with two execution times:

• `T` from the real device with a full correct key `d`.
• `T'` from the emulator. This is partial as it only includes the execution time of the already disclosed bits plus the new bit we’re trying to reveal.
``````    T - T' = T(k-1) + ... + T(i+1) + T(i) + ... + T(0)
- T(k-1) - ... - T(i+1) - T'(i) =
= T(i) + ... + T(0) - T'(i) =
= T(i) - T'(i) + T(i-1) + ... + T(0)
``````

This is the difference of two aleatory variables, we compute the variance of the difference of the times:

``````Var[T - T']
``````

We assume that the times relative to the single iterations are independent between each other (i.e. `T(i)` and `T(j)` are independent for `i ≠ j`).

``````Var[T(i)] = Var[T'(i)] = v
``````

If the value of `d[i]` that has been tried by the attacker is correct then the emulations of the attacker are correct down to the `i`-th iteration.

And thus we have that :

``````T - T' = T(i-1) + ... + T(0)
``````

And thus:

``````Var[T - T'] = Var[T(i-i)] + ... + Var[T(0)]
``````

If instead the bit value has not been chosen correctly then the variance is:

``````Var[T - T'] = Var[T(i) - T'(i)] + Var[T(i-i)] + ... + Var[T(0)]
= Var[T(i)] + Var[T'(i)] + Var[T(i-i)] + ... + Var[T(0)]
``````

Thus, if we have chosen the wrong value for `d[i]` then we’re going to have a variance that is greater by a term `2·v`.

The attacker is thus going to take as the value for `d[i]` the one that in the end gives the smaller variance.

In short, the attacker:

• executes the algorithm with a bunch of `mi` (e.g. 1000);
• gets the timings for each `T_mi`
• computes the empirical variance using the samples

## Reference

• Rust and Python PoC here