linux-kernel - Re: [PATCH] random: mix all saved registers into entropy pool

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: <20140612200541.GA16012@logfs.org>
Date:	Thu, 12 Jun 2014 16:05:41 -0400
From:	Jörn Engel <joern@...fs.org>
To:	Theodore Ts'o <tytso@....edu>
Cc:	"H. Peter Anvin" <hpa@...or.com>,
	lkml <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] random: mix all saved registers into entropy pool

On Tue, 10 June 2014 20:10:09 -0400, Jörn Engel wrote:
> On Tue, 10 June 2014 12:14:01 -0400, Theodore Ts'o wrote:
> > On Mon, May 19, 2014 at 05:17:19PM -0400, Jörn Engel wrote:
> > > +/*
> > > + * Ratelimit to a steady state of about once per jiffy.  A naïve approach
> > > + * would be to return 1 every time jiffies changes.  But we want to avoid
> > > + * being closely coupled to the timer interrupt.  So instead we increment
> > > + * a counter on every call and shift it right every time jiffies changes.
> > > + * If the counter is a power of two, return false;
> > > + *
> > > + * Effect is that some time after a jiffies change and cutting the counter
> > > + * in half we reach another power of two and return false.  But the
> > > + * likelihood of this happening is about the same at any time within a
> > > + * jiffies interval.
> > > + */
> > > +static inline int ratelimited(struct fast_pool *p)
> > > +{
> > > +	int ret = !(p->regs_count == 0 || is_power_of_2(p->regs_count));
> > > +
> > > +	p->regs_count++;
> > > +	if (p->last_shift != (u32)jiffies) {
> > > +		p->regs_count >>= min(31u, (u32)jiffies - p->last_shift);
> > > +		p->last_shift = (u32)jiffies;
> > > +	}
> > > +	return ret;
> > > +}
> > 
> > I wasn't convinced this would do the right thing, so I wrote a quick
> > test program where the main loop was basically this:
> > 
> > 	for (i=0; i < 1024; i++) {
> > 		jiffies = i >> 2;
> > 		r = ratelimited(jiffies);
> > 		printf("%5u %5u %5u %d\n", i, jiffies, regs_count, r);
> > 	}
> > 
> > ... which basically simulated a very simple scheme where there were
> > four interrupts for each clock tick.  In the steady state ratelimited
> > returns true 75% of the time.  If this was as documented, we would
> > expect it to return true 25% of the time.  So I don't think this is
> > working quite right:
> > 
> >    20     5     3 1
> >    21     5     4 1
> >    22     5     5 0
> >    23     5     6 1
> >    24     6     3 1
> >    25     6     4 1
> >    26     6     5 0
> >    27     6     6 1
> >    28     7     3 1
> >    29     7     4 1
> >    30     7     5 0
> >    31     7     6 1
> >    32     8     3 1
> 
> Doh!  Removing the "!" from "!(p->regs_count..." will fix that.  Shows
> I spent 100x more time testing the bootup entropy collection.

On second look, the function was correct.  If ratelimited() returns
true, the interrupt is ratelimited, i.e. ignored.  So correct
behaviour is to return false 25% of the time, just like it does.

You confused me for a moment!

Jörn

--
There are two ways of constructing a software design: one way is to make
it so simple that there are obviously no deficiencies, and the other is
to make it so complicated that there are no obvious deficiencies.
-- C. A. R. Hoare
--
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/