9 ms·

I think this is actually a mistake by the author since the rant is mostly focused on implementation defined behavior, not undefined. The examples they give are

by duped 2y ago

I think this is actually a mistake by the author since the rant is mostly focused on implementation defined behavior, not undefined. The examples they give are all perfectly valid code. The specific bugs they're talking about seem to be compiler optimizations that replace bit twiddling arithmetic into branches, which isn't a safe optimization if the bit twiddling happens in a cryptographic context because it opens the door for timing attacks. I don't think it's correct to call either the source code or compiler buggy, it's the C standard that is under specified to the author's liking and it creates security bugs on some targets. Ultimately though I can agree with the C standard authors that they cannot define the behavior of hardware, they can only define the semantics for the language itself. Crypto guys will have to suffer because the blame is on the hardware for these bugs, not the software.

gabrielhidasy 2y ago
Where suffer means "not be lazy, implement the assembly for your primitives in a lib, optimize it as best as you can without compromising security, do not let the compiler 'improve' it"
- Dylan16807 2y ago
  But then you're not writing C, except maybe as some wrappers. Wanting to use C isn't laziness. Making it nearly unfeasible to use C is the most suffering a C compiler can inflict.
  - g15jv2dp 2y ago
    There's no reason that C should be suitable for every purpose under the sun.
    - Dylan16807 2y ago
      Fiddling some bits cross-platform is supposed to be one of them.
      - zdragnar 2y ago
        As was pointed out elsewhere, fiddling bits with constant time guarantees isn't part of the C specification. You need a dedicated implementation that offers those guarantees, which isn't clang (or C, to be pedantic).
        Dylan16807 2y ago
        It's not in the spec right now but it still feels solidly in C's wheelhouse to me.
        viraptor 2y ago
        Fortunately you don't have to go 100% one way or the other. Write your code in C, compile and check it's correct and constant time, then commit that assembly output to the repo. You can also clean it up yourself or add extra changes on top. You don't need to rely on C to guarantee some behaviour forever.
        uecker 2y ago
        I agree that an extension (e.g. a pragma or some high-level operations similar to ckd_{add,sub,mul}) that allows writing code with fixed timing would be very useful. But we have generally the problem that there are far more people complaining that actually contributing usefully to the ecosystem. For example, I have not seen anybody propose or work on such an extension for GCC.
        PhilipRoman 2y ago
        The problem doesn't stop there, if you want to ensure constant time behaviour you must also be able to precisely control memory loads/stores, otherwise cache timings can subvert even linear assembly code. If you have to verify the assembly, might as well write it in assembly.
        NohatCoder 2y ago
        The cryptographic constant time requirement only concerns operations that are influenced by secret data. You can't learn the contents of say a secret key by how long it took to load from memory. But say we use some secret data to determine what part of the key to load, then the timing might reveal some of that data.
tialaramex 2y ago
The blog post does, at the very end, mention the thing you should actually do. You need a language where you can express what you actually meant, which in this case is "Perform this constant time operation". Having expressed what you meant, now everybody between you and the hardware can co-operate to potentially deliver that. So long as you write C (or C++) you're ruined, you cannot express what you meant, you are second guessing the compiler authors instead. I think a language related to WUFFS would be good for this in the crypto world. Crypto people know maths already, so the scariest bits of such a language (e.g. writing out why you believe it's obvious that 0 <= offset + k + n < array_length so that the machine can see that you're correct or explain why you're wrong) wouldn't be intimidating for them. WUFFS doesn't care about constant time, but a similar language could focus on that.
- eschneider 2y ago
  > You need a language where you can express what you actually meant, which in this case is "Perform this constant time operation". Having expressed what you meant, now everybody between you and the hardware can co-operate to potentially deliver that. Yeah, even with assembly, your timing guarantees are limited on modern architectures. But if you REALLY need something specific from the machine, that's where you go.
  - pjmlp 2y ago
    And besides, Assembly should not be a scary thing. Even most managed languages provide a way to get down into Assembly dumps from their AOT and JIT compiler toolchains. Maybe we need some TikTok videos showing how to do such workflows.
    - eschneider 2y ago
      There's nothing terribly difficult to writing specific routines in asm. It's kinda fun, actually. Assembly _in the large_ is hard, just because you need to be next-level organized to keep things from being a mess.
topspin 2y ago
> it's the C standard that is under specified to the author's liking Isn't this unreasonable? Here we are, 52, years down the road with C et al. and suddenly it's expected that compiler developers must consider any change in the light of timing attacks? At what point do such new expectations grind compiler development to a halt? What standard would a compiler developer refer to to stay between the lines? My instincts tell me that this would be a forever narrowing and forever moving target. Does timing sensitivity ever end? Asked differently: is there any code that deals in sensitive information that can't, somehow, be compromised by timing analysis? Never mind cryptographic algorithms. Just measuring the time needed to compute the length of strings will leak something of use, given enough stimuli and data collection. Is there some reason a cryptographic algorithm developer must track the latest release of a compiler? Separate compilation and linking is still a thing, as far as I know. Such work could be isolated to "validated" compilers, leaving the insensitive code (if that concept is even real...) to whatever compiler prevails. Also, it's not just compilers that can "optimize" code. Processing elements do this as well. Logically, therefore, must we not also expect CPU designers to also forego changes that could alter timing behavior? Forever? I've written a lot of question marks above. That's because this isn't my field. However, invoking my instincts again: what, short of regressing to in-order, non-speculative cores and freezing all compiler development, could possibly satisfy the expectation that no changes are permitted to reveal timing differences where it previously hadn't? This all looks like an engineering purity spiral.
- dataflow 2y ago
  > Isn't this unreasonable? Here we are, 52, years down the road with C et al. and suddenly it's expected that compiler developers must consider any change in the light of timing attacks? We already went through a similar case to this: when the C++11 multithreaded memory model was introduced, compiler authors were henceforth forced to consider all future optimizations in light of multithreading. Which actually forced them to go back and suppress some optimizations that otherwise appeared reasonable. This isn't to say the idea is good (or bad), but just that "compiler development will grind to a halt" is not a convincing against it.
  - 2y ago
n_plus_1_acc 2y ago
The optimizations are valid because the C standard and the semantics of its abstract machine don't have a concept of timing.

by duped 2y ago

gabrielhidasy 2y ago

Where suffer means "not be lazy, implement the assembly for your primitives in a lib, optimize it as best as you can without compromising security, do not let the compiler 'improve' it"

Dylan16807 2y ago
But then you're not writing C, except maybe as some wrappers. Wanting to use C isn't laziness. Making it nearly unfeasible to use C is the most suffering a C compiler can inflict.
- g15jv2dp 2y ago
  There's no reason that C should be suitable for every purpose under the sun.
  - Dylan16807 2y ago
    Fiddling some bits cross-platform is supposed to be one of them.
    - zdragnar 2y ago
      As was pointed out elsewhere, fiddling bits with constant time guarantees isn't part of the C specification. You need a dedicated implementation that offers those guarantees, which isn't clang (or C, to be pedantic).
      - Dylan16807 2y ago
        It's not in the spec right now but it still feels solidly in C's wheelhouse to me.
        viraptor 2y ago
        Fortunately you don't have to go 100% one way or the other. Write your code in C, compile and check it's correct and constant time, then commit that assembly output to the repo. You can also clean it up yourself or add extra changes on top. You don't need to rely on C to guarantee some behaviour forever.
        uecker 2y ago
        I agree that an extension (e.g. a pragma or some high-level operations similar to ckd_{add,sub,mul}) that allows writing code with fixed timing would be very useful. But we have generally the problem that there are far more people complaining that actually contributing usefully to the ecosystem. For example, I have not seen anybody propose or work on such an extension for GCC.
        PhilipRoman 2y ago
        The problem doesn't stop there, if you want to ensure constant time behaviour you must also be able to precisely control memory loads/stores, otherwise cache timings can subvert even linear assembly code. If you have to verify the assembly, might as well write it in assembly.
        NohatCoder 2y ago
        The cryptographic constant time requirement only concerns operations that are influenced by secret data. You can't learn the contents of say a secret key by how long it took to load from memory. But say we use some secret data to determine what part of the key to load, then the timing might reveal some of that data.

tialaramex 2y ago

The blog post does, at the very end, mention the thing you should actually do. You need a language where you can express what you actually meant, which in this case is "Perform this constant time operation". Having expressed what you meant, now everybody between you and the hardware can co-operate to potentially deliver that. So long as you write C (or C++) you're ruined, you cannot express what you meant, you are second guessing the compiler authors instead. I think a language related to WUFFS would be good for this in the crypto world. Crypto people know maths already, so the scariest bits of such a language (e.g. writing out why you believe it's obvious that 0 <= offset + k + n < array_length so that the machine can see that you're correct or explain why you're wrong) wouldn't be intimidating for them. WUFFS doesn't care about constant time, but a similar language could focus on that.

eschneider 2y ago
> You need a language where you can express what you actually meant, which in this case is "Perform this constant time operation". Having expressed what you meant, now everybody between you and the hardware can co-operate to potentially deliver that. Yeah, even with assembly, your timing guarantees are limited on modern architectures. But if you REALLY need something specific from the machine, that's where you go.
- pjmlp 2y ago
  And besides, Assembly should not be a scary thing. Even most managed languages provide a way to get down into Assembly dumps from their AOT and JIT compiler toolchains. Maybe we need some TikTok videos showing how to do such workflows.
  - eschneider 2y ago
    There's nothing terribly difficult to writing specific routines in asm. It's kinda fun, actually. Assembly _in the large_ is hard, just because you need to be next-level organized to keep things from being a mess.

topspin 2y ago

> it's the C standard that is under specified to the author's liking Isn't this unreasonable? Here we are, 52, years down the road with C et al. and suddenly it's expected that compiler developers must consider any change in the light of timing attacks? At what point do such new expectations grind compiler development to a halt? What standard would a compiler developer refer to to stay between the lines? My instincts tell me that this would be a forever narrowing and forever moving target. Does timing sensitivity ever end? Asked differently: is there any code that deals in sensitive information that can't, somehow, be compromised by timing analysis? Never mind cryptographic algorithms. Just measuring the time needed to compute the length of strings will leak something of use, given enough stimuli and data collection. Is there some reason a cryptographic algorithm developer must track the latest release of a compiler? Separate compilation and linking is still a thing, as far as I know. Such work could be isolated to "validated" compilers, leaving the insensitive code (if that concept is even real...) to whatever compiler prevails. Also, it's not just compilers that can "optimize" code. Processing elements do this as well. Logically, therefore, must we not also expect CPU designers to also forego changes that could alter timing behavior? Forever? I've written a lot of question marks above. That's because this isn't my field. However, invoking my instincts again: what, short of regressing to in-order, non-speculative cores and freezing all compiler development, could possibly satisfy the expectation that no changes are permitted to reveal timing differences where it previously hadn't? This all looks like an engineering purity spiral.

dataflow 2y ago
> Isn't this unreasonable? Here we are, 52, years down the road with C et al. and suddenly it's expected that compiler developers must consider any change in the light of timing attacks? We already went through a similar case to this: when the C++11 multithreaded memory model was introduced, compiler authors were henceforth forced to consider all future optimizations in light of multithreading. Which actually forced them to go back and suppress some optimizations that otherwise appeared reasonable. This isn't to say the idea is good (or bad), but just that "compiler development will grind to a halt" is not a convincing against it.
- 2y ago

n_plus_1_acc 2y ago

The optimizations are valid because the C standard and the semantics of its abstract machine don't have a concept of timing.