timing attack countermeasures (nonrandom but unpredictable delays)

[John Kelsey]

>From: "Travis H." <solinym at gmail.com>
>Sent: Nov 16, 2005 11:37 PM
>To: David Wagner <daw at cs.berkeley.edu>
>Cc: cryptography at 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 at metzdowd.com