[Cryptography] Compiler optimization side channel

[Jerry Leichter]

>>> The right solution is to make your language more expressive so you can say what you mean, e.g., this value is sensitive so don't leave copies of it, this loop needs to run in constant time so don't helpfully remove code that looks dead.
>>> 
>>> I'm not aware of anyone working on this.  Is anyone else?  I suppose I should ask comp.compilers too.
>> I find it extremely unlikely that, even if someone is working on this, it will ever find its way into mainstream compilers.  The fact is, code for which this matters is *extremely* rare.  It's really hard to justify the additional complexity in the compiler and, perhaps, the language to support what probably amounts to, in the entire world, at most, a few hundred thousands of lines of code if you add up all the actually used implementations of cryptographic primitives - as against the many billions of lines for code for which this kind of consideration is completely meaningless.
> 
> Recent compilers do have pragma or attributes to ensure that a particular piece of code is not optimized. They implement it using code marking that tells the compiler to leave this segment as is. It is non standard, not defined in C (let alone C++) and so GCC, Clang and Microsoft all have different names for the macros or the attributes. It is also version dependent, in the sense that old compiler versions don't do that. But there are common traits, such as having the granularity at the function level, as in, "for this function, do not optimize".
> 
> Which makes me think that it should be possible to standardize the feature in a future version of C. But I have no idea what kind of lobbying is required to achieve that.
Yes, but what exactly does "don't optimize this code" mean?  There are typically many ways to express the same source statements in specific machine instructions, and which ones are "optimized" is in the eye of the beholder.

The original message to which I was responding actually gives two examples of what you *really* need to be able to say:  "Don't leave copies of this data around," and "this loop needs to run in constant time."  Neither of these corresponds in any direct way to "don't optimize this code."  In fact, generating a constant-time loop is highly instruction set - and sometimes particular implementation of that instruction set - specific.  There is no particular reason to think that the non-optimized output from the compiler - whatever that might mean - will always be constant-time, no matter what the source code says.

Even the apparently more obvious "don't leave copies of data around" is quite problematic.  Let's take what looks like a nicely defined case of C as specified by its standard, which defines an abstract machine relative to which the semantics of the code is defined.  So we can say that non-optimized code should, in some way, map one-to-one with the operations of the abstract machine.  But ... the abstract machine has no registers, while most real machines can't implement any of the abstract machine's operations without moving data to and from registers.  So saying "just implement the abstract machine" can't in any way lead to a requirement that some register will be cleared after its data is stored to memory.  And of course the same can be said for any memory - like a stack frame - that the generated code for a real machine must use, but which is not visible in the abstract machine's description.

If you are really, really concerned about this kind of thing, what you need to do is first figure out exactly what properties some piece of code is assuming about its executable version, then find a way to express those properties, and finally have a way for a compiler to generate code that actually has those properties, on every machine the compiler targets.  Making sure that when you said "zero this memory location" that the memory location is actually zeroed seems like a trivially easy case.  But what if the data in that location is in the cache, and the cache entry is simply marked stale and not zeroed - but the old value can still be read by privileged code?  What exactly is the compiler supposed to do?
                                                        -- Jerry