linux-kernel - Re: [PATCH 3/6] random: do extraction before mixing

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-next>] [day] [month] [year] [list]

Date:	Sat, 8 Dec 2007 19:35:54 -0500
From:	Theodore Tso <tytso@....edu>
To:	Matt Mackall <mpm@...enic.com>
Cc:	Andrew Morton <akpm@...ux-foundation.org>,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH 3/6] random: do extraction before mixing

On Sat, Dec 08, 2007 at 05:20:17PM -0600, Matt Mackall wrote:
> random: do extraction before mixing
> 
> If an attacker manages to capture the current pool state, she can
> determine the last 10 bytes extracted from the pool. 

That's not true; we aren't just extracting data in the
__add_entropy_words() call.  In fact, above that, the bulk of the
extraction comes form when we hash the entire pool, feeding back a
portion of the hash into the pool here:

	for (i = 0; i < r->poolinfo->poolwords; i += 16) {
		/* hash blocks of 16 words = 512 bits */
		sha_transform(buf, (__u8 *)(r->pool + i), buf + 5);
		/* feed back portion of the resulting hash */
		add_entropy_words(r, &buf[i % 5], 1);
	}

So the buf[0..5] contains a hash of the entire pool, and every 16
words, we're already mixing 32 bits into the pool.  So even if the
attacker captures the current pool state, she's not going to be able
to undo the intermediate SHA values that had been mixed into the pool.

> By mixing after
> the extraction, this is made substantially harder.

Not that much harder; as I mentioned as comments in my last patch, we
are doing a linear polynomial mixing for speed purposes, so relying on
the mixing to obscure the extraction isn't going to help much.

But that's OK, we don't need to depend on that.  Note the amount of
feedback that we do in the above loop.

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