News for hackers. Stuff that matters.
Re:FaCT: Constant Time Programming Language by pierrebai on Sunday October 23, 2022 @02:11PM (#33308937)
I do wonder if it is possible to truly be certain code runs in constant-time. The problem is that modern CPU translate their instruction set into internal micro-code. For example, the x86 CMOVE instruction (conditional move) could potentially become a branching path once translated to microcode. There are other instructions like multiplication or division that may end-up having different run time depending on input.
Re:FaCT: Constant Time Programming Language by mysterydip on Sunday October 23, 2022 @02:36PM (#33309107)
It should be possible on microcontrollers at least. I don't believe most have a cache.
Re:FaCT: Constant Time Programming Language by AlotOfReading on Sunday October 23, 2022 @03:05PM (#33309318)
It's increasingly rare to see a uC without some kind of memory hierarchy nowadays. Even a barebones rpi2040 uses what's effectively an SRAM cache in front of the flash. Unless you have compelling use case that isn't solved by disabling caching (which any chip can do) or region attributes, it's basically a free spec boost for manufacturers.

Regardless, you probably don't want to do your fast-path cryptography on the slowest coprocessors imaginable.

Re:FaCT: Constant Time Programming Language by whatshisface on Sunday October 23, 2022 @04:13PM (#33309859)
The RPI2040 is enormous for a microcontroller. A typical microcontroller is something like an Arduino.
Re:FaCT: Constant Time Programming Language by AlotOfReading on Sunday October 23, 2022 @04:52PM (#33310153)
The Cortex-M0 used in the rpi2040 is also used by Arduino. More broadly, both the SAM and the AVR32 families have some level of support for caching. Only the AVR8s don't. I think it's fair to describe 8 bit uCs as "increasingly rare".
Re:FaCT: Constant Time Programming Language by kragen on Monday October 24, 2022 @12:24AM (#33312923)
I think whatshisface means "ATMega328" when he says "Arduino".

I think there are more 8-bit μCs around than ever before, even though it's harder and harder to justify using one instead of a 32-bit μC. But lots of 32-bit μCs don't have caching either, or they have it to the extent of "you can run code from internal RAM, or more slowly from internal Flash, or much more slowly from QSPI-connected memory". But that doesn't introduce any nondeterminism into the timing, because your code has control over where it's running from.

Re:FaCT: Constant Time Programming Language by AlotOfReading on Monday October 24, 2022 @01:42AM (#33313286)
I imagine we all agree that the entire idea of running crypto code from a dog-slow uC executing from flash is silly, but to continue the hypothetical...

The way old processors used to do XIP with constant random access latency is pretty much dead at this point for new designs. Semiengineering did a good article on this awhile back [1]. Even if there weren't usually a lot of invisible caching in the middle, flash cells usually don't have identical access latencies (worse, they change with age/write cycles!), and the AVR conditonal branch has data-dependent timings besides. At the design side, there's also a lot of decisions like burst modes that can introduce timing variations that can change with minor design revisions. Most of these aren't documented or even well understood by manufacturers. Truly eliminating architectural timing side channels is very, very difficult today.

[1] https://semiengineering.com/what-happened-to-execute-in-plac...

Re:FaCT: Constant Time Programming Language by kragen on Monday October 24, 2022 @02:23AM (#33313511)
I don't think there's anything wrong with running crypto code from a dog-slow μC executing from Flash, except that sometimes you might prefer the Flash to be mask ROM.

This is a good article! I guess you're right that when you're running code loaded over a QSPI bus it's probably going to be cached unless you're using an old chip. So data processed by code loaded that way is subject to timing-channel leaks.

However, I think it's very unusual for embedded NOR memory in a μC to have detectable variable access latency. As the article says:

> As long as the operating frequency is slow enough that the flash access times can keep up, instructions can be fetched and executed directly out of the flash, otherwise known as executed in place. The original idea was that you didn’t need to buffer the instructions somewhere else before executing them. ¶ Embedded NOR memory is still alive and well, although today’s higher volumes are on nodes far from what would be considered leading-edge for logic.

So, on-chip Flash is probably still fine.

You probably don't want to try to make an AVR8 into an SSL accelerator, but there are plenty of applications where the ability to do crypto securely is valuable, even if it's very slow.

Re:FaCT: Constant Time Programming Language by AlotOfReading on Monday October 24, 2022 @02:50AM (#33313642)
On-chip flash would still be susceptible to whether the CPU uses burst accesses or other weird microarchitectural details. The former manifests as the 8th or 16th instruction having slightly higher real latency, for example. This sort of stuff is endless, which is why stuff like TFA that gets around the issue by simply removing the data dependencies before they ever get to the hardware is a better general approach if you're not going to do ASICs.
Re:FaCT: Constant Time Programming Language by kragen on Monday October 24, 2022 @02:39PM (#33320615)
Slightly higher real latency? Are you talking about asynchronous CPUs like the GreenArrays GA144? Or saying that if you're running off the internal RC oscillator the clock speed will vary because the supply voltage varies depending on memory access patterns? Or by "slightly higher real latency" do you mean that an instruction will take 2 clock cycles instead of 1 or 3 cycles instead of 2? I don't think any of those are true on things like the ATMega328 AVR8 mentioned above or the Padauk PMS150C. Maybe you mean something else?

Bitbanging protocols with tight timing requirements using cycle-accurate code is still a thing people routinely do on small microcontrollers, and it wouldn't work if instruction timing was as unpredictable as you're saying.

Nevertheless, I agree that removing data-dependent branches is a better way to close timing leaks.

Re:FaCT: Constant Time Programming Language by zokier on Sunday October 23, 2022 @05:12PM (#33310297)
Not really sure where you are getting your "typical" from, 32bit mcus dominate the market over old 8bitters like avrs in the arduino. And rpi2040 is not particularly enormous as far as ARM microcontrollers go, while it is dual-core the cores are tiny M0+ ones instead of bigger cores like M7 or M33
Re:FaCT: Constant Time Programming Language by mhh__ on Sunday October 23, 2022 @02:14PM (#33308954)
It can be done if you insert data dependencies everywhere and know which CPU it's running on.
Re:FaCT: Constant Time Programming Language by rdlw on Sunday October 23, 2022 @02:52PM (#33309212)
Yes, since every computer has finite memory.

If you bubble sort a list of bytes, say your algorithm runs in 10000+n^2 clock cycles. You have at most an exabyte of storage, so your code will run in at most 10^37 clock cycles! :p

As storage technology improves, of course the coefficient will increase, but at that point is should be considered a different algorithm. This one has undefined behaviour when you have more than an exabyte of storage.

Re:FaCT: Constant Time Programming Language by PeterisP on Sunday October 23, 2022 @04:01PM (#33309782)
This article has nothing to do with algorithm complexity and "constant time" big-O complexity class, this is about guarantees of code executing in absolutely constant time (i.e. exactly x clock cycles, not "at most") in an input-independent manner to ensure that execution time does not reveal any information about what the inputs/outputs were.

In essence, this is about a programming language that can ensure that execution time always equals the worst case; if there's branching, taking both branches and ignoring one of the results; if there's iteration, doing a constant maximum count of iterations no matter what the input data is, etc.

Re:FaCT: Constant Time Programming Language by dataflow on Sunday October 23, 2022 @03:45PM (#33309647)
> For example, the x86 CMOVE instruction (conditional move) could potentially become a branching path once translated to microcode.

Would you have any links to more reading on this and when it happens? It's the first time I've heard it.

Re:FaCT: Constant Time Programming Language by Someone on Sunday October 23, 2022 @04:23PM (#33309941)
If the language spec says a piece of code must execute in constant-time, any deviation is a compiler bug.

But yes, that may mean the language can’t be implemented well on lots of modern hardware.

A lot probably can be done by avoiding some instructions, flushing caches very often, clearing branch prediction history (if possible), etc.

That would not make the language win performance shootouts, though.

There also is the problem that not all cores may be equal and that quite a few modern CPUs drop speed ‘at will’, depending on system load, core temperature, etc.

Re:FaCT: Constant Time Programming Language by mek6800d2 on Sunday October 23, 2022 @04:23PM (#33309946)
No, I think. Much like your examples, I have in mind "False Data Dependencies" in the CPU. I came across this on StackOverflow several years ago. It is a long question and a long, informative thread about seemingly irrational performance differences: "https://stackoverflow.com/questions/25078285/replacing-a-32-..."
Re:FaCT: Constant Time Programming Language by djrenren on Sunday October 23, 2022 @04:52PM (#33310150)
Hey, one of the paper authors here, this has been a serious problem in the past (and present), but is definitely improving. For example, intel’s docs state that cmove is constant-time on recent hardware. ARM’s DIT (data-independent timing) [1] extension provides hardware-level guarantees and intel has extensive docs on how to use their chips for constant-time coding [2]

[1]: https://developer.arm.com/documentation/ddi0601/2020-12/AArc...

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