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

[Beryllium Sphere LLC]

Can you destroy the relationship between key contents and timing without hurting average run time?

Each round of AES has sixteen table lookups. If you permute the order in which  the implementation does the lookups, then you get a completely different pattern of cache hits and misses. If you permute the order of lookups in a key-independent fashion for every encryption operation then each key has 16! or almost 21 trillion possible timings.

If I'm not making sense in English, schematic pseudocode would look like

Let indirection_array=random permutation of (0..15)
...
do_round:
For i = 0 to 15
Let j = indirection_array[i]
Let mixcolumns_input[j] = subbytesandshiftrows_array[state[j]]
End for
Let newstate = mixcolumns(mixcolumnsinput)
End do_round

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