netdev - Re: [DRAFT PATCH] random32: make 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 for Android: free password hash cracker in your pocket

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

Message-ID: <20200809170639.GB25124@SDF.ORG>
Date:   Sun, 9 Aug 2020 17:06:39 +0000
From:   George Spelvin <lkml@....ORG>
To:     Willy Tarreau <w@....eu>
Cc:     netdev@...r.kernel.org, aksecurity@...il.com,
        torvalds@...ux-foundation.org, edumazet@...gle.com,
        Jason@...c4.com, luto@...nel.org, keescook@...omium.org,
        tglx@...utronix.de, peterz@...radead.org, tytso@....edu,
        lkml.mplumb@...il.com, stephen@...workplumber.org, fw@...len.de,
        George Spelvin <lkml@....ORG>
Subject: Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

On Sun, Aug 09, 2020 at 11:38:05AM +0200, Willy Tarreau wrote:
> So I gave it a quick test under Qemu and it didn't show any obvious
> performance difference compared to Tausworthe, which is a good thing,
> even though there's a significant amount of measurement noise in each
> case.

Thank you very much!  I'm not quite sure how to benchmark this.
The whole idea is that it's *not* used in a tight cache-hot loop.
Hopefully someone already has a test setup so I don't have to invent
one.

> However it keeps the problem that the whole sequence is entirely
> determined at the moment of reseeding, so if one were to be able to
> access the state, e.g. using l1tf/spectre/meltdown/whatever, then
> this state could be used to predict the whole ongoing sequence for
> the next minute. What some view as a security feature, others will
> see as a backdoor :-/  That's why I really like the noise approach.
> Even just the below would significantly harm that capability because
> that state alone isn't sufficient anymore to pre-compute all future
> values:
> 
> --- a/lib/random32.c
> +++ b/lib/random32.c
> @@ -375,6 +375,7 @@ static u32 siprand_u32(struct siprand_state *s)
>  {
>         unsigned long v0 = s->v[0], v1 = s->v[1], v2 = s->v[2], v3 = s->v[3];
>  
> +       v0 += get_cycles();
>         SIPROUND(v0, v1, v2, v3);
>         SIPROUND(v0, v1, v2, v3);
>         s->v[0] = v0;  s->v[1] = v1;  s->v[2] = v2;  s->v[3] = v3;

As long as:
1) The periodic catastrophic reseeding remains, and
2) You use fresh measurements, not the exact same bits
   that add_*_randomness feeds into /dev/random
then it doesn't do any real harm, so if it makes you feel better...

But I really want to stress how weak a design drip-reseeding is.

If an attacker has enough local machine access to do a meltdown-style attack,
then they can calibrate the TSC used in get_cycles very accurately, so the
remaining timing uncertainty is very low.  This makes a brute-force attack on
one or two reseedings quite easy.  I.e. if you can see every other output,
It's straightforward to figure out the ones in between.

I wonder if, on general principles, it would be better to use a more
SipHash style mixing in of the sample:
	m = get_cycles();
	v3 ^= m;
	SIPROUND(v0, v1, v2, v3);
	SIPROUND(v0, v1, v2, v3);
	v0 ^= m;

Not sure if it's worth the extra register (and associated spill/fill).