Re: Random delay as a countermeasure to timing attacks
- From: "François Grieu" <fgrieu@xxxxxxxxx>
- Date: 6 Nov 2006 14:27:54 -0800
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
.
- Follow-Ups:
- Re: Random delay as a countermeasure to timing attacks
- From: David Wagner
- Re: Random delay as a countermeasure to timing attacks
- References:
- Random delay as a countermeasure to timing attacks
- From: Francois Grieu
- Re: Random delay as a countermeasure to timing attacks
- From: David Wagner
- Re: Random delay as a countermeasure to timing attacks
- From: David Wagner
- Random delay as a countermeasure to timing attacks
- Prev by Date: Re: generating a nonce
- Next by Date: Re: generating a nonce
- Previous by thread: Re: Random delay as a countermeasure to timing attacks
- Next by thread: Re: Random delay as a countermeasure to timing attacks
- Index(es):
Relevant Pages
|
