Comment by zbentley
16 days ago
Eh, I don't think you need to get that extreme.
A combination of careful use of a given high-level-language with expert awareness of compiler behavior, and the presence of tests that detect some of the nasty timing behaviors that get compiled in via static analysis of compiler IR or assembly on selected platforms will get you pretty far--not guaranteed perfect like handwritten asm would, but far enough that the advantages of not needing maintainers to be fluent in assembly past the point of maintaining those tests might outweigh the drawbacks.
Validating that your compiler didn’t introduce a timing side channel into a crypto algo is harder than validating that the crypto algo has no memory safety bugs.
I think this is true for crypto algos because they have low cyclomatic complexity and you’re going to think deeply about its behavior anyway as part of cryptanalysis, benchmarking, and other testing
> Validating that your compiler didn’t introduce a timing side channel into a crypto algo is harder than validating that the crypto algo has no memory safety bugs.
Genuine question from a novice in this area: assuming that your critical crypto operations are, at the assembly level, in identifiable labeled blocks, why is this hard?
My understanding of timing attacks is that most of them derive from code that uses a looping construct such that performance is O(length(data)), and that most mitigations involve either replacing loops with constant-time instructions, or padding loops out to be fixed-iteration-count (in which case, they can/should hopefully be unrolled).
If that's true, wouldn't it be easy to identify whether a specific, user-selected critical section of compiled/assembly-output code was vulnerable to a side channel by checking it for nonterminal jumps (or generating a very simple/shallow-depth CFG and checking for cycles)?
Even if that's possible, I know it's definitely not sufficient for timing attack protection (awareness of specific instructions' performance and instructions whose performance are affected by other code are just a few examples of where this breaks down); I'm just wondering if it's a means of checking some timing-attack low hanging fruit in an easy way at compile time or (assuming simple disassembly is possible and critical sections can still be identified from machine code) startup time.
I very much do not want to sound like I'm proposing a solution from first principles here; I'm a total novice and this is a very deep area. I'm quite certain the answer is somewhere on the spectrum between "this doesn't work for $reasons" and "this is already well-known and practiced in sanitizer passes/serious cryptography libs". I'm just curious about the approach.
> assuming that your critical crypto operations are, at the assembly level, in identifiable labeled blocks, why is this hard?
The compiler won't do you that kind of favor. The crypto code will be smeared in with other junk, reordered according to the compiler's inscrutable whims.
Worse, exactly what kind of nonsense the compiler will do to your algo will depend on compiler version, ABI, OS, and countless spooky-action-at-a-distance properties of your larger project. Like, you could breathe on a non-crypto part of your code, and for complex reasons the compiler now emits different instructions for your crypto. This means that you'll have to revalidate what the compiler output every time you make any change to your code, even if that change doesn't affect the crypto kernels themselves.
> My understanding of timing attacks is that most of them derive from code that uses a looping construct such that performance is O(length(data))
That's not the big risk. The risk is that the compiler does one of the following:
- Introduces a branch on secret data for the purpose of speculation. There's nothing stopping a compiler from doing this. There are many optimizations in LLVM today that will do this (or not) based on heuristics. The moment this happens, you get a timing leak. Note that the branch isn't for a loop - it's the compiler saying "if this value is like this then I can short-circuit the calculation somehow"
- Turns math into a lookup table. This is less common, but again, there's nothing stopping the compiler from doing it. Again, that's a timing leak.
> If that's true, wouldn't it be easy to identify whether a specific, user-selected critical section of compiled/assembly-output code was vulnerable to a side channel by checking it for nonterminal jumps (or generating a very simple/shallow-depth CFG and checking for cycles)?
Theoretically, but first you'd have to decompile the assembly to work out which parts of it are even part of the crypto.
Here's a good way to think about it: writing assembly by hand is way easier than analyzing the assembly generated by a compiler. And, if you write it by hand, you only have to validate it if you make changes to that assembly, not anytime you breathed on the compiler or its inputs.