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

[Ian Grigg]

On Friday 24 June 2005 04:36, Beryllium Sphere LLC wrote:
> >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}. 

The rearrangement cost should be fairly low compared to
the cost of doing the decrypt in the first place?  And rekeying
involves network interchange which is expensive and
"complicated".

> 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.   

You don't need entropy, do you?  All you need to do is generate
an unrelatable time signature for a particular decryption, and for
that you just need a stream that is unrelated in its timing effects.

What I'm not sure about is if the stream needs to be secret.  If
the listener knows how you permute, can that be then factored
into the timing statistics?  If not, then simply use the last decrypt
in the mode as a seed to create the next table.  If it has to be
kept secret then generate a new xor-chain that is keyed from
original secret key (including an enlarged key).  Either way,
it seems as if the "PRNG" of past decrypts would solve the table
keying need.

Further as there is no coordination required in the table keying,
the decryptor has wide flexibility in strategies, such as using
the secret key to hash the last ciphertext to hash the table.

> 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?

There are two distinct classes of problems here - fixes that
would work on AES, and fixes that would work on any block
cipher.  Your neat idea falls into the former.

iang
-- 
Advances in Financial Cryptography, Issue 1:
   https://www.financialcryptography.com/mt/archives/000458.html
Daniel Nagy, On Secure Knowledge-Based Authentication
Adam Shostack, Avoiding Liability: An Alternative Route to More Secure Products
Ian Grigg, Pareto-Secure

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