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