linux-kernel - Re: [PATCH,RFC] random: make fast

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]

Message-ID: <20130923001623.GD4584@logfs.org>
Date:	Sun, 22 Sep 2013 20:16:23 -0400
From:	Jörn Engel <joern@...fs.org>
To:	Theodore Ts'o <tytso@....edu>
Cc:	Jörg-Volker Peetz <jvpeetz@....de>,
	John Stultz <john.stultz@...aro.org>,
	Stephan Mueller <smueller@...onox.de>,
	LKML <linux-kernel@...r.kernel.org>, dave.taht@...ferbloat.net,
	Frederic Weisbecker <fweisbec@...il.com>,
	Thomas Gleixner <tglx@...utronix.de>
Subject: Re: [PATCH,RFC] random: make fast_mix() honor its name

On Sun, 22 September 2013 19:36:41 -0400, Theodore Ts'o wrote:
> On Sun, Sep 22, 2013 at 04:53:34PM -0400, Jörn Engel wrote:
> > 
> > And I want to keep that function.  Essentially the point of fast_mix()
> > is to ratelimit _mix_pool_bytes().  Naïve ratelimiting would simply
> > discard the input once the ratelimit has been reached.  My proposal is
> > to still use the input bits, but use a really cheap mixing function.
> 
> Sure, but how cheap is "cheap"?  There's a balance here.  I don't buy
> the argument that we must weaken the fast_mix() at all costs because
> we have to drive the cost of fast_mix() to zero.  If we're going to do
> that, to the limit fast_mix() should be a no-op, which is ridiculous.

Agreed.  We always have a tradeoff between quality and cost.  And I
repeat yet again that driving the cost down is important, because it
allows us to collect entropy more often.  The schedule is an entropy
source I would like to tap.

> So what I've suggested already makes fast_mix() much faster.  It's not
> fast as what you've proposed, but it's pretty clear that my fast_mix()
> is better at mixing the fast_mix pool.

Agreed.

> > Your version of fast_mix() failed in the "really cheap" department.
> > As a result, it showed up in profiles and at least one idiot (me)
> > reverted to naïve ratelimiting.  It could have been worse, I was
> > explicitly asked twice to just remove the call to
> > add_interrupt_randomness().
> 
> Sure, but that's not _my_ problem.  If someone stupid adulterates
> /dev/random, that's not my responsibility.  Most people aren't going
> to be dealing with systems with truly stupid interrupt rates, and most
> people aren't going to be tampering with the random driver.

This is where I don't agree.  I very much care even about the plastic
routers running some variant of Linux modified by some embedded
engineers under insane time pressure.  If you leave them an incentive
to cripple the random generator, some of them will.  If you find
source code with a maliciously crippled random generator, the author
has plausible deniability.

So this should be _our_ problem.  Maybe not yours specifically, but
certainly that of kernel developers in general.

> I'm certainly willing to make fast_mix() faster, to reduce the
> temptation for idiots to tamper with /dev/random, but we need to
> balance the time of fast_mix() with the quality of its mixing, and to
> remember what the common case is (and it's not 100k interrupts per
> second!)

How about we switch between the two mixing functions depending on the
interrupt load?  If this CPU has seen fewer than 1000 interrupts in
the last second, use the better one, otherwise us the cheaper one?

I don't really like the idea too much.  But it would cover both the
common case and my particular degenerated one.

> In practice, we are using randomness in so many places (every single
> time we start a process for ASLR, in lots of security-related programs
> that use SSL libraries, etc.), that we are actually practically
> *never* hitting trickle_thresh.
> 
> The trickle_thresh was added originally when add_timer_randomness()
> was used for interrupts that used SA_SAMPLE_RANDOM.  Given that we
> don't use add_timer_randomness() for that, but for things that happen
> much more rarely (i.e., such as keyboard/mouse input), I'm probably
> going to end up removing the trickle thresh_check altogether.

Makes sense to me.

Jörn

--
Doubt is not a pleasant condition, but certainty is an absurd one.
-- Voltaire
--
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/