>From: "Travis H." <[EMAIL PROTECTED]> >Sent: Nov 16, 2005 11:37 PM >To: David Wagner <[EMAIL PROTECTED]> >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 [EMAIL PROTECTED]
