News for hackers. Stuff that matters.
Re:Clang vs. Clang by duped on Saturday August 03, 2024 @03:50PM (#41148792)
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.

Re:Clang vs. Clang by gabrielhidasy on Saturday August 03, 2024 @07:54PM (#41150162)
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"
Re:Clang vs. Clang by Dylan16807 on Saturday August 03, 2024 @08:02PM (#41150191)
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.
Re:Clang vs. Clang by g15jv2dp on Saturday August 03, 2024 @08:11PM (#41150224)
There's no reason that C should be suitable for every purpose under the sun.
Re:Clang vs. Clang by Dylan16807 on Saturday August 03, 2024 @08:25PM (#41150264)
Fiddling some bits cross-platform is supposed to be one of them.
Re:Clang vs. Clang by zdragnar on Saturday August 03, 2024 @09:09PM (#41150447)
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).
Re:Clang vs. Clang by Dylan16807 on Saturday August 03, 2024 @09:13PM (#41150462)
It's not in the spec right now but it still feels solidly in C's wheelhouse to me.
Re:Clang vs. Clang by viraptor on Saturday August 03, 2024 @09:54PM (#41150647)
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.

Re:Clang vs. Clang by uecker on Sunday August 04, 2024 @04:09AM (#41151890)
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.

Re:Clang vs. Clang by PhilipRoman on Sunday August 04, 2024 @04:19AM (#41151934)
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.
Re:Clang vs. Clang by NohatCoder on Sunday August 04, 2024 @04:51AM (#41152044)
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.
Re:Clang vs. Clang by account42 on Monday August 05, 2024 @08:15AM (#41160576)
Not when the precise timing of operations matters.
Re:Clang vs. Clang by tialaramex on Saturday August 03, 2024 @08:12PM (#41150228)
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.

Re:Clang vs. Clang by eschneider on Sunday August 04, 2024 @11:33AM (#41154178)
> 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.

Re:Clang vs. Clang by pjmlp on Sunday August 04, 2024 @11:56AM (#41154327)
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.

Re:Clang vs. Clang by eschneider on Sunday August 04, 2024 @02:34PM (#41155415)
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.
Re:Clang vs. Clang by rbanffy on Monday August 05, 2024 @05:15AM (#41159417)
I find it rather easy as long as you don’t have to interact with the OS. That’s where it becomes messy, with inflexible data structures and convoluted arguments in ABIs designed to be used from higher level languages.

If you are doing really low level stuff, sometimes it’s worth rolling out your own little RTOS with just the bits and pieces you need.

Not that long ago, I realised most 8-bit (and MS-DOS) computer games had their own RTOS woven into the game code, with multi-tasking, hardware management, IO, and so on.

Re:Clang vs. Clang by eschneider on Monday August 05, 2024 @09:51AM (#41161385)
Yeah...Old 8-bit computers didn't exactly have any OS services. :)
Re:Clang vs. Clang by rbanffy on Monday August 05, 2024 @10:06AM (#41161486)
Some very minimal things such as reading or writing to disk or files, reading the keyboard, or other very simple activities
Re:Clang vs. Clang by pclmulqdq on Sunday August 04, 2024 @02:24PM (#41155373)
Most architectures have a subset of their instructions that can be called in constant time (constant time meaning data-independent time). Things like non-constant pointer loads and branches are obviously out, and so are div/mod in almost all chips, but other arithmetic and conditional moves are in that set.

CPUs are actually much better at making those guarantees than compilers are.

Re:Clang vs. Clang by rbanffy on Monday August 05, 2024 @04:30AM (#41159191)
If you tell the compiler, it can generate code with only those instructions.
Re:Clang vs. Clang by ynik on Monday August 05, 2024 @05:56AM (#41159626)
That's no longer true: https://www.intel.com/content/www/us/en/developer/articles/t... x86 hardware does not guarantee anything unless you enable "Data Operand Independent Timing Mode", which is disabled by default and AFAIK can only be enabled by kernel-level code. So unless operating systems grow new syscalls to enable this mode, you're just out of luck on modern hardware.
Re:Clang vs. Clang by pclmulqdq on Monday August 05, 2024 @06:30AM (#41159795)
In the most purely theoretical sense, you are correct, but everything Intel and AMD has said indicates they will still offer strong guarantees on the DOIT instructions:

https://lore.kernel.org/all/851920c5-31c9-ddd9-3e2d-57d379aa...

In other words, they have announced the possibility of breaking that guarantee years before touching it, which is something the clang developers would never do.

Re:Clang vs. Clang by kragen on Thursday August 15, 2024 @04:42PM (#41260147)
not only does it mention that, the author also implemented that language, jasmin, with some collaborators. he does mention that, but he doesn't mention that he'd already done it previously, the unreleased qhasm
Re:Clang vs. Clang by einpoklum on Thursday August 15, 2024 @06:40PM (#41261215)
> what you actually meant, which in this case is "Perform this constant time operation".

This notion is not expressible in most (or almost all) high-level programming languages. Or, to put it another way: If you wrote C or C++ you never mean to say "perform this guaranteed-constant-time CPU operation" (ignoring asm instructions and hardware-aware builtins).

Re:Clang vs. Clang by topspin on Saturday August 03, 2024 @10:36PM (#41150799)
> 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.

Re:Clang vs. Clang by dataflow on Sunday August 04, 2024 @02:15AM (#41151451)
> 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.

Re:Clang vs. Clang by quietbritishjim on Sunday August 04, 2024 @04:17AM (#41151925)
The difference is that threads have enormously wider applicability than timing preservation does.
Re:Clang vs. Clang by dataflow on Monday August 05, 2024 @05:55PM (#41165984)
That is orthogonal to whether compiler development would grind to a halt though, was my point.
Re:Clang vs. Clang by uecker on Sunday August 04, 2024 @04:05AM (#41151874)
It is completely unreasonable though to assume that a compiler should now preserve some assumed (!) timing of source operations.

It would be reasonable to implement (and later standardize) a pragma or something that specifies timings constraint for a subset of the language. But somebody would need to do the work.

Re:Clang vs. Clang by mst on Sunday August 04, 2024 @06:41AM (#41152583)
An attribute for functions that says "no optimisations may be applied to the body that would change timings" seems like a reasonable level of granularity here, and if you were conservative about which optimisations it allowed in version zero it'd probably not be a vast amount of work.

I'm sort of reminded of the software people vs. hardware people stuff in embedded work, where ideally you'd have people around who'd crossed over from one to another but (comparing to crypto authors and compiler authors) there's enough of a cultural disconnect between the two groups that it doesn't happen as often as one might prefer.

Re:Clang vs. Clang by saalweachter on Sunday August 04, 2024 @09:02AM (#41153249)
Why not just specify "all branches of this code must execute in the same amount of time", and let the compiler figure it out for the architecture being compiled for?
Re:Clang vs. Clang by davrosthedalek on Sunday August 04, 2024 @10:56AM (#41153943)
Instruction duration isn't constant even within the same arch. You cannot have branches in constant-time code.

I do wonder though how often cpu instructions have data-dependent execution times....

Re:Clang vs. Clang by davrosthedalek on Sunday August 04, 2024 @05:57PM (#41156600)
(Correction: You cannot have data-dependent branches. You can of course have branches to make a fixed-iterations for loop, for example)
Re:Clang vs. Clang by komon on Sunday August 04, 2024 @03:25AM (#41151715)
> Is there some reason a cryptographic algorithm developer must track the latest release of a compiler?

Tracking the latest release is important because:

1. Distributions build (most? all?) libraries from source, using compilers and flags the algorithm authors can't control

2. Today's latest release is the base of tomorrow's LTS.

If the people who know most about these algorithms aren't tracking the latest compiler releases, then who else would be qualified to detect these issues before a compiler version bearing a problematic optimization is used for the next release of Debian or RHEL?

> Logically, therefore, must we not also expect CPU designers to also forego changes that could alter timing behavior?

Maybe? [1]

> freezing all compiler development

There are many, many interesting areas of compiler development beyond incremental application of increasingly niche optimizations.

For instance, greater ability to demarcate code that is intended to be constant time. Or test suites that can detect when optimizations pose a threat to certain algorithms or implementations. Or optimizing the performance of the compiler itself.

Overall I agree with you somewhat. All engineers must constantly rail against entropy, and we are doomed to fail. But DJB is probably correct that a well-reasoned rant aimed at the community that both most desires and most produces the problematic optimizations has a better chance at changing the tide of opinion and shifting the rate at which all must diminish than yelling at chipmakers or the laws of thermodynamics.

[1]https://en.m.wikipedia.org/wiki/Spectre_(security_vulnerabil...

Re:Clang vs. Clang by thesz on Sunday August 04, 2024 @03:58AM (#41151846)
> short of regressing to in-order, non-speculative cores

I guess you are referring to a GPU cores here.

It is a joke but can hint that in-order non-speculative cores are powerful computers nonetheless.

Re:Clang vs. Clang by SkiFire13 on Sunday August 04, 2024 @05:30AM (#41152218)
They are a totally different kind of powerful computer though, you can't compare them for sequential workloads.
Re:Clang vs. Clang by topspin on Monday August 05, 2024 @12:29PM (#41162824)
You make a fine point. If you follow this regression to its limit you're going to end up doing your cryptography on a MCU core with a separate, controlled tool chain. TPM hardware has been a thing for a while as well. Also, HSMs.

This seems a lot more sane than trying to retrofit these concerns onto the entire stack of general purpose hardware and software.

Re:Clang vs. Clang by NohatCoder on Sunday August 04, 2024 @05:05AM (#41152109)
We had ~30 years of "undefined behaviour" practically meaning "do whatever the CPU does". It is not new that people want predictable behaviour, it simply wasn't a talking point as we already had it.
Re:Clang vs. Clang by GTP on Sunday August 04, 2024 @06:14AM (#41152439)
It's not even that. Yes, in case of signed intger overflow, usually yoj get whatever the CPU gives as answer for the sum. But you also have the famous case of an if branch checking for a null pointer being optimized away. And even in the case of integer overflow, the way to correctly check for it isn't intuitive at first, because you need to check for integer overflow without the check itsef falling under UB.

EDIT: just to make my point clear: the problem with UB isn't just that it exists, it is also that compiler optimizations make it hard to check for it.

Re:Clang vs. Clang by atiedebee on Tuesday August 06, 2024 @12:23PM (#41172356)
When do NULL checks get optimised away, apart from the case where the pointer has already been accessed/is known at compile time to be invalid?
Re:Clang vs. Clang by GTP on Wednesday August 07, 2024 @04:43AM (#41179444)
I couldn't find again the example I saw many years ago, I could only find a GCC bug that has been fixed now. So you're likely right and I just didn't remember correctly. But we still can have the zeroing out of memory before deallocation that can get silently optimized away. Maybe also naive attempts at checking for signed integer overflow could be silently optimized away. My general point is that, if the compiler determines that the code has dead instructions/unneded checks, it is very likely that the programmer's mental model of the code is wrong. So, just like the case of using an integer as a pointer or vice versa, we should have a warning telling the programmers that some code is going to not be compiled. Also in the case of the null pointer check: this would make the programmer realize that the check is happening too late and should instead be performed earlier
Re:Clang vs. Clang by adrianN on Sunday August 04, 2024 @06:19AM (#41152469)
When were those decades? Any decent optimizing compiler built in the last couple of decades exploits undefined behavior.
Re:Clang vs. Clang by NohatCoder on Sunday August 04, 2024 @06:58AM (#41152670)
You pretty much answered your own question. ~20 years ago and back. But I think it is also worth pointing out that it has gotten worse, those 20 years has been a steady trickle of new foot guns.
Re:Clang vs. Clang by pjmlp on Sunday August 04, 2024 @12:03PM (#41154373)
We have ill defined behaviour, implementation defined behaviour, erroneous behaviour, unspecified behaviour, undefined behaviour.

Undefined behaviour isn't exactly what most people think it is.

Re:Clang vs. Clang by klyrs on Sunday August 04, 2024 @11:22AM (#41154114)
The author is somewhat known for his over-the-top rants. When you read his writing in the context of a 90's flamewar, you'll find them to be quite moderate and reasonable. But it comes from a good place; he's a perfectionist, and he merely expects perfection from the rest of us as well.
Re:Clang vs. Clang by jeanlucas on Sunday August 04, 2024 @11:41AM (#41154242)
> he's a perfectionist, and he merely expects perfection from the rest of us as well.

Nicely put, but at the end perfectionism is a flaw.

Re:Clang vs. Clang by himinlomax on Sunday August 04, 2024 @11:49AM (#41154288)
Not when computer security is concerned.
Re:Clang vs. Clang by klyrs on Sunday August 04, 2024 @12:39PM (#41154652)
In all things, moderation. Security must be evaluated as a collection of tradeoffs -- privacy, usability, efficiency, etc. must be considered.

For example, you might suspect that the NSA has a better sieve than the public, and conclude that your RSA key needs to be a full terabyte*. We know that this isn't perfect, of course, but going much beyond that key length will prevent your recipient from decrypting the message in their lifetime.

* runtime estimates were not performed to arrive at this large and largely irrelevant number

Re:Clang vs. Clang by saagarjha on Sunday August 04, 2024 @01:13PM (#41154919)
Security is a tradeoff. Perfect security is not using a computer.
Re:Clang vs. Clang by jeanlucas on Thursday August 08, 2024 @12:55PM (#41193653)
Security is a constant tradeoff, and trading off time for perfectionism is not a good one to take.
Re:Clang vs. Clang by duped on Sunday August 04, 2024 @12:33PM (#41154594)
> This all looks like an engineering purity spiral.

To get philosophical for a second, all of engineering is analyzing problems and synthesizing solutions. When faced with impossible problems or infinite solution space, we must constrain the problem domain and search space to find solutions that are physically and economically realizable.

That's why the answer to every one of your questions is, "it depends."

But at the top, yes, it's unreasonable. The C standard specifies the observable behavior of software in C. It does not (and cannot) specify the observable behavior of the hardware that evaluates that software. Since these behavior are architecture and application specific, it falls to other tools for the engineer to find solutions.

Simply put, it isn't the job of the C standard to solve these problems. C is not a specification of how a digital circuit evaluates object code. It is a specification of how a higher level language translates into that object code.

Re:Clang vs. Clang by n_plus_1_acc on Sunday August 04, 2024 @06:10AM (#41152406)
The optimizations are valid because the C standard and the semantics of its abstract machine don't have a concept of timing.