Received-SPF: pass (google.com: domain of linux-crypto-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Content-Type: text/plain;
        charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\))
Subject: Re: [Cryptography] [RFC] random: add new pseudorandom number
 generator
From:   Jon Callas <jon@callas.org>
In-Reply-To: <CACXcFm=-E_wnDdRPztKJwDo8hvt6ENf84D90iFUXReuw2s0kuQ@mail.gmail.com>
Date:   Sat, 2 Oct 2021 17:08:03 -0700
Cc:     Jon Callas <jon@callas.org>,
        Linux Crypto Mailing List <linux-crypto@vger.kernel.org>,
        Cryptography <cryptography@metzdowd.com>,
        Ted Ts'o <tytso@mit.edu>
Content-Transfer-Encoding: quoted-printable
Message-Id: <378733E4-D976-4E2D-BE14-AD900C901CE8@callas.org>
References: <CACXcFm=-E_wnDdRPztKJwDo8hvt6ENf84D90iFUXReuw2s0kuQ@mail.gmail.com>
To:     Sandy Harris <sandyinchina@gmail.com>
Precedence: bulk


> On Sep 16, 2021, at 20:18, Sandy Harris <sandyinchina@gmail.com> =
wrote:
>=20
> 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