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