Protecting against the cache-timing attack.

[Jon Callas]

One of the things to remember in all of this is that one of the reasons 
we picked Rijndael as the AES was its speed. (And yes, I mean "we." I 
was present at the conferences, and I filled out the little poll about 
which ciphers I liked and why. That means I participated and bear part 
of the responsibility, along with everyone else who was there.)

Rijndael is a fast little bugger. It is the fastest of all the 
candidates. This means that if we're forced to slow it down a little, 
then that isn't really so bad (assuming it can be done easily).

Bulk encryption on modern cpus is really, really fast. We're making 
servers that do a lot of encryption at PGP Corporation. We also do a 
lot of performance testing. One test that we did where we tested how 
many messages 10K in size we could do in an hour, and then 100K in size 
saw a performance drop of between 1 and 10%. Yes, between one percent 
and ten percent!

Bulk encryption is not the bottleneck for a protocol like PGP. The 
bottleneck is some combination of public key encryption and message 
invariant data formatting.

So let's conduct a small thought experiment. Take the set of timings T, 
where it is the timings of all possible AES keys on a given computer. 
(It's going to be different depending on cpu, compiler, memory, etc.) 
Order that set so that the shortest timing is t_0 and the longest one 
is t_omega. Obviously, if you delay until t_omega, you have a 
constant-time encryption.

I'm going to assert that if you delay only until t_omega-1 (by which I 
mean the first timing smaller than t_omega. It is possible that there 
is more than one key with the timing of t_omega. Actually, I think 
there *must* be a set of them through some basic combinatorics.) then 
the system is still secure enough -- that the attack is infeasible. By 
that I mean that the timing attack doesn't work. Let's just presume 
this is true.

So then there are two questions:

What is the largest t_n for which my assertion is still true? In other 
words, what's the minimum delay time?

What is the smallest t_n for which it's still feasible to make the 
timing attack?

"Feasible" is a squishy thing here, but we can get a handle on it. Take 
the example Perry gave -- a wireless router that you can suitably 
inject packets into. If I assume that it's using AES-256, and that the 
key is changed once a decade, and that the attacker consumes 100% of 
the bandwidth of router, then the attacker can only get P timings, and 
P is going to be much smaller than 2^256. That means that there must be 
some t_p that is a delay short enough that makes the attack impractical 
for a set of statistical parameters (like that the chi-square of my key 
guess is less than c).

Now if I'm completely wrong, and you *must* always delay to t_omega, 
that's *also* an interesting answer -- actually more interesting 
because it's counter-intuitive.

So -- is there a way to make some calculations about a small t_m, a 
delay that's kinda skanky, but short, and t_n, a delay that we'd all 
feel good about? Heck -- how do we even find out what t_omega is 
without having to enumerate the set? Or even more practically, if I 
just pick a t, how do I know that it's at least as big as t_omega?

	Jon


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