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

[Ingo Molnar <mingo@elte.hu>]

* Matt Mackall <mpm@selenic.com> wrote:

> On Wed, May 06, 2009 at 10:51:45PM +0200, Ingo Molnar wrote:
> > Linus's patch is a marked improvement, and it is really what we need 
> > here mostly.
> 
> No one's arguing that it isn't an improvement. But -15 years of 
> research- points to MD4 (let alone **half**MD4) being 
> insufficient. To counter that, two non-cryptanalysts have 
> presented nothing beyond "it seems strong enough to me" and "it 
> passes a meaningless test". Pardon me if I'm not satisfied by 
> that.

So is it your point that mixing the cycle counter with a bad hash 
function is not sufficient? Not sufficient in precisely what threat 
model and against what attack vector? I'd like to hear specifics. 
The URLs pasted in this thread were inapposite - they were using 
information leaks from privileged contexts. If you have relevant 
URLs then please share them.

Are you worried about an attacker being able to run analysis code 
locally, trigger get_random_int() and observe its results, and then 
start a privileged context and know its address space layout?

I can tell you with near certainty that if we mix in the cycle 
counter (and those other task local and call local details) that 
then this attack vector is not practical on x86, at all.

( This particular attack would probably not be feasible even if we 
  used rot13 as the hash plus the cycle counter and the other values 
  - although i certainly feel more confident about this argument 
  with half-md4 in place as the hash. )

> > We cannot afford true physical randomness (it's too expensive to 
> > get and not all hw has it), and even a 'good' PRNG is pretty 
> > expensive.
> 
> And what of my suggestion (multiple times now) to replace halfMD4 
> with SHA1? Or AES. Or any cryptographic primitive that's not known 
> to be completely worthless?

They are all rather expensive, while the existing usage pattern for 
get_random_int() is really: "i want some randomness but also want it 
to be fast".

	Ingo