Re: Successful remote AES key extraction

From: Louis Scheffer (lou_at_cadence.com)
Date: 04/17/05 

Date: 16 Apr 2005 23:52:04 -0800

"D. J. Bernstein" <djb@cr.yp.to> writes:

>Tom St Denis wrote:

>> Couldn't you just insert noise in the process to lower the bias?

>Adding noise doesn't lower the bias. The attacker sees through the noise
>by averaging over a larger number of packets. See page 5. See also [7].

>The number of packets needed is proportional to the timing variance (the
>square of the timing deviation). I was already dealing with a variance
>over a thousand squared cycles; your specific look-up-a-few-entries
>tweak wouldn't have noticeably affected the variance. Hiding behind a
>cable modem is a much better way to add variance, although the attack is
>still doable with enough effort.

This is not clear to me, in practice. A session of ping -s shows at least
1 ms rms deviation on all servers I tried. According to the chart in your
paper, you are looking at 10 cycle deviations, or about 10^{-8} sec. So
making this work over typical inter-institution networks would require
roughly 10^10 trials. This is months at 1000 packets/second, even
assuming you can arrange for 10 billion known plaintexts.

On a more theoretical note, beating down the noise by factors of 1000s is
not always possible. To do so requires the noise to have some nice
statistical properties, which are not guaranteed in real life. (For
example, router delays are definitely not stationary - they vary with the
time of day, and the day of week, among other factors.) So the
routers between you and the target may introduce timing variances that
cannot be averaged out. Routers have CPUs and caches, use table lookup,
are subject to delays due to other traffic, and so on. I'd guess the
data dependency (and delays from other traffic, etc) is much worse for
routers than crypto algorithms. This may well get worse as routers do
more "deep inspection" for viruses, worms, etc.

Exploiting this in practice, against an opponent at least one hop distant
through the public internet, would seem very difficult. It would be an
good experiment to try, though.

If you do need to fix this at the CPU level, there are many possibilities.
For example, memory is cheap, so you could perhaps provide a "fast array"
which is few thousand bytes of dedicated memory, not shareed with anything
else, so all array accesses ARE constant time. (it would be saved and
restored, when needed, as a unit to avoid traffic conflcits).
This could also be useful DSP coefficients, FFT tables, and so on.

    Lou Scheffer

Relevant Pages

  • Re: standard deviation and N-1
    ... but in college the book has N-1 in the denominator. ... >deviations is always zero, the last deviation can be found once we know ... Suppose the distribution variance is v_d. ... n m_s is the sum of n ...
    (sci.math)
  • Re: Square Root in VBA
    ... Depending on what you are doing, it is possible to derive the standard ... deviation from the variance using a matrix and row construct with MMULT ... Function test1(RegionR, CovarMatrix) As Variant ...
    (microsoft.public.excel.programming)
  • Re: Basic Question: What Does Variance Measure.?
    ...    Just curious about variance: ... deviation. ...  the value of the St. Deviation, does the variance ... conservation of standard deviation. ...
    (sci.stat.math)
  • Re: Chebyshev Inequality for Sample Variance
    ... Population Variance is not known? ... theorem applied to Probability based in the sample variance. ... "Given any set of of numbers with Standard deviation s, ...
    (sci.stat.math)