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

From: Linus Torvalds
Date: Sat May 16 2009 - 12:09:24 EST




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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/