According to Theodore Ts there was pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction.
"
I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction. To quote from the article below:
"By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors...."
Relying solely on the hardware random number generator which is using an implementation sealed inside a chip which is impossible to audit is a BAD idea.
"
Putting a backdoor into CSPRNG is a favored way to break crypto, for example Dual_EC_DRBG.
"
Weaknesses in the cryptographic security of the algorithm were known and publicly criticised well before the algorithm became part of a formal standard endorsed by the ANSI, ISO, and formerly by the National Institute of Standards and Technology (NIST). One of the weaknesses publicly identified was the potential of the algorithm to harbour a cryptographic backdoor advantageous to those who know about it—the United States government's National Security Agency (NSA)—and no one else. In 2013, The New York Times reported that documents in their possession but never released to the public "appear to confirm" that the backdoor was real, and had been deliberately inserted by the NSA as part of its Bullrun decryption program. In December 2013, a Reuters news article alleged that in 2004, before NIST standardized Dual_EC_DRBG, NSA paid RSA Security $10 million in a secret deal to use Dual_EC_DRBG as the default in the RSA BSAFE cryptography library, which resulted in RSA Security becoming the most important distributor of the insecure algorithm. RSA responded that they "categorically deny" that they had ever knowingly colluded with the NSA to adopt an algorithm that was known to be flawed, but also stated, "We have never kept this relationship [with the NSA] a secret and in fact have openly publicized it."
It is just possible they decided crypto code that uses it was safer to skip zeros. (Whist mathematically it should be no more likely; it is vastly more likely someone will actually try that key).
It is also possible that their code was generating too many zeros and the easiest fix was to discard them all.
Can you clarify what you mean by "it is vastly more likely someone will actually try that key"?
I'm guessing you don't think there are people calling rdrand in a loop and throwing away the output with high probability except when it is 0, but I can't see how else you imagine people would be vastly more likely to use the output when it is 0?
In lots of scenarios I know the software used to generate the key; the only unknown is the random numbers used. If I am searching for weaknesses it is highly likely I would try keys with different seeds; zero, one, are going to me much more likely choices here then hoping I can guess the right values.
If someone was using RDRAND16 to seed a PRNG, choosing to omit one single value (a zero) from the return value would not significantly improve the generated values, if at all.
So you think a weighted die is more random than a fair die? A uniform distribution means each outcome has equal probability; it doesn’t mean the outcome is predictable.
Because each number is equally as likely as every other number. If you know you're more likely to get certain numbers, or in this case have no chance of getting certain other numbers, it is by definition _less random_.
You are both right, the atom decaying is completely random but the distribution of the decays is still predictable.
If you have a random number generator your are relying on the fact that it is uniformly distributed and thus has no bias towards certain numbers.
Or if it is not uniformly distributed you would want to know the exact distribution so you can correct for it.
If you have an RNG that is treated as putting out uniformly distributed numbers but it is does in fact favor some numbers over others, that would be a defect that can cause problems/be exploited.
Ah. My reasoning, with the normal distribution, was that zero was at the left most end of the curve and with a pretty much non-existent chance of appearing.
As the number of samples approaches infinity, the percentage share of all possible results approaches equality. A uniform random distribution is like the mathematical identity of statistics.
I'm getting 16-bit zeros on my Zen 3 chip (+1:3821, 0:3893, -1:3895), I will wait to get some statistically significant samples for the 32-bit values and update the forum thread. Maybe it was fixed after Zen 2?
Does anyone have access to an HPC cluster with thousands of Zen2 chips? We might want to check 64-bit ones with that - should take just a couple years depending on the size of the machine.
Anyone from the High-Performance Computing Center Stuttgart willing to play on the 720,320 Zen2 cores?
This is not the first RNG bug on Zen 2, I recall after I first got mine that some application or other would quit immediately at startup because rdrand always returned -1, i.e. all 1s. It was fixed with a microcode update.
Do we now learn that they fixed "always generate all 1s" with "never generate all 0s"??
EDIT: I've been unable to reproduce the problem on my CPU, FWIW. It's a Ryzen 5 3600.
EDIT2: OK, update, I can reproduce it with rdrand16, rdrand32 is fine but rdrand16 can never generate all 0s. So my CPU does have this problem!
The PS3 was first released in November 2006. I haven't watched the video yet, but its description says "2010 saw the first hacks for the Playstation 3".
Yes it does. rdrand32()%65535 was my first attempt, and generated zeroes at about the expected rate, that's why I initially erroneously thought my CPU did not have this problem.
But it looks like the rdrand16 instruction can produce zeros just fine, it just sets CF=0 erroneously (indicating an error and that the user program should retry).
So keep that in mind when you try to reproduce it too and use some abstraction that could implement retries internally.
No, CF=0 occurences seem to be happen frequently and uniformely distributed like valid results at ~1/65536, not clustered.
Under a minute-long all-core load CF=0 always produces zero, but that's to be expected according to the manual.
Here are some stats:
Rounds (N): 1000000000
Failed (F): 15312
Valid (V): 999984688
N/65536: 15258.789
V/65536: 15258.555
Failed, result was zero: 15312
Failed, result non-zero: 0
Bucket value for 0: 15312
Bucket value for 1: 15290
Bucket value for 65535: 15223
Min bucket value: 14670
Max bucket value: 15835
I used this C program to collect them:
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
const size_t N = 1000000000; // 1e9
struct rdrand16_result {
uint16_t n;
bool ok;
};
static inline struct rdrand16_result rdrand16()
{
struct rdrand16_result result;
__asm__ __volatile__( "rdrand %0" : "=r" (result.n), "=@ccc" (result.ok) );
return result;
}
int main()
{
size_t buckets[0xFFFF + 1] = { 0 };
size_t notok = 0, notok_zero = 0, notok_nonz = 0;
for (size_t i = 0; i < N; ++i) {
struct rdrand16_result result = rdrand16();
++buckets[result.n];
if (! result.ok) {
++notok;
notok_zero += result.n == 0;
notok_nonz += result.n != 0;
}
}
size_t max = 0, min = N;
for (size_t i = 0; i <= 0xFFFF; ++i) {
size_t n = buckets[i];
min = n < min ? n : min;
max = n > max ? n : max;
}
printf("Rounds (N): %zu\n", N);
printf("Failed (F): %zu\n", notok);
printf("Valid (V): %zu\n", N - notok);
printf("N/65536: %.3f\n", (double)N / 65536);
printf("V/65536: %.3f\n", (double)(N - notok) / 65536);
printf("Failed, result was zero: %zu\n", notok_zero);
printf("Failed, result non-zero: %zu\n", notok_nonz);
printf("Bucket value for 0: %zu\n", buckets[0]);
printf("Bucket value for 1: %zu\n", buckets[1]);
printf("Bucket value for 65535: %zu\n", buckets[0xFFFF]);
printf("Min bucket value: %zu\n", min);
printf("Max bucket value: %zu\n", max);
return 0;
}
Funny. Look up errata AMD-SB-7055: RDSEED Failure on AMD “Zen 5” Processors.
Zen 5 rdrand16/32 return zero with CF=1 on entropy exhaustion and their recommended approach directly leads to the issue you observed: treat all-zero result of rdseed as if cf=0 (failure) and re-roll the dice, effectively recreating the zen 1/zen 2 issue all over again!
They say this might be addressed by a future microcode update… meaning there’s a chance they’ll just patch it to do just that in software. Maybe that’s how they got into this mess in the first place?
Also, am I a complete idiot or is asserting the relative distribution of a mere 64k possible results a rather easy black box validation test that I would’ve assumed they’d be doing? When I used to write cycle-accurate emulators in the past, that would have been an obvious test to include. This isn’t some arcane instruction no one uses or a really complicated case with deep dependency and/or timing issues; it’s like getting rdtsc wrong.
If I remember correctly, we had a setting in every Linux server we owned to remove CPU as a RNG seeder for the kernel because of those bugs with AMD CPUs.
I.e., we had `random.trust_cpu=off nordrand` in `GRUB_CMDLINE_LINUX`.
As far as I know that is correct; the kernel was written in a way such that one bad source doesn’t poison the pool. Still, if you know one source is bad, might as well take it out.
Why? That would actually reduce randomness. The value of adding sources to the entropy pool has a floor of zero. Worst case scenario, it just provides no extra entropy.
You don't know if it's bad. Microcode updates might fix it, or break it for that matter. Revision history can be difficult if not impossible to comprehensively catalog.
What it is is unreliable. And that's fine so long as you have other entropy sources. OpenBSD is really good about this. Quite a few drivers for various chipsets and cards exist just to read their RNGs, not actually use them for their primary function (which can be a bummer if you want to use the the device, get your hopes up when you see the driver exists in the tree, then discover the only capability it supports is reading the RNG). If you have a CPU with a known bad rdrand, odds are OpenBSD is still sourcing strong randomness from some other chip in your system (PSP, NIC, etc). And because feeding bad (as opposed to malicious[1]) entropy is harmless[2], they don't have to maintain a pile of conditions. Nobody is worse off, and overall everybody is better off, including having stronger getrandom/getentropy output, by not trying to be clever.
[2] Presuming nothing is relying on an entropy estimator. I can't remember if Linux finally moved past the entropy estimator nonsense. IIRC they did add a software jitter RNG that runs early to try to set a minimum entropy floor, regardless of hardware sources.
that's fine so long as you have other entropy sources
Well, if you literally have nothing else, then you don't have an option anyway, so the whole question is moot.
Except yeah if literally the only way to collect entropy in your system is the platform's opaque RNG, then sure this means your risk assessment should list that as a SPOF. But by definition these cases only have that option, so you can't do anything else.
In reality, you can probably do something else in all but the most extreme embedded environments.
if you know one source is bad, might as well take it out.
Yes and no. Mostly no.
In a simplified model, it's only useless if it adds zero bits of entropy. But if a source that's supposed to add 128 bits of entropy only adds 16, well, it's still 16.
I would never trust RDRAND on its own. If nothing else because it's always subject to a microcode backdoor. But if I already have something I'm happy with the entropy of, sure, I'd XOR it with RDRAND output. It cannot make it worse.
this is generally true however if an adversary is able to control a source it becomes dangerous if they can preview the results or inspect the other sources.
if your algorithm controls a source of entropy and can inspect the other sources, it can craft its source to bias the result. a fanciful attack but it means you should at least discriminate what you put into the pool.
Can you link to the paper you're thinking of? Maybe people are just talking past each other here. A biased random source can't bias the kernel random pool in any straightforward kind of way.
Right, so your starting point is that the attacker has read-only access to ALL entropy sources, and in that scenario it's worse if the attacker has read-write access to one entropy source.
Yes. I don't find this a particularly interesting scenario, though. Sure, we can come up with stuxnet-like airgap attacks where we on-device, but not remotely, can read entropy sources. AND we can modify the output of RDRAND. And there keys have been generated for data we can later intercept. But despite that control (potentially on a CPU microcode level) we are unable to stegonographically leak it?
nordrand has been removed from the kernel as it had become overloaded by meaning both a) and b)
Under most circumstances, a) is harmless. You mostly want that off when the CPU exhibits some performance hiccups when asked.
Under some circumstances, b) is outright dangerous. Some applications can work without seeded pool at some slightly reduced performance, but could be made to fail miserably if they had been made to believe that the pool was seeded yet it was not. This happens with hash tables when you skip some of the accounting because it seems no longer relevant. It really would not be relevant, once even a determined attacker should be unable to reliably trigger the worst-case-performance.
Usually you do "rdrand % <some-number>" anyways, and in that case you will still get zeroes. True, your result might be skewed by 1/(maxint/some-number) but I guess that's not a big problem in practice
If you want uniformly-distributed random numbers, computing the remainder works only when the modulus is a power of two.
Otherwise, a slightly more complicated algorithm is necessary, where you reject a range of numbers either before computing the remainder (to make the set of possible values a multiple of the modulus) or after computing the value modulo some power of two (to reject values greater than your target).
Besides these 2 variants based on the remainder of division of integers, there are also 2 corresponding algorithms using multiplication of the input interpreted as a fraction, followed by taking the integer part of the result.
I always wonder how hardware bugs like this happen with the sheer amount of hardware validation that's done. It'd be fascinating to know how it slipped through the cracks, though I know almost nothing about this side of the industry sadly
That "sheer amount of hardware validation" is always less-than-perfectly spread across a whole lotta billions of transistors, and combinatorics is a harsh mistress.
Validation can't be better than the quality of the specification. Humans don't create comprehensive, unambiguous specifications for the same reasons that we don't write bug-free code, and need formal validation.
Brooks talks about this in _Mythical_Man-Month_... if you really could "just implement the specification", then the specification itself would be complete enough to serve as your code. There will always be bugs in both.
So what? The point is to be non predictable not to pick all the numbers in the range with exactly the same probability. Would it be a problem if it never generated 16542?
By your argument, it would not be a problem if the RNG never generated 0. So, it must follow that it would also not be a problem if it never generated {1, 2, 3, ..., 253}.
That means that our RNG now only generates the values 254 and 255. Which of the values is generated is unpredictable on any given call. However, 7 of the 8 output bits are now always fixed and so completely predictable. Can you imagine how an attacker could exploit that?
Failing to generate only the number 0 is a weaker version of the same class of flaw.
We're talking about whether a modification of the expected probabilities changes the dynamics of the game. The example I gave was deliberately extreme, because that makes it easier to reason about.
If you want a casino example, then consider a roulette wheel that always lands on 36 but still pays out as usual. I think you'd want to play on it. Now consider one that always lands somewhere between 30 and 36. Still worth it, right? With careful bets and a good starting float you're still coming away from the table up (with a very high probability).
In fact for a roulette wheel you only need two dead pockets for the player to get an edge. Bias is exploitable.
Sure, but you’re pressing on the truth that a small modification taken to an extreme is a large modification.
When the original point was that a tiny fractional loss in an RNG is not going to make a practical difference. Which I believe is also true. And it is also true that a large loss in an RNG is catastrophic.
They can both be true.
And roulette is 2 out of 38, 5.2%. That’s 17 times more than the 1/256 here, which was already a simplification of the (I think) 1/65536 in question.
With respect, I think you're still missing my point, which is simply that bias introduces vulnerability. Without a real scenario to analyze, the scale doesn't really factor into the argument. A vulnerability is a vulnerability until proven mitigated.
a tiny fractional loss in an RNG is not going to make a practical difference
I'm not so sure this is true. I don't think either of us is in a place to say whether this vulnerability has practical applications or not. A 1/65536 bias might seem like nothing important to you. It seems like potentially something to me, in a world where the attacker might control the volume of data generated.
It is absolutely untrue that a biased RNG has "zero practical impact." Modern cryptography has plenty of examples of relatively small biases leading to breaks. Check out Bleichenbacher's attack, for instance.
You could be correct that the very small bias here is not enough to be exploitable. But, given the history around this, it would be wrong to handwave it away as trivial.
It's not a 2^16-sided weighted die. But a 2^16 - 1 sided fair die.
I am not saying there is no bug. I am saying the bug has no practical impact.
Sure if you are that one guy that is getting these values raw from the instruction and comparing to zero for some purpose then you are in trouble. But I am pretty sure no one is doing that, especially given that the bug surfaced after 6 years of millions of users.
“Pick all the numbers in the range with exactly the same probability” is a very important property of RNGs. Yes, skipping 16542 would be equally bad.
You can frame it around being “non predictable”, but then you need to define those words. It’s not, for example, a poker game where it’s trying to bluff you, right? It’s also not about just making predictions < 100% reliable and declaring victory. It must specifically make all predictions no better than random guessing, and that entails picking any number in range with equal probability, otherwise predictions like “it will be {hot spot}” or “it won’t be {cold spot}” do better than random chance. In this case, specifically, I can predict with 100% accuracy that the result won’t be 0, and that’s a flaw in its unpredictability. I can also predict a bunch of other things with slightly higher accuracy than random guessing, like that it will be odd or greater than max ÷ 2.
Yikes at this: "I am so glad I resisted pressure from engineers working at Intel to let /dev/random in Linux rely blindly on the output of the RDRAND instructure." -Theodore Ts'o (2013)
It is literally the first Peano axiom that 0 is a natural number. In fact it is the only natural number that is defined in and of itself. All other natural numbers are defined by using the “successor” operation to add things to zero.
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.
Yes, /dev/(u)random is supposed to do that, but what if there’s a bug in a kernel (e.g. some embedded system which may not even be running Linux) which causes /dev/(u)ramdom to be less than secure? There’s also issues where, for example, it may no longer be possible to read /dev/(u)random after putting the process in a chroot() sandbox (chroot() isn’t defined in POSIX so its behavior is not guaranteed to be consistent across multiple operating systems).
getrandom() is often times suggested, but alas isn’t a standardized function, i.e. it’s not part of the POSIX specification. Considering how the C23 changes to the C specification caused a lot of perfectly good C code to no longer compile, I’m very anal about sticking to specs; I use '-std=C99' for my code these days (even though it can compile as C23 code) and stick to POSIX functions (except chroot() and setgroups(), but both of those predate POSIX, and even here I have a compile-time option to compile my code without those non-POSIX syscalls).
The code using a secure XOF (the algorithm was developed by the same team which later on made SHA-3, and includes people who helped make AES) has been around for nearly two decades (the code where I roll my own RNG to make secure random numbers has been around for over 25 years, but used AES before XOFs existed) and not one security problem has found with the RNG code has ever been found. [1] “Don’t roll your own RNG” is a suggestion, but it is possible to do so securely if one knows what they are doing (i.e. they have read Applied Cryptography and keep current with cryptographic developments).
For anything vibe coded (my code is 100% human written, for the record), rolling one’s own RNG is a really bad idea.
[1] There was a theoretical issue with cache timing attacks over two decades ago, so I put mitigations in place, and then chose to use an XOF for newer code.
[2] There was an issue where a separate implementation I made of this XOF would generate incorrect test vectors in clang, but only at some optimization levels. I now test the XOF in both GCC and clang at multiple optimization levels to make sure it acts correctly.
No you see what we do, Is we ask Claude to make no mistakes in implementing the CSPRNG. This way we ensure there are no mistakes in the implementation or mathematics.
I know it’s a joke, but that code wouldn’t pass the DieHard tests. That’s actually one of the tests I did with the XOF I used, a test I ran over 16 years ago.
Black-and-white thinking like this is always inaccurate.
untested
The automated tests includes tests that make sure the XOF is correctly implemented. [1]
unlooked at
People have been looking at my code for security holes for well over 20 years, and I have been getting multiple AI assisted security reports over the last year, things like “there’s a buffer overflow in this code which is nay to impossible to exploit, using code which hasn’t even been able to compile since 2022”.
XOF correctly implemented doesn’t ensure you haven’t made other mistakes, such as using entropy sources correctly, doing needed math correctly to avoid any entropy bias, etc. etc….
You’re correct about black and white thinking. Then you invoke multiple straw men in this thread to defend that you’ll roll your own.
Disclaimer: I’ve been hired for multiple DoD projects to break hardware and software security systems, and I nearly always succeed, because so many people (and companies) roll their own.
The nice thing about a secure XOF is that it doesn’t matter if the entropy given to the XOF is less than perfect. If an XOF is given 10 different sources of entropy, and only one of them is secure, the XOF will remain secure. [1]
One reason why I don’t change the RNGs used in my code is because I know how dangerous playing with RNG code is. For example, one implemention I wrote of the XOF—not one I used in production code, mind you—generated incorrect vectors, but only in clang and only at some levels of optimization. Needless to say, I now have a test to make sure my XOF code generates correct vectors with both GCC and clang at multiple different optimization levels.
People have brought up CVE-2008-0166 in this thread, but the Coldcard incident from this year (where people literally lost millions of dollars) also comes to mind, so I’m aware how dangerous playing with RNG code is.
That’s why the code is basically the same code I had 18 years ago, and why I (as well as multiple people running AI-assisted security audits) have extensively tested that code.
The proof is in the pudding: No security issues have ever been found with the XOF PRNG, and it’s been nearly two decades.
(I also think “straw men” is being used incorrectly here; most likely the parent poster thinks I was implying that Linux’s /dev/urandom is insecure but the actual argument is that my code runs on a lot more than just Linux, and some of those systems could have an insecure /dev/urandom)
[1] As per https://blog.cr.yp.to/20140205-entropy.html as long as we’re not using a malicious source of entropy, but said malicious source will need to perform 2^n operations of the XOF to generate n bits of controlled output, and only in the case if said malicious entropy source can somehow know the output of the other entropy sources, especially since the XOF is seeded once then run indefinitely in my code.
The nice thing about a secure XOF is that it doesn’t matter if the entropy given to the XOF is less than perfect. If an XOF is given 10 different sources of entropy, and only one of them is secure, the XOF will remain secure. [1]
Isn’t that also true of the cryptographic sponge function that is used to implement /dev/{,u}random?
i remember some linux kernel dev got ousted by the community because he/she wanted to not implement a backdoor that would compromise the results of /dev/urandom.
I have no idea about the claim of a backdoor. But here is the source:
Matt Mackall:
"It's worth noting that the maintainer of record (me) for the Linux RNG quit the project about two years ago precisely because Linus decided to include a patch from Intel to allow their unauditable RdRand to bypass the entropy pool over my strenuous objections. "
The fact that Intel Bull Mountain (code name for Secure Key Technology), and NSA's BULLRUN program share the name "bull" is a complete coincidence. I'm sure.
getrandom() is often times suggested, but alas isn’t a standardized function
The POSIX standard function is getentropy(), which internally calls getrandom() on Linux.
what if there’s a bug in the kernel which causes /dev/(u)ramdom to be less than secure?
It's often the other way around: the Linux kernel contains thousands of workarounds for buggy hardware, while the buggy hardware itself doesn't always get patched. Linux developers take this stuff very seriously. As a result it's often safer to rely on kernel APIs than to access the hardware directly.
The kernel code involving random number generation receives an exceptionally high amount of scrutiny because of its security implications, so I'd trust it to do the right thing over a naked call to RDRAND which nobody knows how exactly it's implemented in proprietary hardware or a handrolled solution to mix the RDRAND output with other entropy sources.
Remember the Debian openssl disaster from 2008? That happened exactly because someone had handrolled their entropy mixing solution, then someone else broke it.
“The intended use of this function is to create a seed for other pseudo-random number generators”
So, if I were to use genentropy() in a POSIX-compliant way, I would need to do what I already do: Use my own pseudo-random number generator.
The Debian openssl disaster (CVE 2008-0166, I remember it well) was caused because someone incorrectly patched secure code: Since the code used uninitialized memory as one of many entropy sources, which causes Valgrind to complain, they patched the code to not use uninitialized memory for entropy, but then accidentally disabled all other sources of entropy (except the 16-bit PID). It was caused because the person making the patch didn’t fully understand why it was a good idea to, in that context, use code which Valgrind complained about. [1]
As an aside, here’s how I deal with those Valgrind errors:
#ifdef VALGRIND_NOERRORS
/* Valgrind reports our intentional use of values of uncleared
* allocated memory as one source of entropy as an error, so we
* allow it to be disabled for Valgrind testing */
memset(noise,0,512);
#endif /* VALGRIND_NOERRORS */
I do believe the Linux Kernel does have secure RNG code, but I also write code which has run on a lot of different systems and environments, including embedded ones, and some of them might not have a secure /dev/urandom.
[1] Debian has a lot of inflexible policies like this which can cause problems. Another issue Debian has is they have a policy a given piece of code must always compile to the same binary on a given architecture. That isn’t true with the unpatched version of my code, because the hash compression routine uses a 32-bit random number generated at compile time to avoid hash collision attacks (it also uses another 32-bit random number at runtime, and I make sure the hash compression values are never visible). So the Debian version of my code was forced to be patched to be less secure.
Uninitialized memory should never be used as source of entropy. Most release software these days compiles using hardening flags, which will (at some levels) replace uninitialized memory with sentinel values, making the entropy of uninitialized memory frequently around 0.
But it gets worse. If the optimizer sees that you're loading uninitialized memory, it can reason that since the result of uninitialized memory is garbage, doing any computation on that result is also garbage, and happily delete said computation as a result. The cascading effect of this is to delete all of the entropy-mixing code, leaving your entropy pool with only the very low entropy source--giving uninitialized memory effectively negative entropy.
The net effect is that, at least for me, seeing someone trying to seed an entropy pool with uninitialized memory is a giant neon flashing sign saying "do not trust this code." It provides at best very little entropy and at worst actively destroys entropy and has other calamitous effects like valgrind or sanitizer errors, so you need to have other entropy sources anyways, so why bother?
If the optimizer sees that you're loading uninitialized memory, it can reason that since the result of uninitialized memory is garbage, doing any computation on that result is also garbage, and happily delete said computation as a result
This is an interesting assertion, and one that is easy enough to prove true.
Let’s take the following C code, which uses the same XOF algorithm (but not implementation) as my application (Deadwood):
This code, as I’m sure the parent poster can clearly see, uses four bits of uninitialized allocated memory as its source of entropy. As per the parent’s assertion, there should therefore exist a compiler whose optimizer will cause this XOF to not correctly run.
The above code can have one of the following possible 16 outputs:
If the above code has any but one of the above 16 outputs, this is a real world case where a C compiler, seeing uninitialized memory being used, optimizes out the code which uses said uninitialized memory as an input, and therefore will not output one of the above 16 possible words.
I’ve tested the above code in GCC -O3 and clang -O3; both generate one of the above 16 possible outputs (each one generating a different output).
If there really is a compiler out there which does “happily delete said computation”, which would give a different output than one of the 16 outputs above, please name that compiler, the version of said compiler used, and all compile-time flags used with said compiler.
While I’ve never heard of a real world case where a compiler would refuse to run code using uninitialized memory as yet another source of entropy for a secure PRNG, I do know of a real world case where a very nasty security hole was caused because someone incorrectly removed code using uninitialized memory as part of an entropy pool: CVE-2008-0166
Parent is right. Use of uninitialized memory is UB, and incidentally, the type of UB that the C standard is not working to define, but is relying on sanitizers to find in source programs, since it is considered always a bug.
This entire thread has a lot of "no security issues have ever been found in my code, and I test a lot. Therefore no bugs will ever exist in my code and we're all safe." To see you doing this in an explicitly security-conscious setting is distressing.
If anything, I see assertions like this and juxtaposed with blatant, willful misunderstanding of how C and C compilers work and it does the opposite of inspiring confidence.
Look at CVE-2009-1897; this is the classic example of how C compilers are happy to try to optimize code in the face of UB and lead to worse problems.
If the above code has any but one of the above 16 outputs
I don't think you understand how insane optimizations in the face of UB can be. Just go look at this issue:
Remember that a compiler is allowed to do anything when it sees undefined behavior, which includes doing the thing you want it to do.
Here's a little example of code disappearing due to a read of uninitialized memory:
void test(int x) {
int uninit;
puts("hello");
if (uninit)
puts("non-zero");
else
puts("zero");
}
clang 23.1.0 -O3 targeting ARMv8 deletes both branches of the if. Not only that, it deletes the code to return from the function. The very last instruction of the function is `bl puts`, meaning that after puts returns, it will start executing whatever function happened to come after this one in memory. That's probably a good thing in context, because that's likely to crash or infinite loop and make it clear that something went badly wrong, but the failure could easily be something more subtle that just disables some random seeding while otherwise executing normally.
Yes, /dev/(u)random is supposed to do that, [...] getrandom() is often times suggested, but alas isn’t a standardized function, i.e. it’s not part of the POSIX specification.
Is /dev/random or /dev/urandom part of the POSIX specification?
Neither one is last time I looked. I’m a lot more uptight about POSIX compliance with code that needs to compile than I am with code that just needs a special /dev file to run, for the simple reason, when using POSIX during the compile stage, I can place the blame on GCC and/or clang if the program doesn’t compile when my program is POSIX and C99 compliant (I was, like many, burned by the C23 changes which made a lot of code which previously used to compile no longer compile).
I actually at one time had a Windows binary which would use Windows proprietary calls to make a “urandom” file (secret.txt was its name) so people could have good entropy on systems using the exact same interface as fopen("/dev/urandom","rb") (i.e fopen("secret.txt","rb")) without needing an actual /dev/urandom.
Refusing the platform's CSPRNG for such nonsense reasons is perhaps the dumbest form of POSIX worship. This is obviously an area where platform feature detection makes sense, there's no reason to follow a religion of standards adherence when it directly leads you into harm's way
Yes, on any modern system you should use the kernel provided random number sources.
The only legitimate reason to roll your own is when you're developing for an embedded system or a bootloader or something like that where there is no kernel API available.
The code I wrote has been used by embedded developers in embedded spaces; I remember getting a bug report from someone in China because they used my code in an embedded system before the timestamp was correctly set on said system.
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?
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.
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.
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.
Nifty! Out of curiosity, how much different is that from taking several partly-random streams and XORing them together? I always assumed what was going on was essentially a fancier version of that.
Oh, I guess you have to ensure the inputs aren’t correlated, or they’ll cancel out?
The advantage of a secure XOF is that a malicious source of entropy needs to do a good deal more work than a simple XOR to generate controlled PRNG output (the attacker needs to do 2^n XOF operations to generate n bits of PRNG output, and that’s only if the attacker knows the output of all other sources of entropy—someone with that level of access can do far more effective attacks).
The sources of entropy can be correlated and won’t cancel out with a well designed secure XOF. SHAKE-256 is an example of a secure XOF.
Well that very similar to how the Linux kernel does it. The linux kernel does it a little differently in that it uses the chacha8 stream cipher instead of a XOF. The chacha8 stream key is frequently reseeded by hashing the entropy pool with blake2b over the collected randomness from all sources but a lot comes from the nanosecond timing of hardware interrupts. Depending on configuration the blocking rng does not return unless 256 bits of trusted randomness are mixed into the entropy pool.
If anyone is interested in this topic please just read the code[0]. It has a lot of interesting tricks that you would not have just rolling your own.
If you're building a userland XOF RNG to extend the kernel's RNG (that has the same security properties) you are reducing security, not improving it. The kernel has advantages for managing and securing a secret "entropy" pool that you won't replicate in userland.
But if you're using a custom kernel that has a custom KRNG based on an XOF, sure, whatever, I guess.
Looks like they tried 16-bit numbers. Does the odd behavior happen also on 32 and 64 (might take a long time to check - I'd start scratching my head after a couple hundred years of no zeroes) ones? Is the zero masking as some other fixed number, increasing its output count? Is RDRAND implemented as multiple reads of an internal state so that a larger random number takes longer?
Yes, when using either 32-bit or 64-bit number, the lowest portion can output a zero, as I suggested on the attached example file as a modification to fix the problem.
But a true zero (fitting the requested size), on AMD, never happens.
Another person (on page 2) confirms those results on an older AMD processor (but failed to reproduce on a very new one, 9950X3D).
I remember setting up a new git CI build server many years ago, which at the time rather quickly started failing build pipelines in a nodejs css frontend build script, turns out there was something funky with the AMD processor's RDRAND. A motherboard BIOS flash update fixed it.
Embarrassing, but probably little practical impact, since these hardware random numbers are typically not used directly and instead seed a CSPRNG.
According to Theodore Ts there was pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction.
" I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction. To quote from the article below:
"By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors...."
Relying solely on the hardware random number generator which is using an implementation sealed inside a chip which is impossible to audit is a BAD idea. "
https://web.archive.org/web/20180611180213/https://plus.goog...
Putting a backdoor into CSPRNG is a favored way to break crypto, for example Dual_EC_DRBG.
"
Weaknesses in the cryptographic security of the algorithm were known and publicly criticised well before the algorithm became part of a formal standard endorsed by the ANSI, ISO, and formerly by the National Institute of Standards and Technology (NIST). One of the weaknesses publicly identified was the potential of the algorithm to harbour a cryptographic backdoor advantageous to those who know about it—the United States government's National Security Agency (NSA)—and no one else. In 2013, The New York Times reported that documents in their possession but never released to the public "appear to confirm" that the backdoor was real, and had been deliberately inserted by the NSA as part of its Bullrun decryption program. In December 2013, a Reuters news article alleged that in 2004, before NIST standardized Dual_EC_DRBG, NSA paid RSA Security $10 million in a secret deal to use Dual_EC_DRBG as the default in the RSA BSAFE cryptography library, which resulted in RSA Security becoming the most important distributor of the insecure algorithm. RSA responded that they "categorically deny" that they had ever knowingly colluded with the NSA to adopt an algorithm that was known to be flawed, but also stated, "We have never kept this relationship [with the NSA] a secret and in fact have openly publicized it."
"
https://en.wikipedia.org/wiki/Dual_EC_DRBG
It is just possible they decided crypto code that uses it was safer to skip zeros. (Whist mathematically it should be no more likely; it is vastly more likely someone will actually try that key).
It is also possible that their code was generating too many zeros and the easiest fix was to discard them all.
this is not how crypto works
Can you clarify what you mean by "it is vastly more likely someone will actually try that key"?
I'm guessing you don't think there are people calling rdrand in a loop and throwing away the output with high probability except when it is 0, but I can't see how else you imagine people would be vastly more likely to use the output when it is 0?
In lots of scenarios I know the software used to generate the key; the only unknown is the random numbers used. If I am searching for weaknesses it is highly likely I would try keys with different seeds; zero, one, are going to me much more likely choices here then hoping I can guess the right values.
If the keys are selected uniformly at random why are 0 and 1 more likely than other values?
Because I don't want my test keys to be random/none reproducable, instead I will just used fixed seeds to see if any timing etc leeks.
So what has that got to do with rdrand? I literally don't understand what you would get from preventing 0 as output?
If someone was using RDRAND16 to seed a PRNG, choosing to omit one single value (a zero) from the return value would not significantly improve the generated values, if at all.
Looked at another way; leaving out the zero also dosn't significantly hurt. If the is any risk if it breaking the PRNG why take the risk.
The probability of generating a zero is incredibly low if you use the normal distribution curve.
So it is not necessarily that it doesn't generate zero, they did not run enough times to increase the probability of actually generating a zero.
Why would it be a normal distribution?
should be a discrete uniform distribution right?
From what I can see they were trying to generate 16bit integers, so the probability is 1 in 65536 and they were running the test for 11 hours.
You definitely would expect a roughly equal number of 0s as any other of those numbers since it's uniformly distributed. And definitely not 0
How would random numbers be uniformly distributed?
So you think a weighted die is more random than a fair die? A uniform distribution means each outcome has equal probability; it doesn’t mean the outcome is predictable.
Because each number is equally as likely as every other number. If you know you're more likely to get certain numbers, or in this case have no chance of getting certain other numbers, it is by definition _less random_.
No, that has nothing to do with randomness. It is however a different distribution than expected.
Think about the odds of a uranium atom decaying in a given second. Certainly a random event, yet for most seconds, the value is False, not True.
You are both right, the atom decaying is completely random but the distribution of the decays is still predictable.
If you have a random number generator your are relying on the fact that it is uniformly distributed and thus has no bias towards certain numbers. Or if it is not uniformly distributed you would want to know the exact distribution so you can correct for it.
If you have an RNG that is treated as putting out uniformly distributed numbers but it is does in fact favor some numbers over others, that would be a defect that can cause problems/be exploited.
Ah. My reasoning, with the normal distribution, was that zero was at the left most end of the curve and with a pretty much non-existent chance of appearing.
https://en.wikipedia.org/wiki/Discrete_uniform_distribution
With enough repetitions.
With a few (say 10, so 655360 runs), you will not get a uniform distribution, and some numbers (like 0) might not appear.
As the number of samples approaches infinity, the percentage share of all possible results approaches equality. A uniform random distribution is like the mathematical identity of statistics.
This also seems to happen for 16 and 32 bit numbers, so you should be able to see zeros easily.
They also write:
I'm getting 16-bit zeros on my Zen 3 chip (+1:3821, 0:3893, -1:3895), I will wait to get some statistically significant samples for the 32-bit values and update the forum thread. Maybe it was fixed after Zen 2?
Does anyone have access to an HPC cluster with thousands of Zen2 chips? We might want to check 64-bit ones with that - should take just a couple years depending on the size of the machine.
Anyone from the High-Performance Computing Center Stuttgart willing to play on the 720,320 Zen2 cores?
This is not the first RNG bug on Zen 2, I recall after I first got mine that some application or other would quit immediately at startup because rdrand always returned -1, i.e. all 1s. It was fixed with a microcode update.
Do we now learn that they fixed "always generate all 1s" with "never generate all 0s"??
EDIT: I've been unable to reproduce the problem on my CPU, FWIW. It's a Ryzen 5 3600.
EDIT2: OK, update, I can reproduce it with rdrand16, rdrand32 is fine but rdrand16 can never generate all 0s. So my CPU does have this problem!
https://xkcd.com/221/ for those not in the know
And for the full fail story behind it, fail0verflow hacking the PS3 presentation is great and covers the bug: https://youtu.be/DUGGJpn2_zY
Most of the console hacking talks are great, both informative and entertaining.
This comic predates that presentation, in fact they use it in their slide deck at 39:00 in your linked video.
That presentation is awesome though, worth a watch either way!
The comic postdates the PS3 DRM bug and jailbreak by many, many years.
That seems impossible (unless maybe you meant to write "predates", and even then it seems to only be about 3 years).
The comic was published on 9 February 2007 [0].
The PS3 was first released in November 2006. I haven't watched the video yet, but its description says "2010 saw the first hacks for the Playstation 3".
[0] https://xkcd.com/221/info.0.json
https://i.imgur.com/bwFWMqQ.png
CVE-2008-0166 (Debian OpenSSL Predictable PRNG Vulnerability) inspired xkcd/221 but this sort of thing happens a lot :)
I always think of https://www.reddit.com/r/ProgrammerHumor/comments/5yhl93/ran...
Does rdrand32 and then taking the lowest 16 bits of its result yield any zeroes?
Basically I'm wondering if it's a bug in the version of the instruction that writes to a 16-bit reg, or a bug in the underlying RNG
Yes it does. rdrand32()%65535 was my first attempt, and generated zeroes at about the expected rate, that's why I initially erroneously thought my CPU did not have this problem.
How about* rdrand32()%65536? Taking the remainder by 65535 doesn't take the lowest 16 bits after all
*: missed a word the first time around
You should be using &0xFFFF for masking. Your mod is off by 1 too.
You're right, the code was correct but my comment above is wrong.
You probably recall https://news.ycombinator.com/item?id=19848953 .
Even if you reproduce the issue, it is not a proof it can't generate a zero - just that it's very unlikely.
To prove it, we'd need to examine the chip and its microcode.
Zen 4 reporting in. I'm unable to reproduce it (7840U).
I used the GCC intrinsic ( _rdrand16_step ),
I can reproduce it too with rdrand16 on Zen2.
But it looks like the rdrand16 instruction can produce zeros just fine, it just sets CF=0 erroneously (indicating an error and that the user program should retry).
So keep that in mind when you try to reproduce it too and use some abstraction that could implement retries internally.
Good observation, that seems like the most likely explanation. Do you ever see "true" CF=0 (with nonzero arg) or did they just take the lazy approach?
No, CF=0 occurences seem to be happen frequently and uniformely distributed like valid results at ~1/65536, not clustered. Under a minute-long all-core load CF=0 always produces zero, but that's to be expected according to the manual.
Here are some stats:
I used this C program to collect them:
Funny. Look up errata AMD-SB-7055: RDSEED Failure on AMD “Zen 5” Processors.
Zen 5 rdrand16/32 return zero with CF=1 on entropy exhaustion and their recommended approach directly leads to the issue you observed: treat all-zero result of rdseed as if cf=0 (failure) and re-roll the dice, effectively recreating the zen 1/zen 2 issue all over again!
They say this might be addressed by a future microcode update… meaning there’s a chance they’ll just patch it to do just that in software. Maybe that’s how they got into this mess in the first place?
Also, am I a complete idiot or is asserting the relative distribution of a mere 64k possible results a rather easy black box validation test that I would’ve assumed they’d be doing? When I used to write cycle-accurate emulators in the past, that would have been an obvious test to include. This isn’t some arcane instruction no one uses or a really complicated case with deep dependency and/or timing issues; it’s like getting rdtsc wrong.
If I remember correctly, we had a setting in every Linux server we owned to remove CPU as a RNG seeder for the kernel because of those bugs with AMD CPUs.
I.e., we had `random.trust_cpu=off nordrand` in `GRUB_CMDLINE_LINUX`.
Adding bad randomness can't degrade good randomness, can it?
I thought the kernel would not replace anything just because it adds a potentially bad source.
E.g. if you have rand source A, and xor it with rand source B, then you get, at worst, the best of A and B,
As far as I know that is correct; the kernel was written in a way such that one bad source doesn’t poison the pool. Still, if you know one source is bad, might as well take it out.
Why? That would actually reduce randomness. The value of adding sources to the entropy pool has a floor of zero. Worst case scenario, it just provides no extra entropy.
You don't know if it's bad. Microcode updates might fix it, or break it for that matter. Revision history can be difficult if not impossible to comprehensively catalog.
What it is is unreliable. And that's fine so long as you have other entropy sources. OpenBSD is really good about this. Quite a few drivers for various chipsets and cards exist just to read their RNGs, not actually use them for their primary function (which can be a bummer if you want to use the the device, get your hopes up when you see the driver exists in the tree, then discover the only capability it supports is reading the RNG). If you have a CPU with a known bad rdrand, odds are OpenBSD is still sourcing strong randomness from some other chip in your system (PSP, NIC, etc). And because feeding bad (as opposed to malicious[1]) entropy is harmless[2], they don't have to maintain a pile of conditions. Nobody is worse off, and overall everybody is better off, including having stronger getrandom/getentropy output, by not trying to be clever.
[1] https://blog.cr.yp.to/20140205-entropy.html
[2] Presuming nothing is relying on an entropy estimator. I can't remember if Linux finally moved past the entropy estimator nonsense. IIRC they did add a software jitter RNG that runs early to try to set a minimum entropy floor, regardless of hardware sources.
Well, if you literally have nothing else, then you don't have an option anyway, so the whole question is moot.
Except yeah if literally the only way to collect entropy in your system is the platform's opaque RNG, then sure this means your risk assessment should list that as a SPOF. But by definition these cases only have that option, so you can't do anything else.
In reality, you can probably do something else in all but the most extreme embedded environments.
Yes and no. Mostly no.
In a simplified model, it's only useless if it adds zero bits of entropy. But if a source that's supposed to add 128 bits of entropy only adds 16, well, it's still 16.
I would never trust RDRAND on its own. If nothing else because it's always subject to a microcode backdoor. But if I already have something I'm happy with the entropy of, sure, I'd XOR it with RDRAND output. It cannot make it worse.
this is generally true however if an adversary is able to control a source it becomes dangerous if they can preview the results or inspect the other sources.
Not to the kernel random pool, no.
this is a well known attack...
if your algorithm controls a source of entropy and can inspect the other sources, it can craft its source to bias the result. a fanciful attack but it means you should at least discriminate what you put into the pool.
Can you link to the paper you're thinking of? Maybe people are just talking past each other here. A biased random source can't bias the kernel random pool in any straightforward kind of way.
I explicitly said
because the malicious source can just precompute the hash for the bias it wants.
https://blog.cr.yp.to/20140205-entropy.html
Right, so your starting point is that the attacker has read-only access to ALL entropy sources, and in that scenario it's worse if the attacker has read-write access to one entropy source.
Yes. I don't find this a particularly interesting scenario, though. Sure, we can come up with stuxnet-like airgap attacks where we on-device, but not remotely, can read entropy sources. AND we can modify the output of RDRAND. And there keys have been generated for data we can later intercept. But despite that control (potentially on a CPU microcode level) we are unable to stegonographically leak it?
Sure. Possible. Has it ever happened?
Careful, there is two different things going on here:
a) whether you use the maybe-entropy provided by the CPU (and/or the bootloader)
b) whether you credit that maybe-entropy towards your tracking of whether the pool should be considered sufficiently seeded
random.trust_cpu/random.trust_bootloader configures b).
nordrand has been removed from the kernel as it had become overloaded by meaning both a) and b)
Under most circumstances, a) is harmless. You mostly want that off when the CPU exhibits some performance hiccups when asked.
Under some circumstances, b) is outright dangerous. Some applications can work without seeded pool at some slightly reduced performance, but could be made to fail miserably if they had been made to believe that the pool was seeded yet it was not. This happens with hash tables when you skip some of the accounting because it seems no longer relevant. It really would not be relevant, once even a determined attacker should be unable to reliably trigger the worst-case-performance.
With the assumption that sources A and B are independent from each other.
Sure. In general this is a very important factor.
In the context of this topic, it's a bit pedantic.
Usually you do "rdrand % <some-number>" anyways, and in that case you will still get zeroes. True, your result might be skewed by 1/(maxint/some-number) but I guess that's not a big problem in practice
If you want uniformly-distributed random numbers, computing the remainder works only when the modulus is a power of two.
Otherwise, a slightly more complicated algorithm is necessary, where you reject a range of numbers either before computing the remainder (to make the set of possible values a multiple of the modulus) or after computing the value modulo some power of two (to reject values greater than your target).
Besides these 2 variants based on the remainder of division of integers, there are also 2 corresponding algorithms using multiplication of the input interpreted as a fraction, followed by taking the integer part of the result.
I always wonder how hardware bugs like this happen with the sheer amount of hardware validation that's done. It'd be fascinating to know how it slipped through the cracks, though I know almost nothing about this side of the industry sadly
The verification plan did not make 0 a bin to cover.
That "sheer amount of hardware validation" is always less-than-perfectly spread across a whole lotta billions of transistors, and combinatorics is a harsh mistress.
Almost definitely an off by one bug.
Validation can't be better than the quality of the specification. Humans don't create comprehensive, unambiguous specifications for the same reasons that we don't write bug-free code, and need formal validation.
Brooks talks about this in _Mythical_Man-Month_... if you really could "just implement the specification", then the specification itself would be complete enough to serve as your code. There will always be bugs in both.
Me too. Hardware bugs that arise out of unanticipated module interactions are understandable. But this is a "you had one job" moment.
So what? The point is to be non predictable not to pick all the numbers in the range with exactly the same probability. Would it be a problem if it never generated 16542?
What are you talking about? The point is in fact to pick all the numbers in the range with exactly the same probability.
See section 7.3.17 of the Intel SDM, and how NIST SP800-90A (which the SDM refers to) defines "random number".
Consider an 8-bit RNG.
By your argument, it would not be a problem if the RNG never generated 0. So, it must follow that it would also not be a problem if it never generated {1, 2, 3, ..., 253}.
That means that our RNG now only generates the values 254 and 255. Which of the values is generated is unpredictable on any given call. However, 7 of the 8 output bits are now always fixed and so completely predictable. Can you imagine how an attacker could exploit that?
Failing to generate only the number 0 is a weaker version of the same class of flaw.
This is the “what’s the big deal if I lost $100k in a casino, it’s really the same thing as if I had lost $5” argument.
I don’t think you can rebut “you only lose one of many values” with “it’s the same as only having one left”.
We're talking about whether a modification of the expected probabilities changes the dynamics of the game. The example I gave was deliberately extreme, because that makes it easier to reason about.
If you want a casino example, then consider a roulette wheel that always lands on 36 but still pays out as usual. I think you'd want to play on it. Now consider one that always lands somewhere between 30 and 36. Still worth it, right? With careful bets and a good starting float you're still coming away from the table up (with a very high probability).
In fact for a roulette wheel you only need two dead pockets for the player to get an edge. Bias is exploitable.
Sure, but you’re pressing on the truth that a small modification taken to an extreme is a large modification.
When the original point was that a tiny fractional loss in an RNG is not going to make a practical difference. Which I believe is also true. And it is also true that a large loss in an RNG is catastrophic.
They can both be true.
And roulette is 2 out of 38, 5.2%. That’s 17 times more than the 1/256 here, which was already a simplification of the (I think) 1/65536 in question.
With respect, I think you're still missing my point, which is simply that bias introduces vulnerability. Without a real scenario to analyze, the scale doesn't really factor into the argument. A vulnerability is a vulnerability until proven mitigated.
I'm not so sure this is true. I don't think either of us is in a place to say whether this vulnerability has practical applications or not. A 1/65536 bias might seem like nothing important to you. It seems like potentially something to me, in a world where the attacker might control the volume of data generated.
The value space goes from 2^16, 2^32, 2^64 to 2^16 - 1, 2^32 - 1, and 2^64 - 1 respectively.
The bug has zero practical impact.
It is absolutely untrue that a biased RNG has "zero practical impact." Modern cryptography has plenty of examples of relatively small biases leading to breaks. Check out Bleichenbacher's attack, for instance.
You could be correct that the very small bias here is not enough to be exploitable. But, given the history around this, it would be wrong to handwave it away as trivial.
It certainly does not.
A never-zero RNG is something one should know about, so that it can be mitigated if necessary, but it's not inherently a dealbreaker.
Betty from accounting will have words.
What does Betty from accounting care about RNGs?
There's an edge case somewhere that will affect a real user when you can't get a zero. Forecasting simulations perhaps?
That may well be a problem, yes.
“Predictable” and “not pick all numbers in range with exactly the same probability” are synonyms here.
"Random" is used by most people to mean "random with an even distribution".
A weighted die is still random, but with an uneven distribution. This is effectively a 2^16-sided, weighted die.
My argument to follow your analogy is.
It's not a 2^16-sided weighted die. But a 2^16 - 1 sided fair die.
I am not saying there is no bug. I am saying the bug has no practical impact.
Sure if you are that one guy that is getting these values raw from the instruction and comparing to zero for some purpose then you are in trouble. But I am pretty sure no one is doing that, especially given that the bug surfaced after 6 years of millions of users.
I can imagine someone doing a
where these are not equally likely anymore (I may have an off-by-one anyway ;)).
“Pick all the numbers in the range with exactly the same probability” is a very important property of RNGs. Yes, skipping 16542 would be equally bad.
You can frame it around being “non predictable”, but then you need to define those words. It’s not, for example, a poker game where it’s trying to bluff you, right? It’s also not about just making predictions < 100% reliable and declaring victory. It must specifically make all predictions no better than random guessing, and that entails picking any number in range with equal probability, otherwise predictions like “it will be {hot spot}” or “it won’t be {cold spot}” do better than random chance. In this case, specifically, I can predict with 100% accuracy that the result won’t be 0, and that’s a flaw in its unpredictability. I can also predict a bunch of other things with slightly higher accuracy than random guessing, like that it will be odd or greater than max ÷ 2.
https://www.amd.com/en/resources/product-security/bulletin/a...
The OP says they discovered this on a Zen 2, which is not covered by that bulletin (?)
[edit to add]: Also, the bulletin is solely about RDSEED zeros, whereas the OP is also reporting RDRAND zeroes.
Older AMD processors had issues as well:
https://github.com/systemd/systemd/pull/12536/commits/1c53d4...
That one's insidious!
I found the thread about it,
https://news.ycombinator.com/item?id=19848953
Yikes at this: "I am so glad I resisted pressure from engineers working at Intel to let /dev/random in Linux rely blindly on the output of the RDRAND instructure." -Theodore Ts'o (2013)
Why does systemd use architecture-specific instructions rather than using the kernel-provided random interface in the first place?
It was removed later https://github.com/systemd/systemd/commit/ffa047a03e4c5f6bd3...
Chased a similar bug in a KDF once and only caught it by histogramming the 16 bit draws, statistical suites never flagged it.
Your suites didn't even do a https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_tes... which is what you did?
0 is not a number, it's undefined
the what?
That's a thing some people used to believe, I guess some of them still do.
Are you a time traveler from the 5th century?
It is literally the first Peano axiom that 0 is a natural number. In fact it is the only natural number that is defined in and of itself. All other natural numbers are defined by using the “successor” operation to add things to zero.
https://en.wikipedia.org/wiki/Peano_axioms
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.
Isn’t this effectively what systems like /dev/(u)rand do? Pool multiple random sources together to hedge against these things?
I fail to see why one should either rely on a single random source nor roll their own.
Yes, /dev/(u)random is supposed to do that, but what if there’s a bug in a kernel (e.g. some embedded system which may not even be running Linux) which causes /dev/(u)ramdom to be less than secure? There’s also issues where, for example, it may no longer be possible to read /dev/(u)random after putting the process in a chroot() sandbox (chroot() isn’t defined in POSIX so its behavior is not guaranteed to be consistent across multiple operating systems).
getrandom() is often times suggested, but alas isn’t a standardized function, i.e. it’s not part of the POSIX specification. Considering how the C23 changes to the C specification caused a lot of perfectly good C code to no longer compile, I’m very anal about sticking to specs; I use '-std=C99' for my code these days (even though it can compile as C23 code) and stick to POSIX functions (except chroot() and setgroups(), but both of those predate POSIX, and even here I have a compile-time option to compile my code without those non-POSIX syscalls).
The code using a secure XOF (the algorithm was developed by the same team which later on made SHA-3, and includes people who helped make AES) has been around for nearly two decades (the code where I roll my own RNG to make secure random numbers has been around for over 25 years, but used AES before XOFs existed) and not one security problem has found with the RNG code has ever been found. [1] “Don’t roll your own RNG” is a suggestion, but it is possible to do so securely if one knows what they are doing (i.e. they have read Applied Cryptography and keep current with cryptographic developments).
For anything vibe coded (my code is 100% human written, for the record), rolling one’s own RNG is a really bad idea.
[1] There was a theoretical issue with cache timing attacks over two decades ago, so I put mitigations in place, and then chose to use an XOF for newer code.
[2] There was an issue where a separate implementation I made of this XOF would generate incorrect test vectors in clang, but only at some optimization levels. I now test the XOF in both GCC and clang at multiple optimization levels to make sure it acts correctly.
so instead you suggest trusting your own untested unlooked at implementation more?
No you see what we do, Is we ask Claude to make no mistakes in implementing the CSPRNG. This way we ensure there are no mistakes in the implementation or mathematics.
https://xkcd.com/221/
I know it’s a joke, but that code wouldn’t pass the DieHard tests. That’s actually one of the tests I did with the XOF I used, a test I ran over 16 years ago.
https://maradns.blogspot.com/2010/07/radiogatun32-passes-all...
Black-and-white thinking like this is always inaccurate.
The automated tests includes tests that make sure the XOF is correctly implemented. [1]
People have been looking at my code for security holes for well over 20 years, and I have been getting multiple AI assisted security reports over the last year, things like “there’s a buffer overflow in this code which is nay to impossible to exploit, using code which hasn’t even been able to compile since 2022”.
[1] https://github.com/samboy/MaraDNS/tree/master/deadwood-githu... and https://github.com/samboy/MaraDNS/tree/master/deadwood-githu...
XOF correctly implemented doesn’t ensure you haven’t made other mistakes, such as using entropy sources correctly, doing needed math correctly to avoid any entropy bias, etc. etc….
You’re correct about black and white thinking. Then you invoke multiple straw men in this thread to defend that you’ll roll your own.
Disclaimer: I’ve been hired for multiple DoD projects to break hardware and software security systems, and I nearly always succeed, because so many people (and companies) roll their own.
The nice thing about a secure XOF is that it doesn’t matter if the entropy given to the XOF is less than perfect. If an XOF is given 10 different sources of entropy, and only one of them is secure, the XOF will remain secure. [1]
One reason why I don’t change the RNGs used in my code is because I know how dangerous playing with RNG code is. For example, one implemention I wrote of the XOF—not one I used in production code, mind you—generated incorrect vectors, but only in clang and only at some levels of optimization. Needless to say, I now have a test to make sure my XOF code generates correct vectors with both GCC and clang at multiple different optimization levels.
People have brought up CVE-2008-0166 in this thread, but the Coldcard incident from this year (where people literally lost millions of dollars) also comes to mind, so I’m aware how dangerous playing with RNG code is.
That’s why the code is basically the same code I had 18 years ago, and why I (as well as multiple people running AI-assisted security audits) have extensively tested that code.
The proof is in the pudding: No security issues have ever been found with the XOF PRNG, and it’s been nearly two decades.
(I also think “straw men” is being used incorrectly here; most likely the parent poster thinks I was implying that Linux’s /dev/urandom is insecure but the actual argument is that my code runs on a lot more than just Linux, and some of those systems could have an insecure /dev/urandom)
[1] As per https://blog.cr.yp.to/20140205-entropy.html as long as we’re not using a malicious source of entropy, but said malicious source will need to perform 2^n operations of the XOF to generate n bits of controlled output, and only in the case if said malicious entropy source can somehow know the output of the other entropy sources, especially since the XOF is seeded once then run indefinitely in my code.
Isn’t that also true of the cryptographic sponge function that is used to implement /dev/{,u}random?
i remember some linux kernel dev got ousted by the community because he/she wanted to not implement a backdoor that would compromise the results of /dev/urandom.
Who?
I have no idea about the claim of a backdoor. But here is the source:
Matt Mackall: "It's worth noting that the maintainer of record (me) for the Linux RNG quit the project about two years ago precisely because Linus decided to include a patch from Intel to allow their unauditable RdRand to bypass the entropy pool over my strenuous objections. "
https://cryptome.wikileaks.org/2013/07/intel-bed-nsa.htm?utm...
That doesn’t read like a backdoor or like the community pushing somebody out.
The fact that Intel Bull Mountain (code name for Secure Key Technology), and NSA's BULLRUN program share the name "bull" is a complete coincidence. I'm sure.
You know there are people who actually reason this way.
The POSIX standard function is getentropy(), which internally calls getrandom() on Linux.
It's often the other way around: the Linux kernel contains thousands of workarounds for buggy hardware, while the buggy hardware itself doesn't always get patched. Linux developers take this stuff very seriously. As a result it's often safer to rely on kernel APIs than to access the hardware directly.
The kernel code involving random number generation receives an exceptionally high amount of scrutiny because of its security implications, so I'd trust it to do the right thing over a naked call to RDRAND which nobody knows how exactly it's implemented in proprietary hardware or a handrolled solution to mix the RDRAND output with other entropy sources.
Remember the Debian openssl disaster from 2008? That happened exactly because someone had handrolled their entropy mixing solution, then someone else broke it.
From https://pubs.opengroup.org/onlinepubs/9799919799/functions/g...
“The intended use of this function is to create a seed for other pseudo-random number generators”
So, if I were to use genentropy() in a POSIX-compliant way, I would need to do what I already do: Use my own pseudo-random number generator.
The Debian openssl disaster (CVE 2008-0166, I remember it well) was caused because someone incorrectly patched secure code: Since the code used uninitialized memory as one of many entropy sources, which causes Valgrind to complain, they patched the code to not use uninitialized memory for entropy, but then accidentally disabled all other sources of entropy (except the 16-bit PID). It was caused because the person making the patch didn’t fully understand why it was a good idea to, in that context, use code which Valgrind complained about. [1]
As an aside, here’s how I deal with those Valgrind errors:
I do believe the Linux Kernel does have secure RNG code, but I also write code which has run on a lot of different systems and environments, including embedded ones, and some of them might not have a secure /dev/urandom.
[1] Debian has a lot of inflexible policies like this which can cause problems. Another issue Debian has is they have a policy a given piece of code must always compile to the same binary on a given architecture. That isn’t true with the unpatched version of my code, because the hash compression routine uses a 32-bit random number generated at compile time to avoid hash collision attacks (it also uses another 32-bit random number at runtime, and I make sure the hash compression values are never visible). So the Debian version of my code was forced to be patched to be less secure.
Uninitialized memory should never be used as source of entropy. Most release software these days compiles using hardening flags, which will (at some levels) replace uninitialized memory with sentinel values, making the entropy of uninitialized memory frequently around 0.
But it gets worse. If the optimizer sees that you're loading uninitialized memory, it can reason that since the result of uninitialized memory is garbage, doing any computation on that result is also garbage, and happily delete said computation as a result. The cascading effect of this is to delete all of the entropy-mixing code, leaving your entropy pool with only the very low entropy source--giving uninitialized memory effectively negative entropy.
The net effect is that, at least for me, seeing someone trying to seed an entropy pool with uninitialized memory is a giant neon flashing sign saying "do not trust this code." It provides at best very little entropy and at worst actively destroys entropy and has other calamitous effects like valgrind or sanitizer errors, so you need to have other entropy sources anyways, so why bother?
If the optimizer sees that you're loading uninitialized memory, it can reason that since the result of uninitialized memory is garbage, doing any computation on that result is also garbage, and happily delete said computation as a result
This is an interesting assertion, and one that is easy enough to prove true.
Let’s take the following C code, which uses the same XOF algorithm (but not implementation) as my application (Deadwood):
This code, as I’m sure the parent poster can clearly see, uses four bits of uninitialized allocated memory as its source of entropy. As per the parent’s assertion, there should therefore exist a compiler whose optimizer will cause this XOF to not correctly run.
The above code can have one of the following possible 16 outputs:
If the above code has any but one of the above 16 outputs, this is a real world case where a C compiler, seeing uninitialized memory being used, optimizes out the code which uses said uninitialized memory as an input, and therefore will not output one of the above 16 possible words.
I’ve tested the above code in GCC -O3 and clang -O3; both generate one of the above 16 possible outputs (each one generating a different output).
If there really is a compiler out there which does “happily delete said computation”, which would give a different output than one of the 16 outputs above, please name that compiler, the version of said compiler used, and all compile-time flags used with said compiler.
While I’ve never heard of a real world case where a compiler would refuse to run code using uninitialized memory as yet another source of entropy for a secure PRNG, I do know of a real world case where a very nasty security hole was caused because someone incorrectly removed code using uninitialized memory as part of an entropy pool: CVE-2008-0166
Parent is right. Use of uninitialized memory is UB, and incidentally, the type of UB that the C standard is not working to define, but is relying on sanitizers to find in source programs, since it is considered always a bug.
This entire thread has a lot of "no security issues have ever been found in my code, and I test a lot. Therefore no bugs will ever exist in my code and we're all safe." To see you doing this in an explicitly security-conscious setting is distressing.
If anything, I see assertions like this and juxtaposed with blatant, willful misunderstanding of how C and C compilers work and it does the opposite of inspiring confidence.
Look at CVE-2009-1897; this is the classic example of how C compilers are happy to try to optimize code in the face of UB and lead to worse problems.
I don't think you understand how insane optimizations in the face of UB can be. Just go look at this issue:
https://github.com/llvm/llvm-project/issues/174844?utm_sourc...
Remember that a compiler is allowed to do anything when it sees undefined behavior, which includes doing the thing you want it to do.
Here's a little example of code disappearing due to a read of uninitialized memory:
clang 23.1.0 -O3 targeting ARMv8 deletes both branches of the if. Not only that, it deletes the code to return from the function. The very last instruction of the function is `bl puts`, meaning that after puts returns, it will start executing whatever function happened to come after this one in memory. That's probably a good thing in context, because that's likely to crash or infinite loop and make it clear that something went badly wrong, but the failure could easily be something more subtle that just disables some random seeding while otherwise executing normally.
Is /dev/random or /dev/urandom part of the POSIX specification?
Neither one is last time I looked. I’m a lot more uptight about POSIX compliance with code that needs to compile than I am with code that just needs a special /dev file to run, for the simple reason, when using POSIX during the compile stage, I can place the blame on GCC and/or clang if the program doesn’t compile when my program is POSIX and C99 compliant (I was, like many, burned by the C23 changes which made a lot of code which previously used to compile no longer compile).
I actually at one time had a Windows binary which would use Windows proprietary calls to make a “urandom” file (secret.txt was its name) so people could have good entropy on systems using the exact same interface as fopen("/dev/urandom","rb") (i.e fopen("secret.txt","rb")) without needing an actual /dev/urandom.
Refusing the platform's CSPRNG for such nonsense reasons is perhaps the dumbest form of POSIX worship. This is obviously an area where platform feature detection makes sense, there's no reason to follow a religion of standards adherence when it directly leads you into harm's way
Yes, on any modern system you should use the kernel provided random number sources.
The only legitimate reason to roll your own is when you're developing for an embedded system or a bootloader or something like that where there is no kernel API available.
The code I wrote has been used by embedded developers in embedded spaces; I remember getting a bug report from someone in China because they used my code in an embedded system before the timestamp was correctly set on said system.
You can effectively achieve the same result with this simple operation:
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.
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.
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:
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?
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:
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.
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.
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 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.
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?
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...
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.
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).
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.
And to show my objections are not just theoretical I wrote a little program to check:
On my system this prints:
So no, 50 iterations of that loop does not provide 256 bits of entropy due to random fluctuations in nanontime between calls.
Thanks for writing that code!
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.
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:
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.
-----
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
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.
There are theoretical issues where a malicious source of entropy could control the PRNG output, but it’s not a very practical attack.
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.
Oh yeah, if your hardware is malicious you are pretty much F'd.
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.
If a deliberate covert channel is the best thing you can come up with from a vulnerability, you usually don't have much of a vulnerability.
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.
Unfortunately you are not correct, and djb explains it quite well here:
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.
Indeed, that’s a real attack.
From that page:
* 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.
Nifty! Out of curiosity, how much different is that from taking several partly-random streams and XORing them together? I always assumed what was going on was essentially a fancier version of that.
Oh, I guess you have to ensure the inputs aren’t correlated, or they’ll cancel out?
The advantage of a secure XOF is that a malicious source of entropy needs to do a good deal more work than a simple XOR to generate controlled PRNG output (the attacker needs to do 2^n XOF operations to generate n bits of PRNG output, and that’s only if the attacker knows the output of all other sources of entropy—someone with that level of access can do far more effective attacks).
The sources of entropy can be correlated and won’t cancel out with a well designed secure XOF. SHAKE-256 is an example of a secure XOF.
Well that very similar to how the Linux kernel does it. The linux kernel does it a little differently in that it uses the chacha8 stream cipher instead of a XOF. The chacha8 stream key is frequently reseeded by hashing the entropy pool with blake2b over the collected randomness from all sources but a lot comes from the nanosecond timing of hardware interrupts. Depending on configuration the blocking rng does not return unless 256 bits of trusted randomness are mixed into the entropy pool.
If anyone is interested in this topic please just read the code[0]. It has a lot of interesting tricks that you would not have just rolling your own.
[0]https://github.com/torvalds/linux/blob/master/drivers/char/r...
If you're building a userland XOF RNG to extend the kernel's RNG (that has the same security properties) you are reducing security, not improving it. The kernel has advantages for managing and securing a secret "entropy" pool that you won't replicate in userland.
But if you're using a custom kernel that has a custom KRNG based on an XOF, sure, whatever, I guess.
I have a couple questions:
Looks like they tried 16-bit numbers. Does the odd behavior happen also on 32 and 64 (might take a long time to check - I'd start scratching my head after a couple hundred years of no zeroes) ones? Is the zero masking as some other fixed number, increasing its output count? Is RDRAND implemented as multiple reads of an internal state so that a larger random number takes longer?
That first question is answered in the thread:
Another person (on page 2) confirms those results on an older AMD processor (but failed to reproduce on a very new one, 9950X3D).
I would be very concerned if an RNG simply produced a natural 0.
I would be very concerned if an RNG simply produced a natural 1.
I would be very concerned if an RNG simply produced a natural 0xf379aa46d1086bca.
I would be very concerned if an RNG simply produced a natural 2.
Why would that be any more concerning than the RNG producing any other number?
"Maybe some C?O person executed RDRAND"
is an amusingly gross misunderstanding of what a C?O person does on a daily basis.
I wonder if this, or something like it, is the issue:
(From this page I found while trying to see if this was a common flaw in PRNGs: https://www.pcg-random.org/other-rngs.html )
I remember setting up a new git CI build server many years ago, which at the time rather quickly started failing build pipelines in a nodejs css frontend build script, turns out there was something funky with the AMD processor's RDRAND. A motherboard BIOS flash update fixed it.
https://github.com/sass/libsass/issues/3151