Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Constant-time support coming to LLVM: Protecting cryptographic code

blog.trailofbits.com

Post reply on HN
Print view View original

41–50 of 62 posts

Re: Constant-time support coming to LLVM: Protecting cryptographic code

#41

Post by GhosT078 »

frabert wrote: post #2

This has been a sore point in a lot of discussions regarding compiler optimizations and cryptographic code, how compilers and compiler engineers are sabotaging the efforts of cryptographers in making sure there are no side-channels in their code. The issue has never been the compiler, and has always been the language: there was never a way to express the right intention from within C (or most other languages, really)…

SPARK is a very expressive language for implementing cryptographic applications. It is available for some LLVM targets (e.g. x86-64).

Re: Constant-time support coming to LLVM: Protecting cryptographic code

#42

Post by adrian_b »

charcircuit wrote: post #24

These are meaningless without guarantees that the processor will run the instructions in constant time and not run the code as fast as possible. Claims like cmov on x86 always being constant time are dangerous because a microcode update could change that to not be the case anymore. Programmers want an actual guarantee that the code will take the same amount of time. We should be asking our CPU vendors to support enab…

Nowadays both Intel/AMD CPUs and Arm-based CPUs guarantee that a certain subset of the instructions are executed in constant time.

For an example of a list of such instructions see:

https://www.intel.com/content/www/us/en/developer/articles/t...

However, cooperation from the operating system is necessary, as the constant-time execution mode may need to be enabled by setting certain CPU-control bits in protected registers (e.g. IA32_UARCH_MISC_CTL[DOITM]).

See for instance:

https://www.intel.com/content/www/us/en/developer/articles/t...

CMOV is on the list of instructions with constant-time execution, but the list is valid only with the corresponding control bit set correctly.

Re: Constant-time support coming to LLVM: Protecting cryptographic code

#43

Post by colmmacc »

jfindper wrote: post #3
frabert wrote: post #2

This has been a sore point in a lot of discussions regarding compiler optimizations and cryptographic code, how compilers and compiler engineers are sabotaging the efforts of cryptographers in making sure there are no side-channels in their code. The issue has never been the compiler, and has always been the language: there was never a way to express the right intention from within C (or most other languages, really)…

> how compilers and compiler engineers are sabotaging the efforts of cryptographers I'm not exposed to this space very often, so maybe you or someone else could give me some context. "Sabotage" is a deliberate effort to ruin/hinder something. Are compiler engineers deliberately hindering the efforts of cryptographers? If yes... is there a reason why? Some long-running feud or something? Or, through the course of thei…

I don't think it's nefarious but it is sabotage. There's long been an implicit assumption that optimization should be more important than safety.

Yes, languages do lack good mechanisms to mark variables or sections as needing constant-time operation ... but compiler maintainers could have taken the view that that means all code should be compiled that way. Now instead we're marking data and section as "secret" so that they can be left unoptimized. But why not the other way around?

I understand how we get here; speed and size are trivial to measure and they each result in real-world cost savings. I don't think any maintainer could withstand this pressure. But it's still deliberate.

Re: Constant-time support coming to LLVM: Protecting cryptographic code

#44

Post by aw1621107 »

colmmacc wrote: post #43
jfindper wrote: post #3

Earlier quoted context omitted.

> how compilers and compiler engineers are sabotaging the efforts of cryptographers I'm not exposed to this space very often, so maybe you or someone else could give me some context. "Sabotage" is a deliberate effort to ruin/hinder something. Are compiler engineers deliberately hindering the efforts of cryptographers? If yes... is there a reason why? Some long-running feud or something? Or, through the course of thei…

I don't think it's nefarious but it is sabotage. There's long been an implicit assumption that optimization should be more important than safety. Yes, languages do lack good mechanisms to mark variables or sections as needing constant-time operation ... but compiler maintainers could have taken the view that that means all code should be compiled that way. Now instead we're marking data and section as "secret" so tha…

> Now instead we're marking data and section as "secret" so that they can be left unoptimized. But why not the other way around?

Worse cost-benefit tradeoff, perhaps? I'd imagine the amount of code that cares more about size/speed than constant-time operation far outnumbers the amount of code which prioritizes the opposite, and given the real-world benefits you mention and the relative newness of concerns about timing attacks I think it makes sense that compiler writers have defaulted to performance over constant-time performance.

In addition, I think a complicating factor is that compilers can't infer intent from code. The exact same pattern may be used in both performance- and timing-sensitive code, so absent some external signal the compiler has to choose whether it prioritizes speed or timing. If you think more code will benefit from speed than timing, then that is a reasonable default to go with.

Re: Constant-time support coming to LLVM: Protecting cryptographic code

#46

Post by adrian_b »

rurban wrote: post #45

Or just disable the fucking broken optimizer for such a function. #pragma GCC optimize ("O0")

Disabling optimizations does not necessarily result in more deterministic execution.

With "-O0", the generated code normally retains a huge number of useless register loads and stores, which lead to non-deterministic timing due to contention in the use of caches and of the main memory interface. Optimized code may run only inside registers, being thus executed in constant time regardless of what other CPU cores do.

The only good part is that this non-deterministic timing will not normally depend on the data values. The main danger of the non-constant execution time is when this time depends on the values of the processed data, which provides information about those values.

There are cases when disabling optimization may cause data-dependent timing, e.g. if with optimization the compiler would have chosen a conditional move and without optimization it chooses a data-dependent branch.

The only certain way of achieving data-independent timing is to use either assembly language or appropriate compiler intrinsics.

Re: Constant-time support coming to LLVM: Protecting cryptographic code

#47

Post by adrian_b »

wahern wrote: post #12
connicpu wrote: post #10

Earlier quoted context omitted.

The side channel from memory access timings are exactly why cmov is its own instruction on x86_64. It retrieves the memory regardless of the condition value. Anything else would change the timings based on condition. If you're going to segfault that's going to be visible to an attacker regardless because you're going to hang up.

AFAIU, cmov wasn't originally intended to be a guaranteed constant-time operation, Intel and AMD won't commit to keeping it constant-time in the future, but it just so happened that at one point it was implemented in constant-time across CPUs, cryptographers picked up on this and began using it, and now Intel and AMD tacitly recognize this dependency. See, e.g., https://www.intel.com/content/www/us/en/developer/artic…

At your link there is a link to the list of instructions that guarantee constant execution time, independent of the operands.

The list includes CMOV.

However, the instructions from the list are guaranteed to have constant execution time, even on any future CPUs, only if the operating system sets a certain CPU control bit.

So on recent and future Intel/AMD CPUs, one may need to verify that the correct choice has been made between secure execution mode and fastest execution mode.

Re: Constant-time support coming to LLVM: Protecting cryptographic code

#48

Post by cesarb »

adrian_b wrote: post #42
charcircuit wrote: post #24

These are meaningless without guarantees that the processor will run the instructions in constant time and not run the code as fast as possible. Claims like cmov on x86 always being constant time are dangerous because a microcode update could change that to not be the case anymore. Programmers want an actual guarantee that the code will take the same amount of time. We should be asking our CPU vendors to support enab…

Nowadays both Intel/AMD CPUs and Arm-based CPUs guarantee that a certain subset of the instructions are executed in constant time. For an example of a list of such instructions see: https://www.intel.com/content/www/us/en/developer/articles/t... However, cooperation from the operating system is necessary, as the constant-time execution mode may need to be enabled by setting certain CPU-control bits in protected regis…

> However, cooperation from the operating system is necessary, as the constant-time execution mode may need to be enabled by setting certain CPU-control bits in protected registers (e.g. IA32_UARCH_MISC_CTL[DOITM]).

The way ARM does this is way better, since it doesn't need help from the operating system: user-space can directly set and clear the DIT bit. Operating system cooperation is necessary only to know whether that bit exists (because the ID registers are not directly readable by user mode).

Re: Constant-time support coming to LLVM: Protecting cryptographic code

#49

Post by amluto »

matu3ba wrote: post #40
amluto wrote: post #23

Earlier quoted context omitted.

I advocated for that, and then I completely lost track of the status. The whole design is ridiculous.

What would be more sane alternatives, when it becomes obvious that any side-effect of timing is a potential attack vector? See https://www.hertzbleed.com/ for frequency side channels. I do only see dedicated security cores as options with fast data lanes to the CPU similar to what Apple is doing with Secure Enclave or do you have better suggestions that still allow performance and power savings?

A design such that it would actually make sense for a compiler to mark code that should permit data-dependent CPU optimizations differently from code that should not.

This could be done using an opcode prefix, which would bloat code but would work perfectly. Or it could use an RFLAGS bit or a bit in MXCSR or a new register, etc.

Almost anything would be better than an MSR that is only accessible to privileged code.

Re: Constant-time support coming to LLVM: Protecting cryptographic code

#50

Post by cesarb »

amluto wrote: post #49
matu3ba wrote: post #40

Earlier quoted context omitted.

What would be more sane alternatives, when it becomes obvious that any side-effect of timing is a potential attack vector? See https://www.hertzbleed.com/ for frequency side channels. I do only see dedicated security cores as options with fast data lanes to the CPU similar to what Apple is doing with Secure Enclave or do you have better suggestions that still allow performance and power savings?

A design such that it would actually make sense for a compiler to mark code that should permit data-dependent CPU optimizations differently from code that should not. This could be done using an opcode prefix, which would bloat code but would work perfectly. Or it could use an RFLAGS bit or a bit in MXCSR or a new register, etc. Almost anything would be better than an MSR that is only accessible to privileged code.

> Or it could use an RFLAGS bit or a bit in MXCSR or a new register, etc.

> Almost anything would be better than an MSR that is only accessible to privileged code.

ARM does that: their flag (DIT) is accessible by non-privileged code. If you know the architecture has that flag, either because your -march= is recent enough or because the operating system told you so through the hwcaps or the emulated id registers, you can use it freely without needing to switch to privileged mode through a syscall.

Post reply on HN