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

[Roland C. Dowdeswell]

On Sat, Oct 02, 2021 at 05:08:03PM -0700, Jon Callas wrote:
>

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

One small problem with a block cipher in counter mode is that you know
that there will never be a repeat of the same ciphertext blocksize bits
in a row.  Quite a while ago, I thought that a good way to resolve this
would be to throw away half the output of each encryption.  This should
resolve that [small] bias in the output.  But, then it occurred to me that
maybe you shouldn't throw away 64 perfectly good bits for each operation,
why not feed them back into the routine?

Something like this:

	(prev(n), output) = AES(key, prev(n-1) ++ ctr)
	ctr += 1

where prev(n), output, and key are 64 bits.

It seems to me that this would have a number of desirable qualities.

To make it a bit faster, you could interleave a bit to be able to run
four operations in parallel to get the most use out of AES-NI.  But,
I think that if designed properly, this wouldn't affect the analysis of
the security properties of the PRNG.

Is this similar to any existing PRNGs?

--
    Roland C. Dowdeswell                          https://Imrryr.ORG/