Re: Random delay as a countermeasure to timing attacks



David Wagner wrote, in two bursts:
One possible hypothesis:
- the signal has a Gaussian distribution,
- the noise (the delay you add, plus any other random noise)
has a Gaussian distribution, and
- all of these contributions are independent.
Then it's easy to see that the S/N ratio goes up linearly
with the standard deviation of the noise, and goes down
proportional to the square root of the number of measurements,
leading to your desired result.

Oops, I think I meant that the signal is 0 or 1
(has a Bernoulli distribution). That's the simplest case,
because then you are just distinguishing between two
distributions: X and 1+X, where X ~ N(\mu,\sigma^2) for
some values of \mu,\sigma. You should be able to compute
the variation distance between these two distributions (as
a function of \sigma) using calculus, and I believe you'll
find that you need \sigma ~ 1 to have some non-negligible
chance of distinguishing. (If \sigma << 1, you're out of luck.)

I'm not quite sure that I follow you. My problem is that our adversary
is not bound to repeating the same experiment n times; she can make n
random queries, or queries chosen according to the cipher, or
iteratively-chosen queries, and from this find the hypothesis on key
bits that best match her data. I fear she may have an efficient
heuristic for this.

If I go in the direction of your Bernoulli distribution idea, what I am
hoping for is an upper bound on the total "knowledge" that may leak
about an unknown function T(j) with result either 0 or 1, if T(j)+X is
observed n times (at 1 to n points j chosen by the adversary), and X is
our random distribution of extra noise.

More precisely, we only need an X that make this "knowledge" less than
one (or suitably few) bits, with a mean X growing reasonably, hopefully
as o(s.n^1/2) for some known s as small as we can.

At least, it is easy to see that a uniform X does not work (extreme
outcomes of X are a giveaway), and that a triangular X (the sum of two
uniform), or a Gaussian, meat my objective *IF* the adversary allways
use the same j (or equivalently the function T is constant).

As an aside I fail to proove that Gaussian gives the lowest s, though I
tend to accept this.

It is OK if T(j) can only be 0 or 1, as "obviously" (meaning: I fail to
proove it) this is worse than for any function in range [0..1]. If we
could say something from the standard deviation of T(j) over the
observed points, that would be excellent.


François Grieu

.



Relevant Pages

  • Re: Frequency retrieval from noise
    ... distribution, one performs fourier transform to identify the ... noise, which means that the the spectrum of the noise is flat. ... I'm asking what are the peaks in the power spectrum of pure ... AWGN is gaussian in amplitude distribution, ...
    (sci.physics)
  • Re: Random numbers with Rice distribution
    ... The rice distribution is related to the normal distribution. ... Indeed a magnitude signal affected by gauss noise in both channels ...
    (comp.soft-sys.matlab)
  • Re: Random delay as a countermeasure to timing attacks
    ... - the signal has a Gaussian distribution, ... the noise ... Neitehr a gaussian nor your step function strike me as good ...
    (sci.crypt)
  • Re: Frequency retrieval from noise
    ... distribution, one performs fourier transform to identify the ... frequencies contained in xby examining the power distribution. ... what if the data is pure gaussian noise? ... gaussian noise, or noise pulled from any distribution for that matter. ...
    (sci.physics)
  • Re: Random numbers with Rice distribution
    ... The rice distribution is related to the normal distribution. ... Indeed a magnitude signal affected by gauss noise in both channels ... Reread my post and you will see that you can generate your variates ...
    (comp.soft-sys.matlab)