AMD's random number generator can't generate a 0?

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

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.

    > it becomes dangerous if they can preview the results or inspect the other sources

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.

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):

  #include<stdio.h>
  #include<stdint.h>
  #include<stdlib.h>
  #define b(z) for(c=0;c<z;c++)
  uint32_t c,e[42],f[42],g=19,h
  =13,n[45],i,j,k;void m(){j=0;
  b(12)f[c+c%3*h]^=e[c+1];b(g){
  i=c*7%g;k=e[i++];k^=e[i%g]|~e
  [(i+1)%g];j=j+c;n[c]=n[c+g]=k
  >>j%32|k<<-j%32;}for(i=39;i--
  ;f[i+1]=f[i])e[i]=n[i]^n[i+1]
  ^n[i+4];b(3)e[c+h]^=f[c*h]=f[
  c*h+h];*e^=1;}int main(int c,
  char**v){char*q=malloc(2);if(
  q==0)return 0;q[0]&=31;q[0]|=
  1;q[1]=0;for(;;m()){b(3){for(
  j=0;j<4;){f[c*h]^=k=(*q?255&
  *q:1)<<8*j++;e[c+16]^=k;if(!
  *q++){b(18)m();b(8){j=c;b(1)
  printf("%02x",(e[1+j%2]>>8*c)
  &255);c=j;if(c%2)m();}puts(
  "");return 0;}}}}}

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:

  0a5d51f3745c7266
  f84b051f67115f1a
  f87105c4ecfefe67
  92074ac8e1e7a42e
  1441ac245f288e18
  87023372e57ae001
  047a3ddd14209546
  340b2ff47c61172e
  bfb9289ed096f977
  dfd56a7a8d7d723e
  2151460954a80242
  6822335c6e0160dc
  3783ce3cae3d0774
  4e0156df46c00bac
  69795d939d211e7a

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

    void test(int x) {
        int uninit;
        puts("hello");
        if (uninit)
            puts("non-zero");
        else
            puts("zero");
    }

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.

That doesn’t read like a backdoor or like the community pushing somebody out.

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

  Android SecureRandom (2013)

  CryptoJS / Ill Bloom (2026)

  Trust Wallet Browser Extension (2023)

  Libbitcoin / Milk Sad (2023)

  Trust Wallet iOS / Trezor Library

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

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.

The reason that you get 3-4 bits of entropy per hash is because of the fundamental nature of CPUs. In addition to having considerable professional experience with cryptography, I also have considerable professional experience with hardware; hardware is fickle as hell, especially when your transistors are tens of nanometers large. Every time you flip a bit, you expend some energy, which heats up the chip, and the heat changes the timing of the next clock cycle. Chips are composed of literally billions of transistors, and each one is going to have a different temperature, because clock cycles last less than a nanosecond (well, embedded hardware is slower but the same idea still applies reliably) and that's not enough time for temperature deltas to dissipate across the chip.

Hashing is particularly chaotic because it lights up a different set of transistors on each clock cycle, which means the hotspots on the chip are being jerked around. Some transistors are going to light up 5-10 times in a row, and others are going to be idle 5-10 times in a row, and then randomly that changes. And all of this changes the number of picoseconds that it takes for a clock cycle to complete, which means that each clock cycle is genuinely going to take a different amount of time to complete, and stuff like temperature throttling is completely not at play whatsoever, because we're not talking about chip-wide temperatures, we're literally talking about temperature deltas between transistor a and transistor b.

That makes it a really wonderful source of entropy for cryptographic applications, because the CPU clock is so critical that it's almost never buggy (especially relative to other components that provide entropy), it's also almost impossible to manipulate reliably by an attacker (unless the attacker has an exploit that allows them to set the value of the clock directly - which is possible, but it's a very narrow surface area relative to other entropy sources), and you can completely take advantage of this entropy entirely in userspace, which once again heavily minimizes attack surface area and exposure to bugs.

I have searched far and wide for a CPU that does not reliably generate entropy using the iterated-hashing-against-the-clock method, and I have not found a single example of a CPU that consistently takes the same amount of time to complete a hash. And the reason isn't implementation, the physics of CPUs simply insist on introducing entropy when trying to repeatedly hash something quickly.

I ran it 500,000 times, discarding the 10% most entropic results ... in the hopes of arriving at a relatively conservative estimate for the amount of entropy you actually get from each iteration. Here's the prompt I used to generate the code: https://chatgpt.com/share/6ab2df4a-7f94-83ea-aecf-1bb57c4838...

And here are the results of running that code:

  === No hashing ===
  Clock resolution: 0.000000001 seconds
  Clock reads:                       500,000
  Second-difference outcomes:        499,998
  Retained outcomes:                 449,998 (90.000%)
  Average Shannon information:       1.755579 bits/retained outcome
  Marginal min-entropy estimate:      1.339460 bits/retained outcome
  Lag-1 conditional min-entropy:      0.960079 bits/retained adjacent outcome
  Conservative descriptive proxy:    0.960079 bits/retained outcome
  Proxy scaled per clock iteration:  0.864067 bits/iteration
  These are empirical timing statistics, not a proven entropy rate.

  === One SHA-256 between clock reads ===
  Clock resolution: 0.000000001 seconds
  Clock reads:                       500,000
  Second-difference outcomes:        499,998
  Retained outcomes:                 449,998 (90.000%)
  Average Shannon information:       4.205076 bits/retained outcome
  Marginal min-entropy estimate:      3.610848 bits/retained outcome
  Lag-1 conditional min-entropy:      3.351217 bits/retained adjacent outcome
  Conservative descriptive proxy:    3.351217 bits/retained outcome
  Proxy scaled per clock iteration:  3.016082 bits/iteration
  These are empirical timing statistics, not a proven entropy rate.

------------

As GPT helpfully points out, this isn't a proven guarantee, but a reasonable estimate is somewhere between 3 and 4 bits of entropy per hash. That means 50 is actually enough, though if you want to be conservative I don't think there's any harm in doing 500 or even 5,000 instead of 50. And, if you are going to be using this in a hostile environment, it doesn't hurt to also add a fortuna-like accumulator that resets your entropy every once in a while.

I said this in another reply as well, but the reason that you get 3-4 bits of entropy per hash is because of the fundamental nature of CPUs. In addition to having considerable professional experience with cryptography, I also have considerable professional experience with hardware; hardware is fickle as hell, especially when your transistors are tens of nanometers large. Every time you flip a bit, you expend some energy, which heats up the chip, and the heat changes the timing of the next clock cycle. Chips are composed of literally billions of transistors, and each one is going to have a different temperature, because clock cycles last less than a nanosecond (well, embedded hardware is slower but the same idea still applies reliably) and that's not enough time for temperature deltas to dissipate across the chip.

Hashing is particularly chaotic because it lights up a different set of transistors on each clock cycle, which means the hotspots on the chip are being jerked around. Some transistors are going to light up 5-10 times in a row, and others are going to be idle 5-10 times in a row, and then randomly that changes. And all of this changes the number of picoseconds that it takes for a clock cycle to complete, which means that each clock cycle is genuinely going to take a different amount of time to complete, and stuff like temperature throttling is completely not at play whatsoever, because we're not talking about chip-wide temperatures, we're literally talking about temperature deltas between transistor a and transistor b.

That makes it a really wonderful source of entropy for cryptographic applications, because the CPU clock is so critical that it's almost never buggy (especially relative to other components that provide entropy), it's also almost impossible to manipulate reliably by an attacker (unless the attacker has an exploit that allows them to set the value of the clock directly - which is possible, but it's a very narrow surface area relative to other entropy sources), and you can completely take advantage of this entropy entirely in userspace, which once again heavily minimizes attack surface area and exposure to bugs.