5 ms·

Breaking Bad: How Compilers Break Constant-Time~Implementations

66 points by belter 2y ago

moomin 2y ago
I saw a rant on here about this not so long ago: it feels ridiculous that nearly all of our security code is compiled using compilers that cannot provide the guarantees these algorithms need.
- empath75 2y ago
  Seems like a hard problem to solve, because even if you mark some block of code as DO_NOT_OPTIMIZE it still is likely to pull in code from elsewhere that probably has been optimized. Seems like you might have to actually just write the relevant code in inlined machine code.
  - immibis 2y ago
    Inlined micro instructions, at that, with a special flag to prevent the CPU skipping over zero runs in multipliers.
    - crest 2y ago
      I can't wait for some uarch to fuck everyone over and decide that after tracking zeroing idioms in the the renamer the next escalation is to eliminate data dependencies if the renamer detects it's not outcome determinative e.g. AND r1, r2, r3 with the renamer having inferred that one of the inputs is zero so the other isn't needed and the result must be zero. Or tracking identity elements for operations (0 for addition/substraction, 1 for multiplication/division) to bypass the computation.
      - marcosdumay 2y ago
        Well, multiplication used to take variable time not long ago. Anyway, IMO, CPU designers seem more aware of security implications than compiler developers. I expect more attention to those things in the future, not less.
      - eigenform 2y ago
        You [as a designer] could probably add latency synthetically and still benefit from avoiding a physical register allocation (although I guess, that's only a workaround for leaking in the time domain). edit: Anyway, if your threat model includes "attacker can discern differences in power at uop-granularity and make meaningful correlations", you are probably doomed at the outset and you should not have used an out-of-order machine in the first place.
      - pjc50 2y ago
        SIMD instructions are a good way to avoid this, even if you only use one column of the operands the fact that it's SIMD means operations have to happen in lockstep across the execution units.
        gpderetta 2y ago
        Do they? An arch with bultin lane predication (like AVX512) could easily implement wide SIMD on top of narrower ALU and then skip the masked out lanes. Actual runtime would depend on the number of non masked lanes. I'm not up to date on GPU architectures, bit I wouldn't be surprised of they do this sort of stuff.
  - jonhohle 2y ago
    It’s not only that, but also the semantics of the language. Is, for example, integer comparison guaranteed to be constant time? What about integer comparison with constants that require multiple load instructions (like on MIPS where all instructions are word sized so loading words requires two instructions). Is it “wrong” to do two comparisons against the high half and the low half independently, each branching on failure, if the language provides no guarantees and the outcome is the same? Ultimately security focused languages that provide operational guarantees with C linkage are probably necessary. I don’t think it’s enough to not optimize C.
- klooney 2y ago
  A lot of it is in ASM, for just that reason.
  - saghm 2y ago
    Sure, but needing to write security code in assembly is ridiculous for other reasons
kibwen 2y ago
> Our work highlights that current defensive programming techniques are more akin to anecdotal workarounds to compilers’ behavior rather than a systematic solution. Our results point out that high-level constant-time code is prone to dangerous transformations and optimizations from compilers and calls for cooperation between developers of security-critical libraries and general-purpose compilers. All optimizing compilers perform optimizations based on the notion of an abstract machine, which determines what semantics of the original program must be conserved. And the abstract machine for a given language is usually provided by the language that is being implemented (except for e.g. languages that just give up and say "give me C's abstract machine"). You definitely don't want compiler backends trying to "guess" when some defensive programming technique is being used, so that they can compile it conservatively. That's a dead-end pathway to madness. You need languages to give you the power to explicitly say "this operation is constant time, don't mess with it". And in practice they do give you this power, via inline assembly. Of course inline assembly is suboptimal for a lot of reasons, and we can certainly try to do better, but this is a language design problem, not an optimizing compiler problem.
- the8472 2y ago
  Not just the abstract machines. CPUs don't guarantee constant-time execution for most instructions. And if you target wasm or some other intermediate compilation target then the first compiler can't do much about the 2nd compiler applying additional optimizations. And then there are post-link optimizations where any hypothetical "please don't optimize this" annotations would be gone.
  - pclmulqdq 2y ago
    In a theoretical sense only, that is true on x86 when a flag (that is always set) is not set. The vast majority of useful instructions are constant-time (in the value of the data).
    - nullc 2y ago
      Indeed, but the manufacturer doesn't promise anything-- for all you know the next processor generation or even microcode revision could change that. It would be nice for processor makers to explicitly specify that the common arithmetic instructions will take time which is constant in terms of their argument data.
p4bl0 2y ago
The subject of my PhD thesis was formal approach to cryptographic implementation against side-channel attacks [1]. In the lab I worked at, most people wrote assembly code for precisely the reasons discussed here [2], and a part of my work consisted in applying a form of formal verification directly on assembly code rather than a more abstract version of the cryptographic algorithms. You cannot trust compilers which are designed with efficiency in mind when your main objective is security. Keeping the same semantics and going as fast as possible often break security measures. And that's not just for constant-time implementations, sometimes it's a lot more simpler than that. Some security scheme against power consumption side-channel attacks, such as dual-rail with precharge logic, require that registers are zeroed before being written to. A compiler seeing code such as: x = 0 /* first write, zeroing */ x = sensitive_data /* second write, actual value */ will of course consider that the first write is never read and optimize it away, thus breaking the security scheme… Then, there's also the need to make sure that the register your using is always the same (because leakage profile may differ a lot between the different registers of a single device). All the more reasons to write critical cryptographic code in directly in assembly. [1] https://pablo.rauzy.name/research.html#phd https://pablo.rauzy.name/research.html#phd [2] A ~fun anecdote: I'm a computer scientist, but most people at that lab were in electronics, and for them assembly code was considered high level because it was already software!
- badmintonbaseba 2y ago
  I get that assembly gets you closer, but does it actually give you the guarantees that you need? Do you have detailed documentation of what instructions and patterns you can use to avoid timing and other side channels that applies to many CPUs that implement an instruction set?
  - p4bl0 2y ago
    That depends a lot on the hardware. For some embedded systems, such as 8-bit smartcards, you can get pretty detailed datasheets from the manufacturer, and the architecture is a lot simpler than modern CPUs.
  - pjc50 2y ago
jkaptur 2y ago
If you offer a programmer a deal where you make their code x% faster on average, never slower, and the actual speedup depends on a huge number of factors making it really hard to reason about, they'll take it 99.99% 0f the time. It seems to me that the entire stack is built on this assumption, making life incredibly difficult the other 0.01% of the time.
- high_na_euv 2y ago
  No. Nobody asks such a question and not all would answer it the same. Id rather take 5% perf. regression to my cpp code if it meant that compile time halves and errors quality will be better
badmintonbaseba 2y ago
Maybe this is overly naive, but I always wondered whether timing side channels could be mitigated by scheduling authentication responses before doing the crypto calculations. 1. authentication request arrives 2. schedule response at a later time, generously leaving time for doing the next step 3. do part of the work that is sensitive to timing attacks 4. respond at scheduled time
- avidiax 2y ago
  That applies over a network. It doesn't apply to someone that has physical access to the machine. Even if the machine delays a response, the power profile of the computation will tell the exact timing of the computation. Since there is lots of cryptography used to keep users out of their own hardware (or stolen hardware) these days, this is important.
jedisct1 2y ago
Jasmin is an amazing tool to write code that's proven to be free of side channels, memory safe, and protected against common speculative execution attacks: https://github.com/jasmin-lang/jasmin https://github.com/jasmin-lang/jasmin I wrote AEGIS implementations in it: https://github.com/jedisct1/aegis-jasmin https://github.com/jedisct1/aegis-jasmin and it was a really great experience.
Validark 2y ago
Good for the authors for putting the idea out there I guess, but to me it seems pretty obvious that people who never look at their assembly would have no idea whether it matches their expectations. And it's not hard. Godbolt.org is free for everyone. Checking if the code branches is super easy, you don't need a super smart runtime analysis tool to figure out if there's a branch. Ditto for everything else you want to check.
LorenPechtel 2y ago
I think the only real option is for the compilers to add a couple of limitations: 1) Allow any block of code to be defined as constant-time. The compiler is forbidden any optimizations that could break this. Constant-time routines can only call other routines that are likewise declared as constant-time. 2) Allow any operation to be defined as important. The compiler can't remove it as redundant.
mrngm 2y ago
A recent thread on compiler optimizations and cryptography (blog post by djb): https://news.ycombinator.com/item?id=41146860 https://news.ycombinator.com/item?id=41146860

66 points by belter 2y ago

I saw a rant on here about this not so long ago: it feels ridiculous that nearly all of our security code is compiled using compilers that cannot provide the guarantees these algorithms need.

empath75 2y ago
Seems like a hard problem to solve, because even if you mark some block of code as DO_NOT_OPTIMIZE it still is likely to pull in code from elsewhere that probably has been optimized. Seems like you might have to actually just write the relevant code in inlined machine code.
- immibis 2y ago
  Inlined micro instructions, at that, with a special flag to prevent the CPU skipping over zero runs in multipliers.
  - crest 2y ago
    I can't wait for some uarch to fuck everyone over and decide that after tracking zeroing idioms in the the renamer the next escalation is to eliminate data dependencies if the renamer detects it's not outcome determinative e.g. AND r1, r2, r3 with the renamer having inferred that one of the inputs is zero so the other isn't needed and the result must be zero. Or tracking identity elements for operations (0 for addition/substraction, 1 for multiplication/division) to bypass the computation.
    - marcosdumay 2y ago
      Well, multiplication used to take variable time not long ago. Anyway, IMO, CPU designers seem more aware of security implications than compiler developers. I expect more attention to those things in the future, not less.
    - eigenform 2y ago
      You [as a designer] could probably add latency synthetically and still benefit from avoiding a physical register allocation (although I guess, that's only a workaround for leaking in the time domain). edit: Anyway, if your threat model includes "attacker can discern differences in power at uop-granularity and make meaningful correlations", you are probably doomed at the outset and you should not have used an out-of-order machine in the first place.
    - pjc50 2y ago
      SIMD instructions are a good way to avoid this, even if you only use one column of the operands the fact that it's SIMD means operations have to happen in lockstep across the execution units.
      - gpderetta 2y ago
        Do they? An arch with bultin lane predication (like AVX512) could easily implement wide SIMD on top of narrower ALU and then skip the masked out lanes. Actual runtime would depend on the number of non masked lanes. I'm not up to date on GPU architectures, bit I wouldn't be surprised of they do this sort of stuff.
- jonhohle 2y ago
  It’s not only that, but also the semantics of the language. Is, for example, integer comparison guaranteed to be constant time? What about integer comparison with constants that require multiple load instructions (like on MIPS where all instructions are word sized so loading words requires two instructions). Is it “wrong” to do two comparisons against the high half and the low half independently, each branching on failure, if the language provides no guarantees and the outcome is the same? Ultimately security focused languages that provide operational guarantees with C linkage are probably necessary. I don’t think it’s enough to not optimize C.
klooney 2y ago
A lot of it is in ASM, for just that reason.
- saghm 2y ago
  Sure, but needing to write security code in assembly is ridiculous for other reasons

kibwen 2y ago

> Our work highlights that current defensive programming techniques are more akin to anecdotal workarounds to compilers’ behavior rather than a systematic solution. Our results point out that high-level constant-time code is prone to dangerous transformations and optimizations from compilers and calls for cooperation between developers of security-critical libraries and general-purpose compilers. All optimizing compilers perform optimizations based on the notion of an abstract machine, which determines what semantics of the original program must be conserved. And the abstract machine for a given language is usually provided by the language that is being implemented (except for e.g. languages that just give up and say "give me C's abstract machine"). You definitely don't want compiler backends trying to "guess" when some defensive programming technique is being used, so that they can compile it conservatively. That's a dead-end pathway to madness. You need languages to give you the power to explicitly say "this operation is constant time, don't mess with it". And in practice they do give you this power, via inline assembly. Of course inline assembly is suboptimal for a lot of reasons, and we can certainly try to do better, but this is a language design problem, not an optimizing compiler problem.

the8472 2y ago
Not just the abstract machines. CPUs don't guarantee constant-time execution for most instructions. And if you target wasm or some other intermediate compilation target then the first compiler can't do much about the 2nd compiler applying additional optimizations. And then there are post-link optimizations where any hypothetical "please don't optimize this" annotations would be gone.
- pclmulqdq 2y ago
  In a theoretical sense only, that is true on x86 when a flag (that is always set) is not set. The vast majority of useful instructions are constant-time (in the value of the data).
  - nullc 2y ago
    Indeed, but the manufacturer doesn't promise anything-- for all you know the next processor generation or even microcode revision could change that. It would be nice for processor makers to explicitly specify that the common arithmetic instructions will take time which is constant in terms of their argument data.

p4bl0 2y ago

The subject of my PhD thesis was formal approach to cryptographic implementation against side-channel attacks [1]. In the lab I worked at, most people wrote assembly code for precisely the reasons discussed here [2], and a part of my work consisted in applying a form of formal verification directly on assembly code rather than a more abstract version of the cryptographic algorithms. You cannot trust compilers which are designed with efficiency in mind when your main objective is security. Keeping the same semantics and going as fast as possible often break security measures. And that's not just for constant-time implementations, sometimes it's a lot more simpler than that. Some security scheme against power consumption side-channel attacks, such as dual-rail with precharge logic, require that registers are zeroed before being written to. A compiler seeing code such as: x = 0 /* first write, zeroing */ x = sensitive_data /* second write, actual value */ will of course consider that the first write is never read and optimize it away, thus breaking the security scheme… Then, there's also the need to make sure that the register your using is always the same (because leakage profile may differ a lot between the different registers of a single device). All the more reasons to write critical cryptographic code in directly in assembly. [1] https://pablo.rauzy.name/research.html#phd https://pablo.rauzy.name/research.html#phd [2] A ~fun anecdote: I'm a computer scientist, but most people at that lab were in electronics, and for them assembly code was considered high level because it was already software!

badmintonbaseba 2y ago
I get that assembly gets you closer, but does it actually give you the guarantees that you need? Do you have detailed documentation of what instructions and patterns you can use to avoid timing and other side channels that applies to many CPUs that implement an instruction set?
- p4bl0 2y ago
  That depends a lot on the hardware. For some embedded systems, such as 8-bit smartcards, you can get pretty detailed datasheets from the manufacturer, and the architecture is a lot simpler than modern CPUs.
- pjc50 2y ago

jkaptur 2y ago

If you offer a programmer a deal where you make their code x% faster on average, never slower, and the actual speedup depends on a huge number of factors making it really hard to reason about, they'll take it 99.99% 0f the time. It seems to me that the entire stack is built on this assumption, making life incredibly difficult the other 0.01% of the time.

high_na_euv 2y ago
No. Nobody asks such a question and not all would answer it the same. Id rather take 5% perf. regression to my cpp code if it meant that compile time halves and errors quality will be better

badmintonbaseba 2y ago

Maybe this is overly naive, but I always wondered whether timing side channels could be mitigated by scheduling authentication responses before doing the crypto calculations. 1. authentication request arrives 2. schedule response at a later time, generously leaving time for doing the next step 3. do part of the work that is sensitive to timing attacks 4. respond at scheduled time

avidiax 2y ago
That applies over a network. It doesn't apply to someone that has physical access to the machine. Even if the machine delays a response, the power profile of the computation will tell the exact timing of the computation. Since there is lots of cryptography used to keep users out of their own hardware (or stolen hardware) these days, this is important.

jedisct1 2y ago

Jasmin is an amazing tool to write code that's proven to be free of side channels, memory safe, and protected against common speculative execution attacks: https://github.com/jasmin-lang/jasmin https://github.com/jasmin-lang/jasmin I wrote AEGIS implementations in it: https://github.com/jedisct1/aegis-jasmin https://github.com/jedisct1/aegis-jasmin and it was a really great experience.

Validark 2y ago

Good for the authors for putting the idea out there I guess, but to me it seems pretty obvious that people who never look at their assembly would have no idea whether it matches their expectations. And it's not hard. Godbolt.org is free for everyone. Checking if the code branches is super easy, you don't need a super smart runtime analysis tool to figure out if there's a branch. Ditto for everything else you want to check.

LorenPechtel 2y ago

I think the only real option is for the compilers to add a couple of limitations: 1) Allow any block of code to be defined as constant-time. The compiler is forbidden any optimizations that could break this. Constant-time routines can only call other routines that are likewise declared as constant-time. 2) Allow any operation to be defined as important. The compiler can't remove it as redundant.

mrngm 2y ago

A recent thread on compiler optimizations and cryptography (blog post by djb): https://news.ycombinator.com/item?id=41146860 https://news.ycombinator.com/item?id=41146860