This is why I use, in security critical contents of my software (where the numbers have to be computationally infeasible to produce), a type of random number generator called an XOF (extendable-output function).
It takes entropy from multiple different sources, makes it all input to the XOF, then the XOF uses cryptography to output a stream that has as much entropy as the combined entropy of all of its sources of randomness. So if an XOF, for example, takes 100 runs of rdrand16, along with the system time in microseconds and the number of milliseconds between receiving 100 packets over the network, the XOF will output a completely random stream without artifacts like never returning 0x0000, even if rdrand16 never outputs 0x0000.
You can effectively achieve the same result with this simple operation:
hash = sha256(current_time());
for i := 0; i < n; i++ {
hash = sha256(hash.append(current_time()))
}
This is because the number of nanoseconds between hashes is actually itself variable, and this is true for physics reasons that are basically beyond the control of any attacker trying to manipulate your entropy. If your time() function has a resolution of nanoseconds, you only need your loop to iterate about 50 times to get a cryptographically secure amount of entropy. If your time() function has a resolution of milliseconds, you need to let this run for more like 20 milliseconds, and if your time() function has a resolution of seconds you need to let it run for more like 5 seconds.
The reason I like doing it this way is that it happens entirely in userspace, it's genuinely a secure method of generating entropy, and it has no dependencies on potentially buggy firmware or microcode outside of the time() call, which is both fairly narrow, fairly heavily used (meaning a bug is likely to be discovered during testing, as the implementation is likely heavily scrutinized), and also fairly easy to test independently - just look at the number of nanoseconds that elapse at each consecutive call to sha256(current_time()) and verify that there's some statistical variance. The above suggestions are assuming about 2.5 bits of variance between calls, meaning there should be a range of at least 20 nanoseconds between your slowest and fastest hash call. This has been true on every CPU I've ever measured, including microcontrollers.
This comment demonstrates everything that's wrong with people trying to be clever and rolling their own crypto.
The security of your system depends on time() providing enough entropy, even though that's not what it's designed to do. It's built on top of the wrong primitive from the start.
> The reason I like doing it this way is that it happens entirely in userspace
On Linux this is often true, but there is no portable way to get the current time that is _guaranteed_ not to do any system calls.
> If your time() function has a resolution of nanoseconds, you only need your loop to iterate about 50 times to get a cryptographically secure amount of entropy.
You haven't proven that at all. It's easy to imagine that on a CPU running at a fixed frequency the interval between reads is constant, so if anyone knows (or can guess) the start time the resulting seed is entirely predictable.
This is completely independent of timer resolution. You seem to realize that as you were writing that:
> just look at the number of nanoseconds that elapse at each consecutive call to sha256(current_time()) and verify that there's some statistical variance
Oh yes, because evaluating the quality of a random number generator is such a trivial thing to do, it's not like there is decades of research behind it or anything.
And assuming you are able to verify the statistical variance: are you going to put that logic in the loop, making it significantly more complex?
Or are you going to do this test on your machine and then ship your code on the assumption that if it works on your machine, it will work everywhere else, too?
> if your time() function has a resolution of seconds you need to let it run for more like 5 seconds.
So not only is it insecure, it's agonizingly slow by design. Why do a system call that takes milliseconds at best, when we can run a loop in userspace for 5 seconds?
All this just so you can avoid writing the obviously correct oneliner:
if (getentropy(&seed, sizeof(seed)) != 0) abort();
You don't need 256 bits of entropy, you only need 128.
I have tested this method on over 100 different CPUs and I have never seen such consistent output. I'm genuinely surprised to see that you only hit 92 bits of entropy, but that can trivially be fixed by doing 10x the iterations. 500 iterations is still going to put you under a millisecond of cost.
And, for what it's worth, code I've actually shipped has combined the above technique with Fortuna, and has typically targeted 2000 bits of entropy rather than 128 (for security buffer).
EDIT: I reviewed his code, and he's not hashing between calls to check the clock; the hash call itself causes the CPU to heat up in arbitrary ways which changes the timing between hashes and introduces more entropy; removing that call basically entirely defeats the idea behind the technique, these results are fully invalid.
---
I updated the code to insert the hash call, this is what I got for his original code on my machine, and the updated code with hashing on my machine (and the difference is cryptographically meaningful):
The increase in calculated entropy comes from the first iteration being slower than the rest, but that's a bit misleading, because the first call is always going to be slower.
Can you run the program 10 times and show me how much variance there actually is in the first column? Because if all the values lie between (say) 756000 and 757000 that's actually just 10 bits of entropy, not 19.5, and if the same applies to the other values, you're much closer to the original 90 bits.
I ran it 500,000 times, discarding the 10% most entropic results ... in the hopes of arriving at a relatively conservative estimate for the amount of entropy you actually get from each iteration. Here's the prompt I used to generate the code: <a href="https://chatgpt.com/share/6ab2df4a-7f94-83ea-aecf-1bb57c4838b9" rel="nofollow">https://chatgpt.com/share/6ab2df4a-7f94-83ea-aecf-1bb57c4838...
And here are the results of running that code:
=== No hashing ===
Clock resolution: 0.000000001 seconds
Clock reads: 500,000
Second-difference outcomes: 499,998
Retained outcomes: 449,998 (90.000%)
Average Shannon information: 1.755579 bits/retained outcome
Marginal min-entropy estimate: 1.339460 bits/retained outcome
Lag-1 conditional min-entropy: 0.960079 bits/retained adjacent outcome
Conservative descriptive proxy: 0.960079 bits/retained outcome
Proxy scaled per clock iteration: 0.864067 bits/iteration
These are empirical timing statistics, not a proven entropy rate.
=== One SHA-256 between clock reads ===
Clock resolution: 0.000000001 seconds
Clock reads: 500,000
Second-difference outcomes: 499,998
Retained outcomes: 449,998 (90.000%)
Average Shannon information: 4.205076 bits/retained outcome
Marginal min-entropy estimate: 3.610848 bits/retained outcome
Lag-1 conditional min-entropy: 3.351217 bits/retained adjacent outcome
Conservative descriptive proxy: 3.351217 bits/retained outcome
Proxy scaled per clock iteration: 3.016082 bits/iteration
These are empirical timing statistics, not a proven entropy rate.
------------
As GPT helpfully points out, this isn't a proven guarantee, but a reasonable estimate is somewhere between 3 and 4 bits of entropy per hash. That means 50 is actually enough, though if you want to be conservative I don't think there's any harm in doing 500 or even 5,000 instead of 50. And, if you are going to be using this in a hostile environment, it doesn't hurt to also add a fortuna-like accumulator that resets your entropy every once in a while.
I said this in another reply as well, but 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.
Here, we see, running it on Windows, at least 1 but of entropy per clock_gettime() call. For people who argue kernel entropy is somehow more secure, perhaps they should become familiar with how kernels before Linux 5.6 or so on some devices had issues where (u)random wouldn’t provide enough entropy to be really secure (people would use haveged to make sure they had enough entropy).
strenholme · · focus · HN ↗
It takes entropy from multiple different sources, makes it all input to the XOF, then the XOF uses cryptography to output a stream that has as much entropy as the combined entropy of all of its sources of randomness. So if an XOF, for example, takes 100 runs of rdrand16, along with the system time in microseconds and the number of milliseconds between receiving 100 packets over the network, the XOF will output a completely random stream without artifacts like never returning 0x0000, even if rdrand16 never outputs 0x0000.
Taek · · focus · HN ↗
The reason I like doing it this way is that it happens entirely in userspace, it's genuinely a secure method of generating entropy, and it has no dependencies on potentially buggy firmware or microcode outside of the time() call, which is both fairly narrow, fairly heavily used (meaning a bug is likely to be discovered during testing, as the implementation is likely heavily scrutinized), and also fairly easy to test independently - just look at the number of nanoseconds that elapse at each consecutive call to sha256(current_time()) and verify that there's some statistical variance. The above suggestions are assuming about 2.5 bits of variance between calls, meaning there should be a range of at least 20 nanoseconds between your slowest and fastest hash call. This has been true on every CPU I've ever measured, including microcontrollers.
sltkr · · focus · HN ↗
The security of your system depends on time() providing enough entropy, even though that's not what it's designed to do. It's built on top of the wrong primitive from the start.
> The reason I like doing it this way is that it happens entirely in userspace
On Linux this is often true, but there is no portable way to get the current time that is _guaranteed_ not to do any system calls.
> If your time() function has a resolution of nanoseconds, you only need your loop to iterate about 50 times to get a cryptographically secure amount of entropy.
You haven't proven that at all. It's easy to imagine that on a CPU running at a fixed frequency the interval between reads is constant, so if anyone knows (or can guess) the start time the resulting seed is entirely predictable.
This is completely independent of timer resolution. You seem to realize that as you were writing that:
> just look at the number of nanoseconds that elapse at each consecutive call to sha256(current_time()) and verify that there's some statistical variance
Oh yes, because evaluating the quality of a random number generator is such a trivial thing to do, it's not like there is decades of research behind it or anything.
And assuming you are able to verify the statistical variance: are you going to put that logic in the loop, making it significantly more complex?
Or are you going to do this test on your machine and then ship your code on the assumption that if it works on your machine, it will work everywhere else, too?
> if your time() function has a resolution of seconds you need to let it run for more like 5 seconds.
So not only is it insecure, it's agonizingly slow by design. Why do a system call that takes milliseconds at best, when we can run a loop in userspace for 5 seconds?
All this just so you can avoid writing the obviously correct oneliner:
sltkr · · focus · HN ↗
Taek · · focus · HN ↗
I have tested this method on over 100 different CPUs and I have never seen such consistent output. I'm genuinely surprised to see that you only hit 92 bits of entropy, but that can trivially be fixed by doing 10x the iterations. 500 iterations is still going to put you under a millisecond of cost.
And, for what it's worth, code I've actually shipped has combined the above technique with Fortuna, and has typically targeted 2000 bits of entropy rather than 128 (for security buffer).
EDIT: I reviewed his code, and he's not hashing between calls to check the clock; the hash call itself causes the CPU to heat up in arbitrary ways which changes the timing between hashes and introduces more entropy; removing that call basically entirely defeats the idea behind the technique, these results are fully invalid.
---
I updated the code to insert the hash call, this is what I got for his original code on my machine, and the updated code with hashing on my machine (and the difference is cryptographically meaningful):
sltkr · · focus · HN ↗
Can you run the program 10 times and show me how much variance there actually is in the first column? Because if all the values lie between (say) 756000 and 757000 that's actually just 10 bits of entropy, not 19.5, and if the same applies to the other values, you're much closer to the original 90 bits.
Taek · · focus · HN ↗
And here are the results of running that code:
------------As GPT helpfully points out, this isn't a proven guarantee, but a reasonable estimate is somewhere between 3 and 4 bits of entropy per hash. That means 50 is actually enough, though if you want to be conservative I don't think there's any harm in doing 500 or even 5,000 instead of 50. And, if you are going to be using this in a hostile environment, it doesn't hurt to also add a fortuna-like accumulator that resets your entropy every once in a while.
I said this in another reply as well, but 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.
strenholme · · focus · HN ↗
Here, we see, running it on Windows, at least 1 but of entropy per clock_gettime() call. For people who argue kernel entropy is somehow more secure, perhaps they should become familiar with how kernels before Linux 5.6 or so on some devices had issues where (u)random wouldn’t provide enough entropy to be really secure (people would use haveged to make sure they had enough entropy).