[Cryptography] Compiler optimization side channel

[Christian Huitema]

On 8/25/2024 6:28 PM, Jerry Leichter wrote:
>> ...
> 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.

Yes. It might work in practice, but it seems to be essentially a 
negative statement, "don't do this behavior that I know is harmful". And 
you are right that just "not optimizing" does not provide any guarantee 
about side effects of the default behavior.

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

Yes indeed. We want to say something like, "compiler, please, try to 
execute the following statements in constant time, whatever the 
variations in cache and branches." And yes, it is something better done 
in the compiler itself than by trying to write code with magical properties.

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

Maybe there is something behind the "abstract machine's description". 
What if the compiler knew of an alternate abstract machine, one that 
would execute the code in constant time and not leave data around if the 
the programmer wrote correct code *for that abstract machine*? And what 
if there was a way to state in the code, "map to this abstract machine, 
not the standard one"?

We would get a split between the programmer, "execute these instructions 
using the constant time model", and the compiler, "write the best 
translation to the abstract model, and the write the compliant mapping 
to this specific hardware."

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

Maybe we could first state the property of this supposed "dream abstract 
machine"...

-- Christian Huitema