Date:	Thu, 7 May 2009 20:41:36 +0200
From:	Ingo Molnar <mingo@...e.hu>
To:	Matt Mackall <mpm@...enic.com>
Cc:	Linus Torvalds <torvalds@...ux-foundation.org>,
	"Eric W. Biederman" <ebiederm@...ssion.com>,
	Arjan van de Ven <arjan@...radead.org>,
	Jake Edge <jake@....net>, security@...nel.org,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	James Morris <jmorris@...ei.org>,
	linux-security-module@...r.kernel.org,
	Eric Paris <eparis@...hat.com>,
	Alan Cox <alan@...rguk.ukuu.org.uk>,
	Roland McGrath <roland@...hat.com>, mingo@...hat.com,
	Andrew Morton <akpm@...ux-foundation.org>,
	Greg KH <greg@...ah.com>, Dave Jones <davej@...hat.com>
Subject: Re: [Security] [PATCH] proc: avoid information leaks to
	non-privileged processes


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

> > As i mentioned it in the previous mail, i'd _really_ like to 
> > hear your thread model and attack vector description. Does this 
> > overhead justify the threat? Your change will only result in 
> > get_random_int() not being considered fast anymore.
> 
> My threat model is that someone more clever and with a lot more 
> expertise attacking systems than either you or me will be able to 
> leverage the extreme weakness of this hash (O(1) attacks against 
> the *full* version!) into an attack that incrementally exposes the 
> hidden RNG state. I've asked a couple such people whether they 
> think that's likely, and they've said yes.

My question was whether the variant laced with the cycle counter 
could be exposable.

I'd say that's almost impossible physically, in all but the most 
trivial cases. Yes, you can do it with a static PRNG and a static 
pool, but neither pool is static in reality (irqs are coming in all 
the time) nor is the cycle counter static. The cycle counter will 
mix in things like cache miss delays.

You need a really, really fast probe and a really quiet system to 
pull off a statistical attack like that. In all other realistic 
cases you have to play catch-up with the current state of the pool, 
trying to guess it. And even if you have a reasonably good idea 
about it, there's no _guarantee_ that your guess about the pool's 
state is when a critical context you'd like to attack seeds its ASLR 
or whatever other secret state.

> In fact, it's been known for over a decade that reduced-round MD4 
> such as ours is *not one way* and that preimages (aka our hidden 
> state) can be found in less than an hour on a *mid-90s era PC*:
> 
> http://citeseer.ist.psu.edu/old/182935.html

But that is completely inapposite to the PRNG i posted. Getting to 
preimage in a static MD4 hash where you have a reasonable number of 
probes right after the unknown result is possible.

Eliminating cycle counter noise out of a _static_ secret permutated 
via a PRNG is probably also possible, if the probe can be done 
faster than the natural noise level of the cycle counter is.

_Combining_ the two and attacking _that_ (combined with the addition 
of jiffies and a kernel stack address) - seems close to impossible 
to me. You'd have to guess the precise cycle counter value at the 
point of the hashing, and your samples wont help with that. They 
might give an estimation, but that's really what ASLR is about: the 
moment an attack isnt 100% sure, other measures (such as crash 
monitoring) can save the day.

The really serious attackers avoid uncertainty like the plague. 

It's the same reason why three letter agencies rather drop slam-dunk 
court cases than expose their sources and methods. A failed attack 
against a system exposes the attack and since the attack failed, 
there's no way to erase traces of the attack.

Furthermore, ASLR is mostly about changing the dynamics of worm 
attacks via the network. If an attack has only a 10% chance to 
succeed, that might break the propagation dynamics of a worm. So 
just a handful of bits are enough there.

> Combine that with greatly improved techniques for attacking hashes 
> in the MD4 family in the last five years and you're probably 
> looking at less than a second of CPU time. Combine that with the 
> fact that we're using the hash in a feedback mode, and things only 
> get easier.
> 
> On the question of 'what if we add in the TSC?', I'd first say (a) 
> we can't and shouldn't assume a TSC is available, though we 
> certainly should use it if it is. Second I'd say that there are 
> numerous timing attacks that have been done that suggest that 
> guessing the TSC can be done with useful probability. For 
> instance, see the branch prediction attacks against AES and RSA.

That is something completely different again, and i'm not sure 
whether you are trolling here or not...

Branch prediction attacks against AES and RSA are _completely 
different_ and the TSC connection is only there in name. They are 
about using timing as a _sample_ of the secret state and its effects 
on runtime.

Here the TSC is taken once, and mixed. _This_ TSC is not taken ever 
again, nor saved. There's no statistical method to recover it! You 
might know it up to a certain precision if you are lucky and can run 
right after the call, but a couple of bits of true randomness will 
be there for sure. In most cases more than a coupleof bits - an exec 
takes 200-300 usecs and you have to run on that same CPU - so to get 
a sample you have to go back almost 1 million TSC cycles ... That's 
20 bits of TSC space.

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

Powered by blists - more mailing lists