Dude, is my code constant time? (2016) | Hacker News Reader

Dude, is my code constant time? (2016)

reparaz.net

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

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.

I'm confused, aren't 'constant' and 'invariant' the same thing?

Linguistically yes, but the spec for constant wasn't constant enough, and so they came up with another word for constant rather than constanter or constantv2

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

As a minor but relevant nit, it's very strange that the C code you're quoting uses int64_t as the type for the timestamp.

The Intel code in the linked paper does not, it uses uint64_t but that was somehow changed when the code was transcribed. Also the clobbers mentioned in the paper are missing, which is suspicious.

The paper has a lot of analysis and includes better implementations, using cpuid and/or the rdtscp instruction.

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.

Did you use RDTSC or RDTSCP?

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.

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.

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.

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.

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

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

Probably 0.00001% of the cases.

The other 99.9999% is when somebody forgot to change a password after an employee left.

The site doesnt load.

The HTML loads for me, but most of the images don't.

A lot of the images are returning a 500 with "could not find oscar/assets/{name}.png in your content namespace".

Reply on news.ycombinator.com