Defeating cache timing attack

[cedric lauradoux <cedric.lauradoux@inria.fr>]

A lot of things have been said recently on attacks against 
cryptographic primitives that make use of cache memory.
Those attacks are not new and if you want a more complete story of 
those attacks you mail me I will send you the
complete list of paper related to this subject. Now 2 kind of attacks 
seems to emerge:
- Passive attacks: just observe the timing of the code and try to find 
correlation between time variation and key

-Active Attacks: try to create correlation between timing and the key. 
Those attacks may involve
hyperthreading, or malicious code which produce interruptions and cache 
flushes.

Now the big problem is how to deal with those attacks:
- for active attacks the countermeasure is quite simple : take a dummy 
key and evaluate cache misses of several encryptions.
If the misses ratio are too big: the implementation is under attack 
(the only difficulty is too evaluate the work load of processor).
If we only want to defeat Hyperthreading attacks, we just have to code 
the algorithm using hyperthreading. The first thread
compute the algorithm and the second perform prefetch for the first 
thread.

- passive attacks are more complicated to defeat. The first solution is 
to use constant time memory access algorithm (removing lookup table).
We can also warmup the cache to reduce memory latency using prefetch 
instruction. This solution is not available when cache is small in 
comparison of the table.

Those countermeasures are in test. I hope that it will ready for WeWorc 
conference.

The conclusion is that those attacks are not really dangerous. Several 
software countermeasures are possible and it does not require to 
completely change cache architecture.

What do you think about my countermeasures ? I will be pleased with any 
comments or idea on attacks and countermeasures.


Cédric Lauradoux
Inria Rocquencourt
Project team CODES
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/