8 ms·

Dude, is my code constant time? (2016)

GrumpyNl 5y ago
The site doesnt load.
- srcreigh 5y ago
  The HTML loads for me, but most of the images don't.
  - kevincox 5y ago
    A lot of the images are returning a 500 with "could not find oscar/assets/{name}.png in your content namespace".
Waterluvian 5y ago
I haven’t followed this stuff but I was loosely aware of the concept of a timing attack. I had no idea they were actually successfully employed.
- not2b 5y ago
  Yes, for this reason crypto algorithms usually avoid using any conditional branches at all. Then you have to worry about whether any of your assembly operations have data-dependent timing.
gnulinux 5y ago
From the linked github code: /* Intel actually recommends calling CPUID to serialize the execution flow and reduce variance in measurement due to out-of-order execution. We don't do that here yet. see §3.2.1 http://www.intel.com/content/www/us/en/embedded/training/ia-32-ia-64-benchmark-code-execution-paper.html */ static int64_t cpucycles(void) { unsigned int hi, lo; __asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi)); return ((int64_t)lo) | (((int64_t)hi) << 32); } Where `cpucycles` returns the number of CPU cycles since its reset (as 64 bit integer). [1] Seems really useful for benchmarking! Note that this code was last updated Oct 2020 and there is a note on top. Also reading about this instruction, sounds like it doesn't work in hyperthreaded CPUs? I was wondering if anyone knows an even more accurate (?) version of this code? Possibly by conforming to Intel's suggestion (or not)? Author in the article claims: > (The code calls the RDTSC instruction to get accurate cycle-level timing measurements.) This implies the above `cpucycles` is more accurate than using high resolution clocks. Is this still accurate in multicore or hyperthreaded CPUs? if not does this mean dudect doesn't work as accurately in such systems? Really curious about this, if anyone can point me to more code I'll be very happy! [1] https://en.wikipedia.org/wiki/Time_Stamp_Counter https://en.wikipedia.org/wiki/Time_Stamp_Counter
- x-shadowban 5y ago
  I wrote a similar program the other week, one rdtsc immediately followed by another. (read2 - read1) was about 50 cycles. I was surprised that it wasn't like 1 or 2. I have no idea what this implies.
  - gpderetta 5y ago
    Did you use RDTSC or RDTSCP?
- toast0 5y ago
  TSC cycles likely have more precision than any other clocks on a modern computer. They are also low cost to read. Early systems with TSC and multiple processors (or possibly multiple cores) either didn't synchronize the TSCs or may have done a poor job. If you've got a cpu that reports constant TSC, the rate is declared to not change when the cpu clock is modulated, but it may pause in some low power states. If the cpu reports invariant TSC, it should continue running in all cpu states other than power off. Anything new enough to have invariant tsc probably has at least all the cores in a single socket properly synchronized. Multi-socket you'd need to read docs or kernel code to know what's specified. OSes often prefer tsc timekeeping, if available, so they've got rules by hardware generation and tests to run when it's not clear. There's some cases where the OS attempts to synchronize the TSCs as well (such as CPU hotplug or startup firmware didn't sync), but they only stay in sync if the clock source for the counter is the same or at least linked. Hope this helps you find more info.
  - Narishma 5y ago
    I'm confused, aren't 'constant' and 'invariant' the same thing?
    - Hello71 5y ago
      constant means the speed doesn't change with cpu frequency, invariant means the speed doesn't change with power saving. https://www.chromium.org/chromium-os/how-tos-and-troubleshooting/tsc-resynchronization https://www.chromium.org/chromium-os/how-tos-and-troubleshoo...
gyulai 5y ago
- wiml 5y ago
  A hundred years ago it was mildly derogatory, but I don't think I've met someone who was offended by "dude" unless it was affront at the extreme informality of the word. (Maybe that's too fine of a distinction to make.)
Zababa 5y ago
Concretly, how often do security breaches happen due to timing attack? I can't grasp how severe this things are.
- otabdeveloper4 5y ago
  Probably 0.00001% of the cases. The other 99.9999% is when somebody forgot to change a password after an employee left.
- extrapickles 5y ago
  The current record[0] in exploiting a timing difference is on the order of 100ns over the Internet. You can do much better if you can get your attack to execute on the same CPU as the victim (eg: the cheaper cloud servers you typically share the cpu with others). I don’t think it’s a popular way in as there are easier and less noisy vulnerabilities to exploit (misconfigurations, protocol errors, etc). [0]: https://www.usenix.org/conference/usenixsecurity20/presentation/van-goethem https://www.usenix.org/conference/usenixsecurity20/presentat...
captainmuon 5y ago
I wonder if there isn't just a simple way to make timing attacks impossible. Find out the longest possible runtime, add some overhead, and then do the encryption in a different thread or process. Then call back after a constant time. It seems like this should be a primitive that is used a lot.
- mannykannot 5y ago
  Off the top of my head, I wonder if an attacker could probe whether the encryption thread had completed the task, and was merely waiting, by submitting other tasks to the system and timing them. Maybe some sort of busywork to run down the clock would help.

The site doesnt load.

srcreigh 5y ago
The HTML loads for me, but most of the images don't.
- kevincox 5y ago
  A lot of the images are returning a 500 with "could not find oscar/assets/{name}.png in your content namespace".

I haven’t followed this stuff but I was loosely aware of the concept of a timing attack. I had no idea they were actually successfully employed.

not2b 5y ago
Yes, for this reason crypto algorithms usually avoid using any conditional branches at all. Then you have to worry about whether any of your assembly operations have data-dependent timing.

gnulinux 5y ago

From the linked github code: /* Intel actually recommends calling CPUID to serialize the execution flow and reduce variance in measurement due to out-of-order execution. We don't do that here yet. see §3.2.1 http://www.intel.com/content/www/us/en/embedded/training/ia-32-ia-64-benchmark-code-execution-paper.html */ static int64_t cpucycles(void) { unsigned int hi, lo; __asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi)); return ((int64_t)lo) | (((int64_t)hi) << 32); } Where `cpucycles` returns the number of CPU cycles since its reset (as 64 bit integer). [1] Seems really useful for benchmarking! Note that this code was last updated Oct 2020 and there is a note on top. Also reading about this instruction, sounds like it doesn't work in hyperthreaded CPUs? I was wondering if anyone knows an even more accurate (?) version of this code? Possibly by conforming to Intel's suggestion (or not)? Author in the article claims: > (The code calls the RDTSC instruction to get accurate cycle-level timing measurements.) This implies the above `cpucycles` is more accurate than using high resolution clocks. Is this still accurate in multicore or hyperthreaded CPUs? if not does this mean dudect doesn't work as accurately in such systems? Really curious about this, if anyone can point me to more code I'll be very happy! [1] https://en.wikipedia.org/wiki/Time_Stamp_Counter https://en.wikipedia.org/wiki/Time_Stamp_Counter

x-shadowban 5y ago
I wrote a similar program the other week, one rdtsc immediately followed by another. (read2 - read1) was about 50 cycles. I was surprised that it wasn't like 1 or 2. I have no idea what this implies.
- gpderetta 5y ago
  Did you use RDTSC or RDTSCP?
toast0 5y ago
TSC cycles likely have more precision than any other clocks on a modern computer. They are also low cost to read. Early systems with TSC and multiple processors (or possibly multiple cores) either didn't synchronize the TSCs or may have done a poor job. If you've got a cpu that reports constant TSC, the rate is declared to not change when the cpu clock is modulated, but it may pause in some low power states. If the cpu reports invariant TSC, it should continue running in all cpu states other than power off. Anything new enough to have invariant tsc probably has at least all the cores in a single socket properly synchronized. Multi-socket you'd need to read docs or kernel code to know what's specified. OSes often prefer tsc timekeeping, if available, so they've got rules by hardware generation and tests to run when it's not clear. There's some cases where the OS attempts to synchronize the TSCs as well (such as CPU hotplug or startup firmware didn't sync), but they only stay in sync if the clock source for the counter is the same or at least linked. Hope this helps you find more info.
- Narishma 5y ago
  I'm confused, aren't 'constant' and 'invariant' the same thing?
  - Hello71 5y ago
    constant means the speed doesn't change with cpu frequency, invariant means the speed doesn't change with power saving. https://www.chromium.org/chromium-os/how-tos-and-troubleshooting/tsc-resynchronization https://www.chromium.org/chromium-os/how-tos-and-troubleshoo...

gyulai 5y ago

wiml 5y ago
A hundred years ago it was mildly derogatory, but I don't think I've met someone who was offended by "dude" unless it was affront at the extreme informality of the word. (Maybe that's too fine of a distinction to make.)

Zababa 5y ago

Concretly, how often do security breaches happen due to timing attack? I can't grasp how severe this things are.

otabdeveloper4 5y ago
Probably 0.00001% of the cases. The other 99.9999% is when somebody forgot to change a password after an employee left.
extrapickles 5y ago
The current record[0] in exploiting a timing difference is on the order of 100ns over the Internet. You can do much better if you can get your attack to execute on the same CPU as the victim (eg: the cheaper cloud servers you typically share the cpu with others). I don’t think it’s a popular way in as there are easier and less noisy vulnerabilities to exploit (misconfigurations, protocol errors, etc). [0]: https://www.usenix.org/conference/usenixsecurity20/presentation/van-goethem https://www.usenix.org/conference/usenixsecurity20/presentat...

captainmuon 5y ago

I wonder if there isn't just a simple way to make timing attacks impossible. Find out the longest possible runtime, add some overhead, and then do the encryption in a different thread or process. Then call back after a constant time. It seems like this should be a primitive that is used a lot.

mannykannot 5y ago
Off the top of my head, I wonder if an attacker could probe whether the encryption thread had completed the task, and was merely waiting, by submitting other tasks to the system and timing them. Maybe some sort of busywork to run down the clock would help.