Optimisation Considered Harmful

[Ben Laurie]

A brief altercation this evening with CERT over the recent hyperthread 
caching issues has brought something that's been simmering at the back 
of my brain to the forefront.

The recent hyperthread/cache key recovery trick, followed by DJB's 
related (IMO) symmetric key recovery, and preceded by the RSA timing 
attacks (Boneh et al?) are all examples of attacks on the same thing: 
optimisation.

The problem is that if different paths through your code expose 
different availability of optimisation, then there's a timing attack 
available. I predict, for example, that someone will find a way to 
attack something using pipeline breaks on Pentium processors[1].

How do we fix this? Well, its easy to say: we make everything equally 
crap - we make sure that all operations are as slow as the slowest 
possible variant can be. However, on a modern processor, this is _very_ 
hard to do.

Could it be that for safe crypto we should be using Z80s?

Cheers,

Ben.

[1] For those who don't know, even old Pentia have several different 
processing units internally, which run in parallel. They can even tell 
when instructions in one's pipeline conflict with another's (e.g. one 
uses a register as input that another is going to change, but hasn't 
yet), and delay processing appropriately. However, sometimes they can't 
work it out (this is, of course, another optimisation, this time for 
transistor count) and so they just throw their hands up, stop all the 
pipelines and start again. This causes a _substantial_ delay, easily 
measurable - I know of loops of tens of instructions that go twice as 
fast if apparently redundant - but pipeline-intelligence-informing - 
instructions are inserted. Of course, the PowerPCs with their 
speculative execution are probably even more fun in this respect (do 
they still do that?).

-- 
 >>>ApacheCon Europe<<<                   http://www.apachecon.com/

http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

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