[Cryptography] [FORGED] Attackers will always win, and it's getting worse!

[Jerry Leichter]

> I have sometimes argued that for security purposes we need semantic-
> level guarantees about things which are completely inexpressible
> in existing semantic frameworks.  Where 'semantics' has been taken as
> expressing everything intended to be observable about program output,
> I've labeled these additional requirements as 'quasi-semantic', on the
> grounds that they affect or determine 'quasi-output' or side channel output....
> 
> Once you introduce quasi-semantic requirements about particular kinds of
> things NOT happening, the ability to do many kinds of optimizations or
> rewrites vanishes, in ways that cascade through the code often down to
> levels where the effects reach into tight loops where you wouldn't
> expect it.  I'd argue that that's an acceptable cost of doing business.
Many, perhaps most, published side-channel attacks are based on:

1.  Algorithmic issues.  The work the algorithm itself specifies must be done is dependent upon sensitive data; it really doesn't much matter what optimizations you apply or don't apply during code generation.
2.  Hardware issues.  The hardware responds differentially to sensitive data - e.g., there are sensitive-data-dependent rotations, and rotations in the hardware have a signature that depends on how far you're rotating.  (This is so common, in fact, that it's now standard not to use key-dependent rotations.)  This is a mismatch between the basic operations as seen by the algorithm designer and as seen all the way down in the hardware; again, optimization or lack thereof doesn't matter.

I'm sure there exist examples of optimizations introducing side-channel attacks, but they appear to be few and far between.  We've mainly figured out how to deal with the algorithmic issues, but the hardware issues appear to be intractable.  CPU's today are stupendously complex, and vendors long ago stopped giving any details about how operations are actually carried out.  And they feel free to change them all the time in the name of performance.  If you think there's little hope in getting compiler writers to have a mode which gives you fine-grained control ... it's way harder to get the chip makers to give you a set of instructions with a simple, controllable semantic model.  Their answer has been to build the crypto directly into the hardware - hopefully making it resistant to side channel attacks.

So ... a compiler specialized for crypto software, which let you specify every last detail of the code generated, would buy you little.  That's not where the problems are.

It's interesting that the NSA has historically concentrated on hardware implementations of complete cryptosystems.  There are undoubtedly many reasons for this - and unlike pretty much any organization other than a couple of counterparts of NSA around the world, they are in a position to build exactly what they want and require people to use their hardware - but I suspect that part of this is their experience in successfully attacking software-based implementations.

                                                        -- Jerry