OSDev.org

moonchild wrote:This discusses various problems with rdrand/rdseed, including their ability of a malicious implementation to poison other sources of entropy. I think the use of rdrand/rdseed should not be recommended at all, even for seeding entropy pools; or if it is recommended, it should be made very clear that you have to:

1, collect rdrand before other strong sources of entropy (e.g. hardware timings); and

2, don't rely solely on rdrand

I have never advocated anything else than the second option. RDRAND and RDSEED are by design black boxes that could be implementing whatever they want, including attacks on my OS. How you get to your conclusion number 1 I don't know. I would just sample RDRAND at random intervals and add that to the entropy pool. Or maybe use it to initialize the pool.

moonchild wrote:The non-cryptographic RNGs section is, I think, remiss without mentions of pcg and xoshiro/xoroshiro.

No, they get a "further reading" entry. If I list every RNG algorithm in existence, we will be here all day. I only listed the most significant ones, for a subjective measure of significance. LFSRs are historically significant, being among the first algorithms used. LCGs are significant because they are still used to implement randomness functions in common language run time libraries. Wichmann-Hill admittedly is a personal choice. It recently gained some prominence for being used in the game The Legend of Zelda: Wind Waker (at least, that's how it came to my attention). And finally the Mersenne Twister, which is often suggested as a replacement for the "bad" LCGs. Honestly, though, although I read a lot of source code, I have never come across a use of the Mersenne Twister in the wild.

nullplan wrote:

moonchild wrote: 1, collect rdrand before other strong sources of entropy (e.g. hardware timings); and

How you get to your conclusion number 1 I don't know.

The slideshow I linked has a demonstration. A malicious rdrand can look at the existing entropy pool and return values calculated to poison it.

moonchild wrote:The slideshow I linked has a demonstration. A malicious rdrand can look at the existing entropy pool and return values calculated to poison it.

So basically what I said in my most recent reply (second most recent now). I guess I didn't think this far enough.

Of course, if the CPU vendor wanted to attack my OS specifically, they have no need to detain themselves with a malicious RDRAND implementation, and can just read out whatever they want from the Management Engine or whatever AMD calls it. And then exfiltrate it via the builtin networking card. But I suppose breaking RDRAND would be stealthier.

Well, crap. Last month I stumbled upon this page and took matters into my own hands. What started as a quick edit to remove the vague "hybrid" PRNG type spiraled out of control a tiny bit:

• In place of the pseudo/hybrid/true split I added some notes on cryptographic security. This then leads into a section on entropy sources, followed by CSPRNGs and finally regular PRNGs. I think this order is best, because you have a logical flow from "strong" to "weak" randomness.
• I also split RDSEED/RDRAND into an entropy source and a CSPRNG, respectively, according to Intel documentation. And I added warnings that you may not want to trust these instructions (or any hardware entropy source for that matter).
• For the CSPRNG, I did not provide my own code because I do not trust myself to create a properly secure implementation. I think a bold (maybe large and red as well) "NOTE: do not use this" is not sufficient to ward off "Duct von Tape" types. Instead, I linked to an article that also explains some possible faults.
• The old PRNG section was particularly silly, with three sections describing the same LCG in slightly different ways. I merged the three into one. The "Fibonacci random number" section I didn't know what to do with. I couldn't find a paper on it and I didn't look for an implementation to check if it's a good RNG so I just left it. It may be best to remove this.
• After the LFSR section (which was excellent, except that it called every bit a register?) I added the Mersenne Twister. It's always available in C++11 and up (std::mt19937[_64]) and is the standard PRNG in PHP and Python and lots of other platforms and programs.
• The last PRNGs are PCG and /xo(ro)?shiro\d+[+*]+/. This is where I got a bit sidetracked by the whole xoshiro vs PCG (or rather, Vigna vs O'Neill) rabbithole. I did want to include them, because they have a... heavy presence on the web. Plus, they're fast, simple and good PRNGs, used by Numpy and Rust for example.
• Finally, I added an example for testing a "home-grown" PRNG, in case the reader suffers from extreme NIH-syndrome and wants to make their own random numbers from scratch.

So that's a (lengthy) recap of the current state of the page. I was still planning on expanding the xoroshiro part (including CC0 code) and adding some background information and "See also" links. And polish the currently rough parts of course. But, life got in the way and after that I got distracted by other projects.

Nullplan, I like your version of the page as well and would hate to see your effort go to waste. I was thinking of:

• copying the introduction of the Entropy section
• merging the Timing subsection into the "Sampling manually" subsection
• copying "Adversarial entropy" into "True random numbers"
• inserting "Wichmann-Hill" just below the LFSR section (adding just one other PRNG won't hurt, right? )
• using your version of the mt19937 code (32-bit support and no auto-seeding, which may be less error-prone)
• using parts of "Cryptographic security" to explain hashing the entropy pool, though I'm uncertain about mixing the hash back into the pool

And otherwise keeping the points in my summary in mind.

Sorry for the mess! I'll see if I can find the time soon to create a merged version under my user page. In any case, I'm interested in what you think of my plan.

Wukl wrote:Sorry for the mess! I'll see if I can find the time soon to create a merged version under my user page. In any case, I'm interested in what you think of my plan.

Go ahead. Looks good so far. And don't apologize for the mess, it fits the rest of the Wiki.