# 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