4 ms·

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

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.

mhh__ 4y ago
It can be done if you insert data dependencies everywhere and know which CPU it's running on.
mysterydip 4y ago
It should be possible on microcontrollers at least. I don't believe most have a cache.
- AlotOfReading 4y ago
  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.
  - whatshisface 4y ago
    The RPI2040 is enormous for a microcontroller. A typical microcontroller is something like an Arduino.
    - AlotOfReading 4y ago
      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".
      - kragen 4y ago
        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.
        AlotOfReading 4y ago
        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-place/ https://semiengineering.com/what-happened-to-execute-in-plac...
        kragen 4y ago
        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.
    - zokier 4y ago
      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
rdlw 4y ago
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.
- PeterisP 4y ago
  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.
dataflow 4y ago
> 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.
Someone 4y ago
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.
mek6800d2 4y ago
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-bit-loop-counter-with-64-bit-introduces-crazy-performance-deviati https://stackoverflow.com/questions/25078285/replacing-a-32-..."
djrenren 4y ago
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/AArch64-Registers/DIT--Data-Independent-Timing https://developer.arm.com/documentation/ddi0601/2020-12/AArc... [2]: https://www.intel.com/content/www/us/en/developer/articles/technical/software-security-guidance/best-practices/data-operand-independent-timing-isa-guidance.html https://www.intel.com/content/www/us/en/developer/articles/t...

mhh__ 4y ago

It can be done if you insert data dependencies everywhere and know which CPU it's running on.

mysterydip 4y ago

It should be possible on microcontrollers at least. I don't believe most have a cache.

AlotOfReading 4y ago
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.
- whatshisface 4y ago
  The RPI2040 is enormous for a microcontroller. A typical microcontroller is something like an Arduino.
  - AlotOfReading 4y ago
    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".
    - kragen 4y ago
      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.
      - AlotOfReading 4y ago
        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-place/ https://semiengineering.com/what-happened-to-execute-in-plac...
        kragen 4y ago
        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.
  - zokier 4y ago
    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

rdlw 4y ago

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.

PeterisP 4y ago
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.

dataflow 4y ago

> 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.

Someone 4y ago

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.

mek6800d2 4y ago

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-bit-loop-counter-with-64-bit-introduces-crazy-performance-deviati https://stackoverflow.com/questions/25078285/replacing-a-32-..."

djrenren 4y ago

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/AArch64-Registers/DIT--Data-Independent-Timing https://developer.arm.com/documentation/ddi0601/2020-12/AArc... [2]: https://www.intel.com/content/www/us/en/developer/articles/technical/software-security-guidance/best-practices/data-operand-independent-timing-isa-guidance.html https://www.intel.com/content/www/us/en/developer/articles/t...