On Sat, Dec 08, 2007 at 05:20:16PM -0600, Matt Mackall wrote:
> random: use xor for mixing
>
> With direct assignment, we can determine the twist table element used
> for mixing (the high 3 bits of the table are unique) and reverse a
> single step of mixing. Instead, use xor, which should also help
> preserve entropy in a given pool slot.
>
> Signed-off-by: Matt Mackall <[email protected]>
>
> diff -r bc336762cfdb drivers/char/random.c
> --- a/drivers/char/random.c Wed Dec 05 17:20:02 2007 -0600
> +++ b/drivers/char/random.c Sat Dec 08 13:27:34 2007 -0600
> @@ -496,7 +496,7 @@ static void __add_entropy_words(struct e
> w ^= r->pool[(i + tap4) & wordmask];
> w ^= r->pool[(i + tap5) & wordmask];
> w ^= r->pool[i];
> - r->pool[i] = (w >> 3) ^ twist_table[w & 7];
> + r->pool[i] ^= (w >> 3) ^ twist_table[w & 7];
> }
In the original design of add_entropy_words(), in order to provably
not lose any entropy, you want add_entropy_words() to be reversible if
you mix in all zero's. So the fact that you can determine the twist
table element used from looking at the high bits was deliberate. The
mixing done in add_entropy_words() is *not* intended to be
cryptographic, but merely to smear the bits around as they are added
and then to permute the pool so that when you use SHA in the output
stage, enough bits are changing that even if there are weaknesses
discovered in the crypto hash algorithm, it won't help the attacker.
The internals of the pool are never exposed, so an attacker should
never gain direct access to the entropy pool; hence worry about
whether someone can "reverse" the mixing isn't particuarly a worry;
indeed, in order to make sure we preserve entropy, the whole *point*
of the mixing algorithm is that it is reversible.
(note: credit for this design should go to Colin Plumb, who worked
with me on this aspect of the design. Colin was responsible for the
original random number generator in PGP....)
- Ted
On Sat, Dec 08, 2007 at 07:01:04PM -0500, Theodore Tso wrote:
> On Sat, Dec 08, 2007 at 05:20:16PM -0600, Matt Mackall wrote:
> > random: use xor for mixing
> >
> > With direct assignment, we can determine the twist table element used
> > for mixing (the high 3 bits of the table are unique) and reverse a
> > single step of mixing. Instead, use xor, which should also help
> > preserve entropy in a given pool slot.
> >
> > Signed-off-by: Matt Mackall <[email protected]>
> >
> > diff -r bc336762cfdb drivers/char/random.c
> > --- a/drivers/char/random.c Wed Dec 05 17:20:02 2007 -0600
> > +++ b/drivers/char/random.c Sat Dec 08 13:27:34 2007 -0600
> > @@ -496,7 +496,7 @@ static void __add_entropy_words(struct e
> > w ^= r->pool[(i + tap4) & wordmask];
> > w ^= r->pool[(i + tap5) & wordmask];
> > w ^= r->pool[i];
> > - r->pool[i] = (w >> 3) ^ twist_table[w & 7];
> > + r->pool[i] ^= (w >> 3) ^ twist_table[w & 7];
> > }
>
> In the original design of add_entropy_words(), in order to provably
> not lose any entropy, you want add_entropy_words() to be reversible if
> you mix in all zero's.
Ahh, yes, that's true. I'd somehow missed that we effectively had a
tap at 0, so I thought this was actually improving the situation. I'll
replace this with a comment explaining the situation.
> The internals of the pool are never exposed, so an attacker should
> never gain direct access to the entropy pool; hence worry about
> whether someone can "reverse" the mixing isn't particuarly a worry;
> indeed, in order to make sure we preserve entropy, the whole *point*
> of the mixing algorithm is that it is reversible.
I'm working on strengthening forward security for cases where the
internals are exposed to an attacker. There are any number of
situations where this can and does happen, and ensuring we don't
expose ourselves to backtracking is a worthwhile theoretical concern.
---
random: document revisibility of mixing function.
Signed-off-by: Matt Mackall <[email protected]>
diff -r bc336762cfdb drivers/char/random.c
--- a/drivers/char/random.c Wed Dec 05 17:20:02 2007 -0600
+++ b/drivers/char/random.c Sat Dec 08 18:38:15 2007 -0600
@@ -447,6 +447,12 @@ static struct entropy_store nonblocking_
* degree, and then twisted. We twist by three bits at a time because
* it's cheap to do so and helps slightly in the expected case where
* the entropy is concentrated in the low-order bits.
+ *
+ * This function is intentionally reversible, meaning that if we mix
+ * in known values, we can run the algorithm backwards and recover the
+ * earlier state. Because we can recover the original state, we are
+ * provably not destroying any existing entropy content in the pool
+ * when we mix.
*/
static void __add_entropy_words(struct entropy_store *r, const __u32 *in,
int nwords, __u32 out[16])
--
Mathematics is the supreme nostalgia of our time.
On Sat, Dec 08, 2007 at 06:40:17PM -0600, Matt Mackall wrote:
> I'm working on strengthening forward security for cases where the
> internals are exposed to an attacker. There are any number of
> situations where this can and does happen, and ensuring we don't
> expose ourselves to backtracking is a worthwhile theoretical concern.
See my other comments; I don't think we are currently vulnerable to
backtracking.
I tend to view backtracking as largely a theoretical concern, as most
of the time, if the attacker has read access to kernel memory in order
to compromise the internal state of /dev/random, the attacker very
likely has *write* access to kernel memory, at which point you have
much bigger problems to worry about, at least going forward.
I suppose if you had *just* generated an 80-bit AES session key, right
before the internal state was compromised, this might be interesting,
but if the attacker can compromise arbitrary kernel memory, then
attacker might as well just grab keying information from the userspace
process --- such as perhaps the long-term private key of the user, or
the data to be encrypted.
So my personal take on it is that protecting against backtracking
attacks is mainly useful in silencing academics who like to come up
with, well, largely academic and theoretical scenario. If it doesn't
take much effort, sure, let's try to protect against it (and I think
we're OK already).
But a much better use of our time would be spent creating userspace
support so we can more efficiently pull entropy from TPM modules, or
the noise from a sound/microphone input, etc., or other hardware
sources of entropy. That would provide a much more practical
improvement to the /dev/random subsystem than worry about what I feel
are largely academic concerns.
Regards,
- Ted
> So my personal take on it is that protecting against backtracking
> attacks is mainly useful in silencing academics who like to come up
> with, well, largely academic and theoretical scenario. If it doesn't
> take much effort, sure, let's try to protect against it (and I think
> we're OK already).
That problem seems to arise here because we have an interface to add
'real' entropy to the pool but not one to add randomness to be used
solely for urandom. If we had both then the user could choose to add some
degree of randomness solely for urandom usage.
Alan
Theodore Tso wrote:
> On Sat, Dec 08, 2007 at 06:40:17PM -0600, Matt Mackall wrote:
>> I'm working on strengthening forward security for cases where the
>> internals are exposed to an attacker. There are any number of
>> situations where this can and does happen, and ensuring we don't
>> expose ourselves to backtracking is a worthwhile theoretical concern.
>
> See my other comments; I don't think we are currently vulnerable to
> backtracking.
>
> I tend to view backtracking as largely a theoretical concern, as most
> of the time, if the attacker has read access to kernel memory in order
> to compromise the internal state of /dev/random, the attacker very
> likely has *write* access to kernel memory, at which point you have
> much bigger problems to worry about, at least going forward.
>
> I suppose if you had *just* generated an 80-bit AES session key, right
> before the internal state was compromised, this might be interesting,
> but if the attacker can compromise arbitrary kernel memory, then
> attacker might as well just grab keying information from the userspace
> process --- such as perhaps the long-term private key of the user, or
> the data to be encrypted.
>
> So my personal take on it is that protecting against backtracking
> attacks is mainly useful in silencing academics who like to come up
> with, well, largely academic and theoretical scenario. If it doesn't
> take much effort, sure, let's try to protect against it (and I think
> we're OK already).
>
> But a much better use of our time would be spent creating userspace
> support so we can more efficiently pull entropy from TPM modules, or
> the noise from a sound/microphone input, etc., or other hardware
> sources of entropy. That would provide a much more practical
> improvement to the /dev/random subsystem than worry about what I feel
> are largely academic concerns.
That doesn't actually sound too hard, and the sounds of passing traffic
are not likely to be replicable in any case. Lots of sensor data might
be used as well, fan rpm, etc. That sounds so obvious I can't believe
there isn't a reason it's not being done.
--
Bill Davidsen <[email protected]>
"We have more to fear from the bungling of the incompetent than from
the machinations of the wicked." - from Slashdot