RE: [PATCH] x86/entry/64: randomize kernel stack offset upon syscall
From: David Laight
Date: Wed Apr 17 2019  05:27:30 EST
From: Reshetova, Elena
> Sent: 16 April 2019 17:47
..
> > It seems though the assumption that we're assuming the attacker has
> > arbitrary ability to get the low bits of the stack, so *if* that's
> > true, then eventually, you'd be able to get enough samples that you
> > could reverse engineer the prandom state. This could take long enough
> > that the process will have gotten rescheduled to another CPU, and
> > since the prandom state is percpu, that adds another wrinkle.
>
> Well, yes, this is also my feeling that it is going to be hard to do, but can we get
> some more concrete numbers of this? We can forget about percpu rescheduling
> for simplicity and just calculate how many calls it would take to recover the state
> given that each call leaks 5 bits.
If you can guarantee back to back requests on the PRNG then it is probably
possible to recalculate its state from 'bits of state'/5 calls.
Depend on the PRNG this might be computationally expensive.
For some PRNG it will be absolutely trivial.
IIRC the kernel PRNG is just the xor of several crc, without any
addition or multiply operations it is probably analytically reversible.
Thinks further...
If it has 128 state bits, 26 consecutive outputs of 5 bits gives
you 130 linear equations in 128 unknowns  trivially solvable.
Stirring in a little bit of entropy doesn't help much either.
The entropy bits are effectively initial state bits.
Add 4 in with each request and 128 outputs gives 640 linear
equations in the (128 + 4 * 128) unknowns  still solvable.
The extra entropy does stop you completely predicting the following
outputs.
Of course, if the PRNG is nonlinear solving the equations is hard.
In that case you don't need to worry anywhere near as much about
feeding in more entropy bits than are being removed.
David

Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)