[Cryptography] Compiler optimization side channel

[Jerry Leichter]

> 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"...
And now we're back to my original point.

Imagine you're coming to me as a compiler developer and asking for support for such stuff.  OK, do you have a precise semantics for what you're asking for?  "Leaves no extra copies behind":  That requires that the underlying machine have a way to guarantee that.  Do the machines of interest specify such a thing?  How about the operating system?  Imagine that just as I'm about to zero out some memory, the page I would write to, along with the CPU, gets taken away from me.  When I get the CPU again, a fresh copy of that page gets swapped in.  Meanwhile, the old page frame, as it happens, hasn't been written to.  Have I violated your spec?

Is there a way to test that the code I generate actually implements your spec?  When you say the loop is "constant time," presumably that's in the face of variations in the inputs.  What variations?  If you have a shift in there, and the hardware uses a step-by-step shifter ... well, shift is out if the shift amount is variable.  Do I need to test for that?  Can I know how the multiplier timing is dependent on the input variables?  Can I even know what combinations of values I need to try?  I'm not going to ship my compiler with a promise of implementing semantics without both some good analysis, and extensive testing - my reputation is at stake here.

OK, so now it should be clear that what you are asking for is not "no optimization," it's a special kind of optimization, not for speed or space, but to meet a certain set of extra semantic requirements.  This is going to require significant work to implement a different code generation path that will have to be adjusted carefully for different instruction sets and for different implementations of those instruction sets.  I already have to do that for the optimizer, and it's a big, complicated, expensive job.

How important is performance for this code?  Ah, sometimes it doesn't much matter (implementing a handshake); sometimes it's really, really essential (bulk encryption); sometimes it's somewhere in between (running a DH ratchet for forward security).  So I have to implement this while keeping the code at least reasonably fast - itself a challenge on any modern machine.

So my final question:  Just how much code out there will actually be interested in this new compilation mode?  That little, huh?  Sure, it's important, but hey accessing special instructions to manipulate virtual memory is at least as important, and the OS guys don't ask me to generate code for that.

I'll tell you what.  I'll put it in the queue.  Check back next year.  Or maybe next decade.  Meanwhile, here's a way to insert assembler code.  Sure, non-portable - but you're asking me to do a lot of non-portable stuff in the compiler, why don't you have at it while we work on stuff that the vast majority of our users might actually need.

                                                        -- Jerry

PS  Way, way back, there used to be this guy who frequented the old comp.compilers Usenet newsgroup.  He was a number theorist, and had some particular things he wanted implemented in compilers to make his work easier.  He somehow felt that he was owed someone doing this for him (for free, of course - his grants were'nt large enough to fund an effort) - after all, he was a number theorist, and number theory was important!  He kept on and on about this for years, ignoring the responses from actual compiler implementers explaining that what he wanted had no real general use, and they had better things to spend their time on.  People were initially respectful, but eventually he got, at best, just outright ignored.