Entropy Loss and Output Predictability in the Libgcrypt PRNG [pdf] (opens in new tab)

How to safely generate random numbers on Windows[1][2]:

  #include <windows.h>
  #define SystemFunction036 NTAPI SystemFunction036
  #include <ntsecapi.h>
  #undef SystemFunction036

  RtlGenRandom(buf, size);

This is more convenient than both rand_s[3] and CryptGenRandom[4]. The former can only generate one byte per call and the latter requires you to create a CSP (cryptographic service provider) before you can call it (which means you have to destroy the CSP when you're done using it). In the end these all call RtlGenRandom.

RtlGenRandom uses a CSPRNG specified in NIST 800-90[4]. It uses AES256 in CTR mode AFAIK.

[1] https://msdn.microsoft.com/en-us/library/windows/desktop/aa3...

[2] https://boringssl.googlesource.com/boringssl/+/master/crypto...

[3] https://msdn.microsoft.com/en-us/library/sxtz2fa8.aspx

[4] https://msdn.microsoft.com/en-us/library/windows/desktop/aa3...

That's exactly what an NSA shill would say.

Unfortunately, there are many ways[1] that using block devices for random numbers can go wrong.

[1] https://insanecoding.blogspot.com/2014/05/a-good-idea-with-b...

> Don't. Use. Userspace. Random. Number. Generators.

I don't see how this flaw is connected to the fact that libgcrypt runs in user space. A similar bug could well be discovered in the mixing function behind /dev/urandom.

There's nothing especially magical about Fortuna. There are basically three problems to solve with a CSPRNG:

1. Ensuring that it's adequately seeded before anyone can use it.

2. Providing forward secrecy by periodically rekeying ("refreshing the entropy pool", but we should do away with that terminology).

3. Carrying over state across reboots.

(There are four problems if you consider "being performant" a problem on the scale of fundamental design, but it's mostly not).

You wouldn't think CSPRNGs are this simple by reading either the literature on things like Fortuna and Yarrow or by reading the LKML and patch proposals for the LRNG. You'd think it was super tricky to collect "enough entropy" from enough "decorrelated sources", you'd think you'd have to deal with "depletion", you'd think about "high quality" versus "low quality" entropy, and the like. But these issues aren't just not important: they are mostly folkloric.

Generating a practically limitless stream of random bits isn't a hard cryptographic problem. It is an elementary problem. It's the problem that every stream encryption scheme solves. You can simply use stream encryption schemes, like stream ciphers or block ciphers and hashes in CTR mode, as CSPRNGs.

The problem we need to solve isn't upgrading the LRNG or getting everyone to use Schneier's favorite CSPRNG design (the section on this in Cryptography Engineering is one of the book's few warts). It's getting everyone to use the kernel RNG to the exclusion of all else. That's because those 3 problems I listed up there are easy to solve if you're using /dev/urandom (or the getrandom system call), but extremely tricky otherwise.

One good reason would be:

  https://blog.cr.yp.to/20140205-entropy.html

However, many engineers, including kernel hackers AFAIK, still subscribe to the more-is-better model, making Fortuna an obvious choice. But they also still believe they can accurately and _reliably_ estimate entropy[1], which Fortuna moved away from. And Fortuna is probably slower than they'd like. They recently moved away from their homegrown hashes to DJB's ChaCha20 stream cipher, with much improved single-core and multi-core performance.

[1] It's been awhile since I researched this, but long ago, in a land far, far way, there was published a Usenix paper (IIRC) that carefully examined and estimated entropy from disk latencies. These figures were hardcoded into many entropy estimators, including the Linux kernel's, over many cycles of hard drive evolution. IOW, even assuming the paper accurately measured entropy of then-current hard drive technology, it was totally irrelevant over the subsequent decade (and maybe more) it was relied upon. No matter how conservatively you discounted the estimate, the baseline was effectively arbitrary in the context of newer technology. And AFAIK nobody even tried carefully re-validating the original paper. At best there was just more hand waving, fudging of constants, and equivocations of spinning rust.

Which is one reason why, IMHO, entropy estimation is a bad idea, especially when you allow it to dictate the design of your PRNG. It's fundamentally all a bunch of hand waving outside the context of purpose built RNG hardware, and even if you got it right, the next model of a product could destroy your proof. One of the designers of the new PRNG in the Linux kernel put a lot of effort into entropy estimation, including comprehensive software instrumentation to validate some of his assumptions. That's laudable work, but even if correct and accurate, unless you lock him in a room and feed him every new model of CPU, memory controller, disk controller, etc, coming out, it's not reliable.

From a security posture, you never want to make decisions based on the assumption that you're at least as clever as a hacker; that you thought of _all_ the corner cases that might be exploitable. That's what entropy estimation is--trying to discover all the hidden variables and then, when you've exhausted your patience, assuming there are no more, at least none your attacker is likely to discover.

Rather, like with ciphers, you want your proof to be capable of being distilled down to a small number of very clear variables and premises (e.g. key length, cipher construction), which you can then easily keep an eye on for evidence of invalidation. Entropy estimation is really far removed from that model of risk analysis.