Re: timing attack countermeasures (nonrandom but unpredictable delays)
Good points all. I was implicitly assuming that d(k, x) is related to the timing of f(k,x) -- tailored to the algorithm(s) used, and that the attacker cannot control k. Actually the idea was to have k merely provide a unique function d_k(x) for each host. 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. Interestingly, I read a book that says that there's no reason for a computer which performs only reversible operations needs to dissipate heat. Basically, destroying information requires generating heat, but actual computation does not. I can't quite place my finger on it, but something in my head says this is related to doing operations on both inputs and their complements. Or more accurately, it involves having as many output bits as input bits. I wonder if there is any more significant relationship. Wouldn't it be neat if the same countermeasure could prevent both timing and power consumption side-channel attacks? -- http://www.lightconsulting.com/~travis/ -- We already have enough fast, insecure systems. -- Schneier Ferguson GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: timing attack countermeasures (nonrandom but unpredictable delays)
In many cases, the observed time depends both on the input and on some other random noise. In such cases, averaging attacks that use the same input over and over again will continue to work, despite the use of a pseudorandom input-dependent delay. For instance, think of a timing attack on AES, where the time compute the map X |-- AES(K,X) depends only on K and X, but where the measured time depends on the computation time (which might be a deterministic function of K and X) plus the network latency (which is random). Indeed, in this example even the computation time might not be a deterministic function of K and X: it might depend on the state of the cache, which might have some random component. 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? -- http://www.lightconsulting.com/~travis/ -- We already have enough fast, insecure systems. -- Schneier Ferguson GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: timing attack countermeasures (nonrandom but unpredictable delays)
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]
