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

[Sandy Harris]

Jon Callas <jon at callas.org> wrote:

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

I'm using counter mode inside an Even-Mansour XOR-permutation-XOR
structure which, among other things, makes it non-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.)

I'm doing this within the Linux random(4) driver which iterates chacha
to generate output. This prng will only generate values for internal
use, like rekeying chacha or dumping data into the input pool. In
fact, if an instruction like Intel RDRAND or a hardware rng exist the
code mostly uses those, only injecting xtea output once in a while to
avoid tructing the other source completely or falling back to xtea if
the other fails.

> XTEA is an okay block cipher. Not great, okay. Probably good enough for a PRNG.

With the Even-Mansour construction it seems good enough to me. Code
includes this comment:

 * Even and Mansour proved proved a lower bound
 * for an XOR-permutation-XOR sequence.
 * S. Even, Y. Mansour, Asiacrypt 1991
 * A Construction of a Cipher From a Single Pseudorandom Permutation
 *
 * For an n-bit cipher and D known or chosen plaintexts,
 * time T to break it is bounded by DT >= 2^n.
 *
 * This applies even if the enemy knows the permutation,
 * for a block cipher even if he or she knows the key.
 * All the proof requires is that the permutation be
 * nonlinear.
 *
 * The main calling function does a full rekey (update
 * key, mask and counter) when xtea_iterations >= 127
 * We therefore have D ~= 2^7 and T >= 2^57 to break
 * each sequence of 127 outputs between rekeyings.
 *
 * Assuming proper keying and that the enemy cannot
 * peek into the running kernel, this can be
 * considered effectively unbreakable, even if
 * xtea itself were found to be flawed.

> But -- why wouldn't you use AES? An obvious answer is that you don't have it in hardware ...

I wanted something that would be reasonably fast on anything Linux
runs on & wanted to avoid using kernel memory for the S-box & round
keys.