[Cryptography] [RFC] random: add new pseudorandom number generator

[Jon Callas]

> On Sep 16, 2021, at 20:18, Sandy Harris <sandyinchina at gmail.com> wrote:
> 
> I have a PRNG that I want to use within the Linux random(4) driver. It
> looks remarkably strong to me, but analysis from others is needed.

A good block cipher in counter mode makes a pretty-okay PRNG. I say pretty-okay only because I would like my PRNG not to be invertible. Iterated hash functions are better. However, they are slower, and a property you want in a PRNG is that it's fast. I did a system PRNG that was intentionally faster than arc4random() and close to linear-congruential because then there's no excuse for not using it. A mildly evil person would replace both of those with a fast real PRNG. (Mildly evil because if some user knew the internals and was counting on it acting the way the internals specified, they might be disappointed.)

XTEA is an okay block cipher. Not great, okay. Probably good enough for a PRNG. But -- why wouldn't you use AES? An obvious answer is that you don't have it in hardware and see previous 'graph commentary about speed. Note that XTEA is a 64-bit block, so if you compare to AES, take that in mind.

The NIST AES_CTR_DRBG is mostly-okay. It's got a few issues (see <https://eprint.iacr.org/2020/619.pdf>), but you can get around them. I don't like that it takes a simple concept (a good block cipher is a good PRP/PRF) and throws enough scaffolding around it to make it hard to understand. I understand the reasons (they are essentially the same as your rekey protection and some more), it just bugs me.

So why not just use your CPU's AES (assuming you have one), or further wrap XTEA in the DRBG stuff for the added misuse protection? Or even iterate MD5, or, ummm, you knew this was coming, didn't you, use the PRNG mode of Skein-512 (which is about twice as fast as software AES on a 64-bit CPU)? Yeah, I know, driver. So we're back to why not AES? What's the design consideration?

	Jon