linux-kernel - Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 14 Oct 2013 10:14:00 -0400
From:	Sandy Harris <sandyinchina@...il.com>
To:	"Theodore Ts'o" <tytso@....edu>,
	LKML <linux-kernel@...r.kernel.org>,
	linux-crypto@...r.kernel.org, Stephan Mueller <smueller@...onox.de>
Subject: Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

On Mon, Oct 14, 2013 at 9:38 AM, Sandy Harris <sandyinchina@...il.com> wrote:

> Stephan Mueller <smueller@...onox.de> wrote:

>> Can you please help me understand why you think that a whitening
>> function (cryptographic or not) is needed in the case of the CPU Jitter
>> RNG, provided that I can show that each individual bit coming from the
>> folding operation has one bit of entropy?
>
> Basically, sheer paranoia. I'd mix and whiten just on general
> principles. Since efficiency is not a large concern, there is little
> reason not to.
>
> On the other hand, most RNGs use a hash because they need
> to distill some large amount of low-entropy input into a smaller
> high-entropy output. With high input entropy, you do not need
> the hash and can choose some cheaper mixer.

You could use strong mixing/whitening:

Feed into random(4) and let it do the mixing.

Use some early outputs from your RNG to key an AES
instance. Then encrypt later outputs; this gives a 64 in 64
out mixer that is cryptographically strong but perhaps a bit
slow in the context.

Alternately, quite a few plausible components for fast cheap
mixing are readily available.

The Aria cipher has one that is 128 in 128 out. It multiplies
a 128-bit object by a fixed Boolean matrix, makes every
output bit depend on many input bits. It is fairly cheap,
used in every round and the cipher is acceptably fast.

The column transform from AES is 32 in 32 out and makes
every output byte depend on every input byte. It is fast; has
to be since it is used four times in every round.

A two-way pseudo-Hadamard transform (PHT) is 2n bits in
and 2n out, requires only two additions, makes both n-bit
outputs depend on both inputs.

PHT can be applied recursively to mix 4n, 8n, ...

My QHT is 32 in 32 out, makes every /bit/ of output
depend on every bit of input. It is a tad expensive;
two multiplications & two modulo operations. File
qht.c at:
ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/

To mix 64 bits, I'd use two qht() calls to mix the 32-bit
halves then a two-way PHT.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/