Message-ID: <20121216003020.GC9016@thunk.org>
Date:	Sat, 15 Dec 2012 19:30:20 -0500
From:	Theodore Ts'o <tytso@....edu>
To:	Stephan Mueller <smueller@...onox.de>
Cc:	Andrew Morton <akpm@...ux-foundation.org>,
	lkml <linux-kernel@...r.kernel.org>,
	Jeff Liu <jeff.liu@...cle.com>,
	Kees Cook <keescook@...omium.org>
Subject: Re: [PATCH] avoid entropy starvation due to stack protection

On Fri, Dec 14, 2012 at 06:36:41PM +0100, Stephan Mueller wrote:
> >> That patch is about one week from a mainline merge, btw.
> > Initially I was also thinking about get_random_int. But stack protection
> > depends on non-predictable numbers to ensure it cannot be defeated. As
> > get_random_int depends on MD5 which is assumed to be broken now, I
> > discarded the idea of using get_random_int.

The original use of get_random_int() was for applications where the
speed impact of using a heavierweight cryptographic primitive was not
something which could be tolerated.

However, the strength of get_random_int() is actually pretty good.
Note that we never expose the full MD5 hash; we only export the first
32-bits of the hash.   So even if you ignore the effects of:

	hash[0] += current->pid + jiffies + get_cycles();

What we effectively have is a deterministic RNG which is using MD5,
where the secret "key" is an initially seeded random value, and the
state counter is the MD5 hash accumulator, where we only expose the
first 32-bits with each turn of the crank.  Now, MD5 has been cracked,
but it's been cracked as a cryptographic checksum --- that is, given a
particular MD5 hash, it is possible to find an input value which will
result in that hash.  That doesn't necessarily mean that it can be
possible to take a stream of numbers produced by using the MD5 core in
this particular RNG configuration, and determine the secret value used
for the RNG (a collision attack allows you to find a possible input
value; that value may not be the one used as the secret).

That being said, it's not a question which has been studied
extensively by cryptographers, and so I can easily see how people
might be paranoid about whether this approach is good enough.

In the case of initializing 16 bits of randomness passed to userspace
after a exec(), performance is presumably not as important, so if
someone wanted to use something that was stronger from a
certificational point of view than get_random_int(), that's certainly
understandable.  However, it's not clear to me that replicating the
full /dev/random pool infrastructure if you're never going to mix in
any additional randomness is the best way to go about things.

What I would do instead is use an AES-based cryptographic random
number generator.  That is, at boot time, grab enough randomness to
for an AES key, and then use that key to create a cryptographic random
number generator by encrypting a counter with said AES key.  This is a
cryptographic primitive which has been very carefully studied, and for
architectures where you have a hardware support for AES (including
ARMv8, Power 7, Sparc T4, as well as x86 processors with the AES-NI
instructions), this will be much faster and require much less memory
and CPU resources than replicating the /dev/urandom infrastructure.

Whether or not we really need this level of paranoia for hardening
stack randomization I'll leave for someone else to decide.
Personally, my philosophy is if someone has managed to get
unprivileged shell acess, trying to protect against a privilege
escalation attack is largely hopeless on most Linux systems.  The name
of the game is to protect against someone who does not yet have the
ability to run arbitrary unprivileged code on the system of interest.
In that case, the attacker isn't going to be able to get access to the
output of get_random_int(), so even if there was a cryptographic
weakness where an attacker who had access to the get_random_int()
output stream could guess the internal state of the MD5-based RNG, in
the case of a remote attacker, they wouldn't have access to the output
of the RNG in the first place.

Regards,

						- Ted
--
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