netdev.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: George Spelvin <lkml@SDF.ORG>
To: Willy Tarreau <w@1wt.eu>
Cc: netdev@vger.kernel.org, aksecurity@gmail.com,
	torvalds@linux-foundation.org, edumazet@google.com,
	Jason@zx2c4.com, luto@kernel.org, keescook@chromium.org,
	tglx@linutronix.de, peterz@infradead.org, tytso@mit.edu,
	lkml.mplumb@gmail.com, stephen@networkplumber.org, fw@strlen.de,
	George Spelvin <lkml@SDF.ORG>
Subject: Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable
Date: Sun, 9 Aug 2020 17:06:39 +0000	[thread overview]
Message-ID: <20200809170639.GB25124@SDF.ORG> (raw)
In-Reply-To: <20200809093805.GA7928@1wt.eu>

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

  reply	other threads:[~2020-08-09 17:11 UTC|newest]

Thread overview: 68+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-08-08 15:26 Flaw in "random32: update the net random state on interrupt and activity" George Spelvin
2020-08-08 17:07 ` Andy Lutomirski
2020-08-08 18:08   ` Willy Tarreau
2020-08-08 18:13   ` Linus Torvalds
2020-08-08 19:03   ` George Spelvin
2020-08-08 19:49     ` Andy Lutomirski
2020-08-08 21:29       ` George Spelvin
2020-08-08 17:44 ` Willy Tarreau
2020-08-08 18:19   ` Linus Torvalds
2020-08-08 18:53     ` Willy Tarreau
2020-08-08 20:47     ` George Spelvin
2020-08-08 20:52       ` Linus Torvalds
2020-08-08 22:27         ` George Spelvin
2020-08-09  2:07           ` Linus Torvalds
2020-08-11 16:01             ` Eric Dumazet
2020-08-08 19:18   ` Florian Westphal
2020-08-08 20:59     ` George Spelvin
2020-08-08 21:18     ` Willy Tarreau
2020-08-08 20:08   ` George Spelvin
2020-08-08 20:47     ` Linus Torvalds
2020-08-09  6:57 ` [DRAFT PATCH] random32: make prandom_u32() output unpredictable George Spelvin
2020-08-09  9:38   ` Willy Tarreau
2020-08-09 17:06     ` George Spelvin [this message]
2020-08-09 17:33       ` Willy Tarreau
2020-08-09 18:30         ` George Spelvin
2020-08-09 19:16           ` Willy Tarreau
2020-08-10 11:47           ` Willy Tarreau
2020-08-10 12:01             ` David Laight
2020-08-10 14:48               ` Willy Tarreau
2020-08-10 12:03             ` Florian Westphal
2020-08-10 14:53               ` Willy Tarreau
2020-08-10 16:31             ` Linus Torvalds
2020-08-10 16:58               ` Willy Tarreau
2020-08-10 17:45                 ` Linus Torvalds
2020-08-10 18:01                   ` Willy Tarreau
2020-08-10 21:04                   ` Willy Tarreau
2020-08-11  5:26                     ` George Spelvin
2020-08-11  5:37                       ` Willy Tarreau
2020-08-11  3:47             ` George Spelvin
2020-08-11  3:58               ` Willy Tarreau
     [not found]     ` <fdbc7d7d-cba2-ef94-9bde-b3ccae0cfaac@gmail.com>
2020-08-09 21:10       ` Marc Plumb
2020-08-09 21:48         ` Linus Torvalds
2020-08-09 13:50   ` Randy Dunlap
     [not found]   ` <CANEQ_++a4YcwQQ2XhuguTono9=RxbSRVsMw08zLWBWJ_wxG2AQ@mail.gmail.com>
2020-08-09 16:08     ` George Spelvin
     [not found] <CA+icZUVnsmf1kXPYFYufStQ_MxnLuxL+EWfDS2wQy1VbAEMwkA@mail.gmail.com>
2020-08-09 21:10 ` Sedat Dilek
     [not found] ` <20200809235412.GD25124@SDF.ORG>
     [not found]   ` <20200810034948.GB8262@1wt.eu>
     [not found]     ` <20200811053455.GH25124@SDF.ORG>
     [not found]       ` <20200811054328.GD9456@1wt.eu>
     [not found]         ` <20200811062814.GI25124@SDF.ORG>
     [not found]           ` <20200811074538.GA9523@1wt.eu>
2020-08-11 10:51             ` Sedat Dilek
2020-08-11 11:01               ` Sedat Dilek
2020-08-12  3:21               ` Willy Tarreau
2020-08-13  7:53                 ` Sedat Dilek
2020-08-13  8:06                   ` Willy Tarreau
2020-08-13  8:13                     ` Sedat Dilek
2020-08-13  8:27                       ` Sedat Dilek
2020-08-13 14:00                         ` Eric Dumazet
2020-08-13 16:02                           ` Sedat Dilek
2020-08-14 15:32                     ` Sedat Dilek
2020-08-14 16:05                       ` Willy Tarreau
2020-08-14 16:17                         ` Sedat Dilek
2020-08-16 15:01                           ` Willy Tarreau
2020-08-16 16:48                             ` Sedat Dilek
2020-08-20  3:05                               ` Sedat Dilek
2020-08-20  4:33                                 ` Willy Tarreau
2020-08-20  4:42                                   ` Sedat Dilek
2020-08-20  6:08                                     ` Willy Tarreau
2020-08-20  6:58                                       ` Willy Tarreau
2020-08-20  8:05                                         ` Willy Tarreau
2020-08-20 12:08                                           ` Sedat Dilek
     [not found]                                           ` <CANEQ_+L+22Hkdqf38Zr0bfq16fcL1Ax2X9fToXV_niHKXCB8aA@mail.gmail.com>
2020-08-27  1:09                                             ` Willy Tarreau
2020-08-27  7:08                                               ` Sedat Dilek

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20200809170639.GB25124@SDF.ORG \
    --to=lkml@sdf.org \
    --cc=Jason@zx2c4.com \
    --cc=aksecurity@gmail.com \
    --cc=edumazet@google.com \
    --cc=fw@strlen.de \
    --cc=keescook@chromium.org \
    --cc=lkml.mplumb@gmail.com \
    --cc=luto@kernel.org \
    --cc=netdev@vger.kernel.org \
    --cc=peterz@infradead.org \
    --cc=stephen@networkplumber.org \
    --cc=tglx@linutronix.de \
    --cc=torvalds@linux-foundation.org \
    --cc=tytso@mit.edu \
    --cc=w@1wt.eu \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).