linux-kernel - Re: [PATCH RFC] random: Account for entropy loss due to overwrites

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: <20121016155307.GF17446@thunk.org>
Date:	Tue, 16 Oct 2012 11:53:07 -0400
From:	Theodore Ts'o <tytso@....edu>
To:	"H. Peter Anvin" <hpa@...ux.intel.com>
Cc:	"H. Peter Anvin" <hpa@...or.com>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	greg@...ah.com, w@....eu, ewust@...ch.edu, zakir@...ch.edu,
	mpm@...enic.com, nadiah@...ucsd.edu, jhalderm@...ch.edu,
	tglx@...utronix.de, davem@...emloft.net, mingo@...nel.org,
	DJ Johnston <dj.johnston@...el.com>, stable@...r.kernel.org
Subject: Re: [PATCH RFC] random: Account for entropy loss due to overwrites

On Mon, Oct 15, 2012 at 09:45:23PM -0700, H. Peter Anvin wrote:
> 
> Or we could compute poolwords (and poolbits, and poolbytes) from it,
> since shifts generally are cheap.  I don't strongly care, whatever your
> preference is.

We are already calculating poolbits from poolwords:

#define POOLBITS	poolwords*32
#define POOLBYTES	poolwords*4

So you'd basically be suggesting that we define

#define POOLWORDS	(1 << (poolshift - 5))
#define POOLBYTES	(1 << (poolshift - 3))
#define POOLBITS	(1 << poolshift)

Yeah, that works; we don't use poolwords in that many places, and a
data dependent shift is cheap at least on x86 and arm (so probably all
modern platforms).

There was one aesthetic reason for using POOLWORDS, which was that
first term of the generating polynomial was the same as poolwords,
i.e:

	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
	{ 128,	103,	76,	51,	25,	1 },
	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
	{ 32,	26,	20,	14,	7,	1 },

If we change it to be:

	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
	{ 12,	103,	76,	51,	25,	1 },
	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
	{ 10,	26,	20,	14,	7,	1 },

It's a wee bit less obvious where the "12" and "10" is coming form.  I
don't see an easy way to fix this, though, other than perhaps making
sure it's clear in the comments.  Unfortunately we can't count on gcc
doing a built-in optimization for a log2 of a constant as far as I
know.... or can we?

Hmm, this does get optimized correctly at least with gcc 4.7:

#define shiftbits(words) ((int) __builtin_log2((double) (words)) + 5)

... and it looks like include/linux/log2.h already has a definition
for ilog2() which should definitely work for all versions of gcc, so
we could do this instead:

#define shiftbits(w)	(ilog2((w)) + 5)

	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
	{ shiftbits(128), 103,	76,	51,	25,	1 },
	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
	{ shiftbits(32),  26,	20,	14,	7,	1 },

						- Ted

--
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/