[lkml]   [2009]   [May]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [Security] [PATCH] proc: avoid information leaks to non-privileged processes

* Matt Mackall <> 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*:

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.


 \ /
  Last update: 2009-05-07 20:47    [W:0.088 / U:15.324 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site