netdev - Re: Revising prandom

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:   Tue, 26 Mar 2019 14:03:55 -0400
From:   "Hannes Frederic Sowa" <hannes@...essinduktion.org>
To:     "George Spelvin" <lkml@....org>,
        "Daniel Borkmann" <daniel@...earbox.net>
Cc:     netdev@...r.kernel.org
Subject: Re: Revising prandom_32 generator

Hi,

On Tue, Mar 26, 2019, at 12:10, George Spelvin wrote:
> I started on a project to correct all of the instances of
> "prandom_u32() % FOO" in the kernel (there are lots)
> to "prandom_u32_max(FOO)".

The conversation definitely makes sense.

Are you trying to fix the modulo biases? I think that prandom_u32_max also has bias, would that be worth fixing as well?

> [...]
>
> Thw ones that seem interesting to me are:
> - Chris Doty-Humphrey's sfc32.  This is a 96-bit chaotic generator
>   (meaning period *probably* long but not well defined) fed with
>   a 32-bit counter to ensure a minimum period.  It's extremely
>   fast, and the author is also the author of PractRand, so it's
>   well-tested.
> - Vigna and Bacman's xoshiro128**.  This is a 128-bit LFSR with some
>   output postprocessing.
> - (on 64-bit machines) xoroshiro128**, by the same authors.
>   This is only efficient on 64-bit machines, so it would need
>   a have a 32-bit backup.
> - Bob Jenkins' jsf (originally "flea").  128 bits, good mixing,
>   fully chaotic.  I prefer the safety of a guaranteed minimum
>   period, but this is well thought of.
> - A lag-3 mutiply-with-carry generator.  2^32 - 1736 is the largest
>   "safe prime" mutiplier.

I think tausworthe is not _trivially_ to predict, what about your proposed algorithms? I think it is a nice to have safety-net in case too much random numbers accidentally leaks (despite reseeding).

Thanks,
Hannes