timing attack countermeasures (nonrandom but unpredictable de lays)

[leichter_jerrold at emc.com]

| > Why do you need to separate f from f+d?  The attack is based on a timing
| > variation that is a function of k and x, that's all.  Think of it this
way:
| > Your implementation with the new d(k,x) added in is indistinguishable,
in
| > externally visible behavior, from a *different* implementation f'(k,x)
| > which has the undesired property:  That the time is a function of the
| > inputs.
| 
| Suppose that the total computation time was equal to a one way
| function of the inputs k and x.  How does he go about obtaining k?
Why would it matter?  None of the attacks depend on inverting f in any 
analytical sense.  They depend on making observations.  The assumption is
not 
that f is invertible, it's that it's countinous in some rough sense.
 
| It is not enough that it is a function, it must be a function that can
| leak k given x and f(k,x) with an efficiency greater than a
| brute-force of the input space of k (because, presumably, f and the
| output are known to an attacker, so he could simply search for k that
| gives the correct value(s)).
Well, yes ... but the point is to characterize such functions in some useful

way other than "they don't leak".  I suppose if d(k,x) were to be computed
as D(SHA1(k | x)) for some function D, timing information would be lost 
(assuming that your computation of SHA1 didn't leak!); but that's a very 
expensive way to do things:  SHA1 isn't all that much cheaper to compute
than 
an actual encryption.

| In reality, the time it takes to compute the crypto function is just
| another output to the attacker, and should have the same properties
| that any other output has with respect to the inputs one wishes to
| keep secret.  It does not have to be constant.
Agreed.  The problem is to (a) characterize those properties; (b) attain
them 
at acceptable cost.
							-- Jerry


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com