[18974] in cryptography@c2.net mail archive
Re: timing attack countermeasures (nonrandom but unpredictable
daemon@ATHENA.MIT.EDU (John Kelsey)
Thu Nov 17 20:06:25 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Thu, 17 Nov 2005 11:28:46 -0500 (EST)
From: John Kelsey <kelsey.j@ix.netcom.com>
Reply-To: John Kelsey <kelsey.j@ix.netcom.com>
To: "Travis H." <solinym@gmail.com>,
David Wagner <daw@cs.berkeley.edu>
Cc: cryptography@metzdowd.com
>From: "Travis H." <solinym@gmail.com>
>Sent: Nov 16, 2005 11:37 PM
>To: David Wagner <daw@cs.berkeley.edu>
>Cc: cryptography@metzdowd.com
>Subject: Re: timing attack countermeasures (nonrandom but unpredictable delays)
...
>I don't follow; averaging allows one to remove random variables from
>the overall time, but you're still left with the real computation
>time plus the the deterministic delay I suggested as a function of
>the input.
>Specifically, time t(k,x) = f(k,x) + d(k,x) + r
>Where r is a random variable modelling all random factors, f is the
>time to compute the function, and d is the deterministic delay I
>suggested that is a function of the inputs. Averaging with repeated
>evaluations of the same k and x allows one to compute the mean value
>of r, and the sum f+d, but I don't see how that helps one seperate f
>from d. What am I missing?
Let's assume d(k,x) is a random function of k||x, uniformly
distributed between 0 and T where T is the average time of the
encryption. I choose a set of inputs to the cipher x[0,1,2,...,n-1]
so that if my guess of some part of k is right, I expect their total
timing to be much lower than the average case.
I get back Sum(f(k,x[i])+d(k,x[i])+r[i]).
Suppose my guess is wrong. Now what we expect is:
a. Sum(f(k,x[i]) = average value
b. Sum(d(k,x[i]) = average value
c. Sum(r[i]) = average value
Suppose my guess is right. Now what we expect is:
a. Sum(f(k,x[i]) = unusually low value
b. Sum(d(k,x[i]) = average value
c. Sum(r[i]) = average value
So, right guesses still give me unusually low values, and wrong
guesses still give me average-looking values. That means the timing
channel is still there--d(k,x) only adds random noise.
The only way to avoid this is to make d(k,x) somehow related to
f(k,x). That's the idea behind things like having software or
hardware go through both the 0 and 1 case for each bit processed in an
exponent. In that case, we get d(k,x) being fast when f(k,x) is slow,
and vice versa, and we close the timing channel.
As long as d(k,x) is independent of f(k,x), I can still test guesses
of parts of k or parts of x.
--John Kelsey
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
