Comment by Taek
5 days ago
Hold on I have to go edit the rest of my responses because I just assumed you wrote the code correctly; you did not.
You are not hashing between calls to the timer. The sha256 hash itself is responsible for doing physical things to the chip (heating up some parts unevenly during the hashing computation) which introduces meaningful entropy between calls to the current time.
You can't just do calls to clock_gettime(), you have do an actual sequential sha256() call between them. Please run this code again and tell me what results you get.
You're missing the point, which is that although timings may vary on the system you are testing on, there is no system guarantee from hardware _or_ software that this always happens.
Case in point:
> The sha256 hash itself is responsible for doing physical things to the chip (heating up some parts unevenly during the hashing computation)
Some CPUs do thermal throttling, others run at a fixed frequency or are so underclocked that thermal throttling doesn't kick in during your 50 iterations. This is exactly the source of randomness that is just not guaranteed to exist across systems.
-----
> You can't just do calls to clock_gettime(), you have do an actual sequential sha256() call between them. Please run this code again and tell me what results you get.
OK, I'll humor you, but to reiterate: it isn't really my point.
After adding hashing in the loop:
Here it's mostly the first few iterations that are slow, the remaining ones are both fast and surprisingly consistent (the value 289 appears six times for example).
It's more obvious if you run it a few times in a row:
The loop timings are quite consistent at least on a single system. That's a problem if an attacker is able to run the same program on the same system to establish baseline timings.
If I estimate the entropy as the logarithm of the difference between maximum and minimum I get only 146 bits of entropy in this case. Technically above your standard of 128 bit, but my point was: nothing guarantees you get even this much entropy on a less noisy system.
This also shows the problem with your "just run more iterations" advice: in the above sample, the first five columns provide 24 bit of entropy per column, and the remaing 45 columns only 2.6 bits. So adding more iterations at the tail end wouldn't double the entropy obtained.
The code I used is here: https://pastebin.com/ZrL1UDEg
The reason that you get 3-4 bits of entropy per hash is because of the fundamental nature of CPUs. In addition to having considerable professional experience with cryptography, I also have considerable professional experience with hardware; hardware is fickle as hell, especially when your transistors are tens of nanometers large. Every time you flip a bit, you expend some energy, which heats up the chip, and the heat changes the timing of the next clock cycle. Chips are composed of literally billions of transistors, and each one is going to have a different temperature, because clock cycles last less than a nanosecond (well, embedded hardware is slower but the same idea still applies reliably) and that's not enough time for temperature deltas to dissipate across the chip.
Hashing is particularly chaotic because it lights up a different set of transistors on each clock cycle, which means the hotspots on the chip are being jerked around. Some transistors are going to light up 5-10 times in a row, and others are going to be idle 5-10 times in a row, and then randomly that changes. And all of this changes the number of picoseconds that it takes for a clock cycle to complete, which means that each clock cycle is genuinely going to take a different amount of time to complete, and stuff like temperature throttling is completely not at play whatsoever, because we're not talking about chip-wide temperatures, we're literally talking about temperature deltas between transistor a and transistor b.
That makes it a really wonderful source of entropy for cryptographic applications, because the CPU clock is so critical that it's almost never buggy (especially relative to other components that provide entropy), it's also almost impossible to manipulate reliably by an attacker (unless the attacker has an exploit that allows them to set the value of the clock directly - which is possible, but it's a very narrow surface area relative to other entropy sources), and you can completely take advantage of this entropy entirely in userspace, which once again heavily minimizes attack surface area and exposure to bugs.
I have searched far and wide for a CPU that does not reliably generate entropy using the iterated-hashing-against-the-clock method, and I have not found a single example of a CPU that consistently takes the same amount of time to complete a hash. And the reason isn't implementation, the physics of CPUs simply insist on introducing entropy when trying to repeatedly hash something quickly.