linux-kernel - Re: [Security] [patch] random: make get_random

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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <alpine.LFD.2.01.0905160854570.3301@localhost.localdomain>
Date:	Sat, 16 May 2009 09:05:06 -0700 (PDT)
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Oliver Neukum <oliver@...kum.org>
cc:	Willy Tarreau <w@....eu>, Ingo Molnar <mingo@...e.hu>,
	security@...nel.org, Linux@...a.kernel.org, stable@...nel.org,
	Cox <alan@...rguk.ukuu.org.uk>, Arjan@...a.kernel.org,
	List <linux-kernel@...r.kernel.org>, Alan@...a.kernel.org,
	Eric Paris <eparis@...hat.com>, Jake Edge <jake@....net>,
	linux-security-module@...r.kernel.org, mingo@...hat.com,
	"Eric W. Biederman" <ebiederm@...ssion.com>,
	Matt Mackall <mpm@...enic.com>, Dave Jones <davej@...hat.com>,
	James Morris <jmorris@...ei.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Roland McGrath <roland@...hat.com>,
	de Ven <arjan@...radead.org>
Subject: Re: [Security] [patch] random: make get_random_int() more random

On Sat, 16 May 2009, Oliver Neukum wrote:
> 
> Why can't we implement more than one hash and choose at boot time?
> Or even change the hash on the fly? That's not as good as a secret
> algorithm, but the attacker would have to guess which is used.

There's never really any point in just expanding the search space by some 
small factor. You want to expand the search space _exponentially_, not by 
just making it "three times harder".

Small factors are meaningless, because it's just going to cut down your 
success rate (well, in this case "failure rate" depending on which side 
you're on) by a small constant factor.

So "one of X known functions" does not help - it's a small constant 
factor, and you're likely _much_ better off instead just adding a couple 
of bits of hash space or entropy instead, which also makes things harder. 

Hashing in the TSC, for example, when possible, is a _lot_ more effective: 
even if the attacker can easily get a close estimation of roughly where 
the TSC is, in practice it's going to add a couple of bits of effectively 
random data on each iteration, and as such is much more powerful than 
adding a couple of bits of effectively random data just once at bootup.

What people often do is to use multiple hashes, but not select among them, 
but run them sequentially over the same data - so that if one hash is 
broken, the combination is not. And even if all hashes are broken, it's 
quite likely that the combination is much harder to break (and not by a 
small constant factor, but potentially a multiplicative cost of each 
individual hash breakage - so as long as breaking each hash isn't some 
_trivial_ O(1) thing, doing sequential hashing can add real security).

Of course, doing the sequential hashes isn't exactly good for performance ;)

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