Comment by pizlonator | Hacker News Reader

Comment by pizlonator | Hacker News Reader

This article references the fact that security issues in crypto libs are memory safety issues, and I think this is meant to be a motivator for writing the crypto using SIMD intrinsics.

This misses two key issues.

1. If you want to really trust that your crypto code has no timing side channels, then you've gotta write it in assembly. Otherwise, you're at the compiler's whims to turn code that seems like it really should be constant-time into code that isn't. There's no thorough mechanism in compilers like LLVM to prevent this from happening.

2. If you look at the CVEs in OpenSSL, they are generally in the C code, not the assembly code. If you look at OpenSSL CVEs going back to the beginning of 2023, there is not a single vulnerability in Linux/X86_64 assembly. There are some in the Windows port of the X86_64 assembly (because Windows has a different calling conv and the perlasm mishandled it). There are some on other arches. But almost all of the CVEs are in C, not asm.

If you want to know a lot more about how I think about this, see https://fil-c.org/constant_time_crypto

I do think it's a good idea to have crypto libraries implemented in memory safe languages, and that may mean writing them in Rust. But the actual kernels that do the cryptographic computations that involve secrets should be written in asm for maximum security so that you can be sure that sidechannels are avoided and because empirically, the memory safety bugs are not in that asm code.

So there are more bugs in a more readable and understandable programming language (C) as opposed to asm? What gives? I am asking because intuition would say the opposite since asm is much more lower-level than C.

compiler optimization is a blackbox. shortcuts to crypto routines will allow side channel attacks

The core primitives written in assembly operate on fixed sized blocks of data; no allocations, no indexing arrays based on raw user controlled inputs, etc. Moreover, the nature of the algorithms--at least the parts written in assembly, e.g. block transforms--means any bugs tend to result in complete garbage and are caught early during development.

Crypto primitives tend to have very simple control flow (those that don’t are usually insecure) and even simpler data structures. You won’t find many branches beyond “is there another block?” in a typical block cipher or hash, for example.

In OpenSSL, the C code is doing stuff that is hard to validate exhaustively like dealing with wire protocols, different sized buffers that have to be handled in special ways, dynamic memory allocation, etc

The assembly code is for the kernels themselves. Usually it’s a loop with easy to understand bounds, usually zero pointer chasing. Mostly math. Definitely no calls to malloc/free

So it’s not that assembly has an advantage over C. It’s that the kinds of things that get written in assembly also happen to:

- Be the sort of code where accidentally overflowing a buffer is unlikely because the indexing is the easy part. And there’s no interesting downcasting or allocation happening

- Be the sort of code where timing side channels are disastrous and the only way to know for sure you don’t have one is to look at the assembly

Is it actually more readable and understandable (not to be confused with more familiar), though? It is hard to beat the understandability of the lowest level. Abstractions add unknowns. C's claim to fame was being a "portable assembler"; freeing developers from having to write the same program over and over and over for different systems.

I can't review assembly, agreed on better language part but we'd need tooling to help prove it's correctness of you want the asm path.

Well, is it that you can't or that you won't? All you need to do is learn it, you know? The full x86 ISA for one is quite nasty, but there's a useful subset, and other architectures are much nicer in general. Asm is as basic as it gets.

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.

Reply on news.ycombinator.com