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();
Depends in what trust do you have over your hardware/OS. If you assume the hardware is potentially backdoored, and the OS is proprietary, or even if open could have malware/rootkits that can thinker around the random number generator, the solution of using a sole implementation inside the program (assuming the sha256 function is inside the program itself) maybe better.
Sure an infected system may as well fake time values, but that is much more difficult and it's possible to detect from a userspace program. For example you mention to use getentroy, but on a compromised system you know how easy it is to change something that is implemented in a system library (e.g. libc) or even if you read /dev/random directly without passing from the libc how easy it's to make it read whatever you want?
To me that is not that bad implementation, in fact it's an implementation that is used in a lot of security software (including GPG, not as the sole source of course but as one of many).
If you cannot trust the platform you're running on, all bets are off. There is a reason so much effort is put in TPM and remote attestation and so on.
A compromised kernel doesn't even have to fake any data. It can just read the generated seed directly from user space without the program ever knowing about it.
> Sure an infected system may as well fake time values, but that is much more difficult
clock_gettime() just reads a value that the kernel has set, so that's not particularly difficult to fake.
If you're thinking of using RDTSC instructions directly, that's of course not portable, and at that point you might as well call RDRAND directly, which is at least designed to provide random data.
> it's possible to detect from a userspace program.
There is no detection that is guaranteed to work on a compromised system.
And whatever detection you have in mind to make the algorithm resistant to tampering was _not_ part of the original for-loop. You cannot claim the for-loop is superior to just calling getentropy() because it "can detect" clock tampering, while handwaving away the actual code to detect this clock tampering.
> it's an implementation that is used in a lot of security software (including GPG, not as the sole source of course but as one of many).
It's fine if you use it as a strictly additional source of entropy, but then the whole argument that it is superior because it avoids syscalls goes out of the window, because you're doing strictly _more_ work.
The strength in this method is that it has the littlest possible surface area for upstream bugs to compromise your final entropy. Because, in the applied world, upstream bugs in "secure" system RNGs have been the cause of stolen crypto and other critical security compromises on numerous occasions.
And, I agree that if the system is compromised to the level that the attacker can control the output of the timer, it's probably compromised to the level that the attacker can just read your generated entropy straight from memory.
The point here is not to be fast, it's to be protected against implementation bugs on systems that weren't designed by security professionals.
> Because, in the applied world, upstream bugs in "secure" system RNGs have been the cause of stolen crypto [...]
You mean javascript libraries that do a bit of Math.random() and a miniscule amount of mixing, that had been widely considered poor practice for years while old bitcoin wallet generator websites were burning users with it?
Has any actual serious CSPRNG exposed bitcoin wallets?
This is the one I'm referring to, it used some very dumb `Math.random()`-with-unverified-incantations code that should have been obvious if anyone had just looked at it. This one is responsible for the majority of hackable bitcoin addresses. It's really embarrassing that this kept going until 2020.
(At one point this would have been a tricky situation, though, because around 2009-2013 when bitcoin wallets were first being generated in web browsers, Internet Explorer didn't provide a CSPRNG API. Because of the prevalence of IE, an in-javascript CSPRNG would have been justified as a fallback if it had proper cryptographic mixing of mouse input entropy and perhaps timing execution jitter entropy as well, along with good entropy estimation to decide when enough seeding has been performed to start generating keys. Some wallet websites actually did mouse entropy collection at the time (e.g. <a href="https://www.bitaddress.org" rel="nofollow">https://www.bitaddress.org), but often with dubious mixing. Might have been best to just ban Internet Explorer.)
> Libbitcoin / Milk Sad (2023)
Mersenne twister... likewise should have been identified as not even remotely correct. Not a serious CSPRNG at all. Similar to the CryptoJS case.
> Trust Wallet Browser Extension (2023)
Also Mersenne twister, similar to the CryptoJS case.
> Trust Wallet iOS / Trezor Library
Time-based seeding, with an exceptionally weak PRNG with only 32 bits of state. Similar to the CryptoJS case.
> Android SecureRandom (2013)
This is a buffer bug that caused existing seed data to be overwritten by newer data rather than correctly appending it. The serious cryptographic primitives weren't broken, just the input. But it is genuinely scary. Unlike the other examples, it wasn't immediately identifiable because it gave the appearance that a CSPRNG was being implemented, and being a platform API it is just as scary as the Debian bug in 2008.
> There is a reason so much effort is put in TPM and remote attestation and so on
If you trust TPM not to be backdoored... come on, you don't think the NSA or who else has put effort in getting a backdoor inside? They even tried to put one in Linux and it's documented, never the less in anything proprietary...
> It can just read the generated seed directly from user space without the program ever knowing about it.
Not that simple: it has to know exactly where in memory it's stored, and that requires understanding of the source code of the program that is encrypting data. That is not of course a simple task if someone wants to write a malware that just "steals" encrypted data from any software just by looking at the network traffic, like you would do if you compromise the RNG of the OS.
> clock_gettime() just reads a value that the kernel has set, so that's not particularly difficult to fake.
You can sample the call millions of time and understand if the value is truly random or there is a pattern. It's something detectable. Software like GPG that doesn't trust what the OS gives you already do that (as well as combining multiple entropy sources).
> It's fine if you use it as a strictly additional source of entropy, but then the whole argument that it is superior because it avoids syscalls goes out of the window, because you're doing strictly _more_ work.
Avoiding the syscall could have other benefits, not only performance. For example: a program making that syscall may be flagged by a possible backdoor as a process with something interesting in it, and thus a potential spyware may be interested in take, for example, the memory image of that program and send it to a remote system for it to be analyzed. The fact that the reading of the current time doesn't pass from a system calls means that it's not possible to identify that process as "some process that uses cryptography and thus has something interesting in it to hide".
“Software like GPG that doesn't trust what the OS gives you already do that”
Exactly. The people who are so adamant that one shouldn’t roll their own crypto are people who think we should just blindly trust the kernel to always return secure random numbers which haven’t been backdoored.
Now, in the real world, if they control the kernel’s RNG, they control a lot more than the RNG so any protection is an illusion. But blindly trusting a kernel’s RNG is something that makes some people understandably uncomfortable.
The decision I made to include a secure random number generator as part of my code in 2007 was the exact same decision DJB made to include a secure random number generator with his code in 1999, and it’s a decision I stand by: It never has had a known security problem, the FUD claiming otherwise isn’t backed up by evidence, and it makes a lot of sense in cross-platform code which targets embedded systems.
The point is this: Getting micro-timing won’t give us as much entropy as we want, but it will still give us entropy. So it’s a perfectly good yet-another-source of entropy to feed in to an entropy pool (such as the input to a XOF).
If those Coldcard devices had used this code as one source of entropy, and this source of entropy was the only entropy still working, they never would had been compromised.
(I won’t update my 18-year-old PRNG to use this code, of course, since that code is now 18 years old and there are no known weaknesses in said code)
Actually, it gives you as much entropy as you need, just increase the iterations. That guy's output is shockingly consistent, so to be conservative maybe we say 0.2 bits of entropy per iteration. So just do 1000 iterations. That's still only going to take a few milliseconds even on embedded hardware.
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.
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).
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.
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: <a href="https://pastebin.com/ZrL1UDEg" rel="nofollow">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.
Any good crypto library will have a solid secure random source that usually combines entropy from multiple sources with a provably secure hash based mixing scheme.
Hardware RNGs can be one source, but no single source is trusted, and they're all combined in a way where even an intentionally malicious source is lost in noise and cannot actually determine output.
Yeah, this comes off as a “they already are on the wrong side of the secure hatch” kind of attack. A malicious hardware device with physical access to a victim’s computer can do a lot more than generate malicious entropy.
It’s like the attacks I occasionally see which are like “once we have administrator, we can attack the process because of this insecurity”. Well, yeah, but once we have administrator, we can read the entire memory of the “vulnerable” process and completely control its output too.
I’ve seen in the real world attacks where things were insecure because the PRNG wasn’t given enough entropy (CVE 2008-0166, Coldcard, etc.). I’ve never seen real world attacks where a PRNG was insecure from getting too much entropy.
That's exactly the challenge though: "any good crypto library" - there is a long history of meaningful security breached (like stolen crypto tokens) due to bugs in an upstream library, especially when using things like embedded code, alternative operating systems, newer programming languages, etc.
The value of the iterated hashing method is that it is dead simple and has little dependency on potentially buggy upstream code; it works even in very lightweight environments designed by engineers with no experience in security.
The reason I roll entropy in userspace is because there's a very long history of "cryptographic" libraries getting it wrong (see the parent article for an example). Crypto tokens stolen because the underlying call to the web browser entropy only had 32 bits of actual randomness. Crypto tokens stolen because the underlying embedded system (like cold card) turned off some security critical features to improve performance and power.
Pretty much the only thing you can control when shipping software to many devices is that it runs on a physical CPU and has a timer. Every other RNG assumption over the decades has shown that sometimes someone upstream gets something catastrophically incorrect.
I wouldn’t trust it as a sole source of entropy, but it can be one of multiple entropy sources to feed in to an XOF to get secure numbers.
The nice thing about using multiple entropy sources with a secure XOF is that the resulting entropy is at least as strong as the most secure entropy source given to the XOF.
TL;DR adding a compromised source of entropy to a pool of already secure sources of entropy can catastrophically compromise the final result.
It's better to source entropy from a smaller number of harder-to-compromise sources.
That's why I like the iterated hashes method; the security surface area is both very small and highly likely to be well tested.
>>>what I'm advocating here, for security reasons, is a sharp transition between
* before crypto: the whole system collecting enough entropy;
* after: the system using purely deterministic cryptography, never adding any more entropy.<<<
Which is exactly how a XOF should be used, and how I used the XOF in my code. A malicious source of entropy will need to perform 2^n operations to control n bits of the XOF’s output, and that’s assuming the malicious entropy source somehow perfectly knows the other entropy the XOF is using.
Yes but why introduce complexity and room for error when something that's extremely basic is also sufficient?
The point here is to eliminate surface area for mistakes, and an XOF has a much larger and more complex implementation than iterated hashing against a timer.
I know that there's a really strong culture in the software world around downvoting anything that looks or smells like "hand-rolled cryptography", but this is my actual profession and specialization within the software world, and most of what I'm seeing in this thread is knee-jerk reactions to an unexpected technique rather than careful intellectual commentary and consideration of the merits of the technique.
I am happy to have a discussion with you at the deepest technical levels of applied cryptography, this is not something I blindly made up on my own. I'm well studied in the field and can readily defend this technique.
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:
alerighi · · focus · HN ↗
Sure an infected system may as well fake time values, but that is much more difficult and it's possible to detect from a userspace program. For example you mention to use getentroy, but on a compromised system you know how easy it is to change something that is implemented in a system library (e.g. libc) or even if you read /dev/random directly without passing from the libc how easy it's to make it read whatever you want?
To me that is not that bad implementation, in fact it's an implementation that is used in a lot of security software (including GPG, not as the sole source of course but as one of many).
sltkr · · focus · HN ↗
A compromised kernel doesn't even have to fake any data. It can just read the generated seed directly from user space without the program ever knowing about it.
> Sure an infected system may as well fake time values, but that is much more difficult
clock_gettime() just reads a value that the kernel has set, so that's not particularly difficult to fake.
If you're thinking of using RDTSC instructions directly, that's of course not portable, and at that point you might as well call RDRAND directly, which is at least designed to provide random data.
> it's possible to detect from a userspace program.
There is no detection that is guaranteed to work on a compromised system.
And whatever detection you have in mind to make the algorithm resistant to tampering was _not_ part of the original for-loop. You cannot claim the for-loop is superior to just calling getentropy() because it "can detect" clock tampering, while handwaving away the actual code to detect this clock tampering.
> it's an implementation that is used in a lot of security software (including GPG, not as the sole source of course but as one of many).
It's fine if you use it as a strictly additional source of entropy, but then the whole argument that it is superior because it avoids syscalls goes out of the window, because you're doing strictly _more_ work.
Taek · · focus · HN ↗
And, I agree that if the system is compromised to the level that the attacker can control the output of the timer, it's probably compromised to the level that the attacker can just read your generated entropy straight from memory.
The point here is not to be fast, it's to be protected against implementation bugs on systems that weren't designed by security professionals.
creatonez · · focus · HN ↗
You mean javascript libraries that do a bit of Math.random() and a miniscule amount of mixing, that had been widely considered poor practice for years while old bitcoin wallet generator websites were burning users with it?
Has any actual serious CSPRNG exposed bitcoin wallets?
Taek · · focus · HN ↗
creatonez · · focus · HN ↗
This is the one I'm referring to, it used some very dumb `Math.random()`-with-unverified-incantations code that should have been obvious if anyone had just looked at it. This one is responsible for the majority of hackable bitcoin addresses. It's really embarrassing that this kept going until 2020.
(At one point this would have been a tricky situation, though, because around 2009-2013 when bitcoin wallets were first being generated in web browsers, Internet Explorer didn't provide a CSPRNG API. Because of the prevalence of IE, an in-javascript CSPRNG would have been justified as a fallback if it had proper cryptographic mixing of mouse input entropy and perhaps timing execution jitter entropy as well, along with good entropy estimation to decide when enough seeding has been performed to start generating keys. Some wallet websites actually did mouse entropy collection at the time (e.g. <a href="https://www.bitaddress.org" rel="nofollow">https://www.bitaddress.org), but often with dubious mixing. Might have been best to just ban Internet Explorer.)
> Libbitcoin / Milk Sad (2023)
Mersenne twister... likewise should have been identified as not even remotely correct. Not a serious CSPRNG at all. Similar to the CryptoJS case.
> Trust Wallet Browser Extension (2023)
Also Mersenne twister, similar to the CryptoJS case.
> Trust Wallet iOS / Trezor Library
Time-based seeding, with an exceptionally weak PRNG with only 32 bits of state. Similar to the CryptoJS case.
> Android SecureRandom (2013)
This is a buffer bug that caused existing seed data to be overwritten by newer data rather than correctly appending it. The serious cryptographic primitives weren't broken, just the input. But it is genuinely scary. Unlike the other examples, it wasn't immediately identifiable because it gave the appearance that a CSPRNG was being implemented, and being a platform API it is just as scary as the Debian bug in 2008.
alerighi · · focus · HN ↗
If you trust TPM not to be backdoored... come on, you don't think the NSA or who else has put effort in getting a backdoor inside? They even tried to put one in Linux and it's documented, never the less in anything proprietary...
> It can just read the generated seed directly from user space without the program ever knowing about it.
Not that simple: it has to know exactly where in memory it's stored, and that requires understanding of the source code of the program that is encrypting data. That is not of course a simple task if someone wants to write a malware that just "steals" encrypted data from any software just by looking at the network traffic, like you would do if you compromise the RNG of the OS.
> clock_gettime() just reads a value that the kernel has set, so that's not particularly difficult to fake.
You can sample the call millions of time and understand if the value is truly random or there is a pattern. It's something detectable. Software like GPG that doesn't trust what the OS gives you already do that (as well as combining multiple entropy sources).
> It's fine if you use it as a strictly additional source of entropy, but then the whole argument that it is superior because it avoids syscalls goes out of the window, because you're doing strictly _more_ work.
Avoiding the syscall could have other benefits, not only performance. For example: a program making that syscall may be flagged by a possible backdoor as a process with something interesting in it, and thus a potential spyware may be interested in take, for example, the memory image of that program and send it to a remote system for it to be analyzed. The fact that the reading of the current time doesn't pass from a system calls means that it's not possible to identify that process as "some process that uses cryptography and thus has something interesting in it to hide".
strenholme · · focus · HN ↗
Exactly. The people who are so adamant that one shouldn’t roll their own crypto are people who think we should just blindly trust the kernel to always return secure random numbers which haven’t been backdoored.
Now, in the real world, if they control the kernel’s RNG, they control a lot more than the RNG so any protection is an illusion. But blindly trusting a kernel’s RNG is something that makes some people understandably uncomfortable.
The decision I made to include a secure random number generator as part of my code in 2007 was the exact same decision DJB made to include a secure random number generator with his code in 1999, and it’s a decision I stand by: It never has had a known security problem, the FUD claiming otherwise isn’t backed up by evidence, and it makes a lot of sense in cross-platform code which targets embedded systems.
sltkr · · focus · HN ↗
strenholme · · focus · HN ↗
The point is this: Getting micro-timing won’t give us as much entropy as we want, but it will still give us entropy. So it’s a perfectly good yet-another-source of entropy to feed in to an entropy pool (such as the input to a XOF).
If those Coldcard devices had used this code as one source of entropy, and this source of entropy was the only entropy still working, they never would had been compromised.
(I won’t update my 18-year-old PRNG to use this code, of course, since that code is now 18 years old and there are no known weaknesses in said code)
Taek · · focus · HN ↗
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.
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).
Taek · · focus · HN ↗
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.
sltkr · · focus · HN ↗
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: <a href="https://pastebin.com/ZrL1UDEg" rel="nofollow">https://pastebin.com/ZrL1UDEg
Taek · · focus · HN ↗
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.
api · · focus · HN ↗
Hardware RNGs can be one source, but no single source is trusted, and they're all combined in a way where even an intentionally malicious source is lost in noise and cannot actually determine output.
strenholme · · focus · HN ↗
<a href="https://blog.cr.yp.to/20140205-entropy.html" rel="nofollow">https://blog.cr.yp.to/20140205-entropy.html
Intel could much more easily compromise and attack systems than make an implementation of RdRand which is malicious in this manner.
api · · focus · HN ↗
strenholme · · focus · HN ↗
It’s like the attacks I occasionally see which are like “once we have administrator, we can attack the process because of this insecurity”. Well, yeah, but once we have administrator, we can read the entire memory of the “vulnerable” process and completely control its output too.
I’ve seen in the real world attacks where things were insecure because the PRNG wasn’t given enough entropy (CVE 2008-0166, Coldcard, etc.). I’ve never seen real world attacks where a PRNG was insecure from getting too much entropy.
tptacek · · focus · HN ↗
Taek · · focus · HN ↗
The value of the iterated hashing method is that it is dead simple and has little dependency on potentially buggy upstream code; it works even in very lightweight environments designed by engineers with no experience in security.
Taek · · focus · HN ↗
Pretty much the only thing you can control when shipping software to many devices is that it runs on a physical CPU and has a timer. Every other RNG assumption over the decades has shown that sometimes someone upstream gets something catastrophically incorrect.
strenholme · · focus · HN ↗
The nice thing about using multiple entropy sources with a secure XOF is that the resulting entropy is at least as strong as the most secure entropy source given to the XOF.
Taek · · focus · HN ↗
<a href="https://blog.cr.yp.to/20140205-entropy.html" rel="nofollow">https://blog.cr.yp.to/20140205-entropy.html
TL;DR adding a compromised source of entropy to a pool of already secure sources of entropy can catastrophically compromise the final result.
It's better to source entropy from a smaller number of harder-to-compromise sources. That's why I like the iterated hashes method; the security surface area is both very small and highly likely to be well tested.
strenholme · · focus · HN ↗
From that page:
>>>what I'm advocating here, for security reasons, is a sharp transition between
* before crypto: the whole system collecting enough entropy;
* after: the system using purely deterministic cryptography, never adding any more entropy.<<<
Which is exactly how a XOF should be used, and how I used the XOF in my code. A malicious source of entropy will need to perform 2^n operations to control n bits of the XOF’s output, and that’s assuming the malicious entropy source somehow perfectly knows the other entropy the XOF is using.
Taek · · focus · HN ↗
The point here is to eliminate surface area for mistakes, and an XOF has a much larger and more complex implementation than iterated hashing against a timer.
Taek · · focus · HN ↗
I am happy to have a discussion with you at the deepest technical levels of applied cryptography, this is not something I blindly made up on my own. I'm well studied in the field and can readily defend this technique.