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
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
Y are independent variables:
Var[X + Y] = Var[X] + Var[Y] Var[X - Y] = Var[X] + Var[-Y] = Var[X] + Var[Y]
Var[Y] = Var[-Y].
Fast Exponentiation Algorithm Recap
Algorithm for fast exponentiation
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
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
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
Also, the partial times
T(i) are aleatory variables that follow an unknown
We can check the values by feeding random
mi values and observing the results.
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
The secret exponent
d is a vector of
Assume that we already determined the bits from
k-1 down to
The current target is the
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
i+1, he can correctly emulate
the device under attack until the exponentiation iteration
Tries with both
d[i] = 0 and
d[i] = 1.
The attacker ends up with two execution times:
Tfrom the real device with a full correct key
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(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
And thus we have that :
T - T' = T(i-1) + ... + T(0)
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
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
- gets the timings for each
- computes the empirical variance using the samples
- Rust and Python PoC here