[Cryptography] Compiler optimization side channel

Tue Aug 27 17:52:27 EDT 2024

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> On Aug 27, 2024, at 3:39 PM, Jerry Leichter <leichter at lrw.com> wrote:
> 
>> 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.

Your larger point is a great one. Although, as someone who has been burned on this in past lives, I would be happy with the much more modest ask of simply locking in behavior, or standardized directives to avoid certain types of optimization (right now some compilers have it, some don’t, and they are all different), or something like that. Clang in particular has not even been consistent across minor releases, and DJB has a recent post complaining about it: 

https://blog.cr.yp.to/20240803-clang.html

You can write “canary code” to detect some optimizations, but even that is trickier than it seems. My goto is now to have hidden flags to detect when it hasn’t been compiled a particular way (i.e., by me, shipped as a binary lib) then complain loudly about that to stderr or crashing.

There’s research on the problem but I’ve not seen great solutions. The folks who have tried to write code avoiding timing and other side channels all recognize the issues, but lack the clout to do much about it. 

-Rick
-----BEGIN PGP SIGNATURE-----
Version: ProtonMail

wsFzBAEBCAAnBQJmzkqaCRA/GuWbfQE6TRYhBAGFytdGt1Ef10NhlD8a5Zt9
ATpNAACd1BAAoxaJBdGtDrQxt2PdIkQKXJNt00PtTm8LDbhCfTlvawI+EbPC
fwDmOHbJwrS9fHqOixDDmCKjhAXAEut1S+hnWdUWLmcrbjasrksbwyL7i90O
gOChZG+lXtenMROziESrmd8svDVLAVQp/y2Nb3YjredOvZKLes5v/PGSJ3H8
s4QP5hUjp8duCbAyMPbAgQBLVPh3u00eQZpIcGkr9YL7/Yppf+YpoiXg5gbW
BYSlSoYoxpqYiU0ySVYfqlEsxdcuWgK4BLRfK0b27lS//tsPLfq6At0f5FY1
rOYyW9W1SNtP1udjQg9ie8fapladZFDkOd08Qaz2LL9iZtds2IEKTaP+9PuA
3olJ6T1ptkeJBoGiRM+npyFZEN6oYc4lmmJ7/zn5JRYla7n2e+UPy0mqo2St
djL2Sus7Eu/P/+HeUqM4ApP5OQzjUkeiU8+5b0TO/N+Hz57El3r6EsRzV9+9
09BygQDRd0v3kBsttBmYSC08qTMePETtTd8M6CZBGIsHq3D4Yk2Jnwq/drJ8
ayCu2OGbpmL48IMeDoTIhJLF/YALsW5tW15AkgnmOzKeZrCUU23QYTFSrfDB
vHtgwqPZobOPGFtiQQveSD+21rePmb88rTPPMrsr53WxrSqf7sUmz/WQa493
IHxyq9xcx70QBf4sj1v7SLP7L94YMZtY6Ho=
=wuXR
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: publickey - rick at carback.us - 0x0185CAD7.asc
Type: application/pgp-keys
Size: 3147 bytes
Desc: not available
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20240827/c26f1322/attachment.key>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: publickey - rick at carback.us - 0x0185CAD7.asc.sig
Type: application/pgp-signature
Size: 566 bytes
Desc: not available
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20240827/c26f1322/attachment.sig>