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

this is not how crypto works

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.

should be a discrete uniform distribution right?

You definitely would expect a roughly equal number of 0s as any other of those numbers since it's uniformly distributed.

How would random numbers be uniformly distributed?

This also seems to happen for 16 and 32 bit numbers, so you should be able to see zeros easily.

They also write:

Running the same programs on an Intel processor, and the 0's are there with no problem.

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

I think that one is referencing a run of six 9's in the digits of pi, which occur much earlier than one would "expect" them to show up in a truly uniform distribution.

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

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

   $ ./a.out | rg '\b\-?\d\b' | sort -n | uniq -c
   15281 -2
   15192 -1
   15273 0
   15243 1
   15269 2

I used the GCC intrinsic ( _rdrand16_step ),

    #include <immintrin.h>
    
    short rdrand16() {     // gcc -mrdrnd
        short ret;
        while (1 != _rdrand16_step(&ret)) { }    
        return ret;
    }

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.

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

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

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

No. We are not talking about amounts lost, we're talking about probabilities and 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? As in, with careful bets and a good starting float you're still coming away from the table up, with a very high probability.

The point I'm making is that bias is exploitable.

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.

What does Betty from accounting care about RNGs?

That may well be a problem, yes.

Older AMD processors had issues as well:

https://github.com/systemd/systemd/pull/12536/commits/1c53d4...

Chased a similar bug in a KDF once and only caught it by histogramming the 16 bit draws, statistical suites never flagged it.

0 is not a number, it's undefined

Yes, /dev/(u)random is supposed to do that, but what if there’s a bug in the kernel 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.

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?

I would be very concerned if an RNG simply produced a natural 0.