Re: [Security] [patch] random: make get_random_int() more random

[Linus Torvalds <torvalds@linux-foundation.org>]

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