AES timing attacks, why not "whiten" the implementation?

[Beryllium Sphere LLC]

>1) How do you generate this in a way that does not leak information about
the permutation generated?

>2) How many times can you re-use a single indirection array?

>3) How quickly can you generate new indirection arrays?

Good questions, which probably require empirical answers. 

The added cost of this particular whitening approach (question 3) is the cost of shuffling an array plus, I'd expect more important, the cost of replacing 44+ bits of randomness (log2(16!)).

How often you can afford to rearrange table access is a question much like how often you can afford rekeying. The attacker still gets information from timing, of course (question 1), but it's information about the pair {key, table access permutation}. 

If you had unlimited entropy available you could re-permute on every encryption or decryption. The minimum frequency would depend on how many trials your attacker needs in order to nail down a key.

The questions I don't know how to answer are
(a) How many bits worth of confusion does this really add for an attacker? There must be symmetries such that some subsets of permutations will have identical cache timings. The answer to (a) determines the answer to (2).
(b) Is there a better way to scramble the timing of an AES operation without going to the last resort of padding everyting to worst-case timing?

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