PRNGs (was Re: machine independent protection from stack-smashing attack)

[John Viega <viega () LIST ORG>]

On Thu, Aug 10, 2000 at 03:05:57PM -0700, Yarrow Charnot wrote:
> ----- Original Message -----
> From: John Viega <viega () LIST ORG>
> To: <BUGTRAQ () SECURITYFOCUS COM>
> Sent: Thursday, August 10, 2000 8:05 PM
> Subject: Re: machine independent protection from stack-smashing attack
>
> > Our understanding is that the biggest reason why StackGuard hasn't
> > been ported to more architectures is that there's not really a
> > portable source of randomness available, such as a /dev/random.

> Not true! There sure are and have always been sources of randomness
> on all the platforms. It just always comes down to proper
> implementation. Sure you would need to add processor-dependent code
> for each platform, but there sure is a portable source of randomness
> available. It's called RDTSC on Intel, %tick on SPARC, etc. and it's
> a base for /dev/random anyway. However, the authors of /dev/random
> didn't conduct any research on its behaviour, missing out on its
> true power.

Yes; I backpeddled a bit on this one in my last post to the list once
I remembered TrueRand from Blaze et al., along with thread timing
stuff that you see in Java's SecureRandom class, etc (which appears to
be what you're doing, and is kinda similar to TrueRand, iirc).  So the
real reason why StackGuard hasn't been ported to other architectures
is probably something along the lines of Crispan not being all that
interested in doing it.  It *does* require hooking up whatever
randomness source, so it's a slight step above completely trivial.

As for what I think the world needs in this area... I think there
needs to be a good end-to-end solution for high-quality random numbers
in software that is widely ported and easily installed.  It should
deal with entropy accumulation, and actually emiting a string of
random numbers from that entropy.

In each of those two areas, I'd like to see a solution that people
will have faith in, much like people seem to have in /dev/random (but
perhaps even more faith than that).  I'd also like to see the
limitations of /dev/random overcome.  In particular, the biggest
limitation is the fact that /dev/random doesn't have reasonable
bandwidth; you have to use /dev/urandom for that, and I don't know as
if people are willing to trust it as much as /dev/random.

Having talked about this issue at great length with John Kelsey, I'm
pretty confident that once your algorithm reaches a state you believe
to be secure, then you should be able to output random numbers as fast
as the software can crank them out, as long as the internal state of
your algorithm isn't compromised.  I know many crypto types who aren't
willing to put that kind of faith into /dev/urandom.

The need for algorithms with better understood security properties is
one reason why John Kelsey and Bruce Schneier wrote the Yarrow
algorithm for pseudo-random number generation.  We've been working
with John in particular to implement a reference version of Yarrow;
the specification of Yarrow has been a moving target as a result.  I'm
hoping that when everything is done, the results will be an excellent
choice for what to use after you've collected entropy, on any
platform.

We have a little bit more implementation to do before that's ready for
the light of day.  Then, we need to work with John on validating the
implementation, which includes coming up with test vectors, etc.

As for collecting entropy, that's an area where it's a lot harder to
assure people as to how good a job you're doing.  The biggest problem
here is entropy estimation.  Decent (conservative) entropy estimation
is assumed when people analyze algorithms like Yarrow.  However,
demonstrating that entropy estimates are accurate is incredibly
difficult.  For example, with your thread timing approach, how much
entropy do you believe your entropy gathering function yield every
time?  How did you come up with that number?

I think it'd be great to distribute something that does a few
different things, and guesses entropy well, packaged along with
Yarrow, in a nice big package for every common platform.  We're
definitely trying to work toward that goal.  The whole entropy
estimation thing is the biggest hurdle.

One worry I have is whether the easily ported techniques alone (mainly
things that don't require code in the OS) are going to provide people
in the security and cryptography community with a good enough sense of
well-being.  For example, I think everybody would feel a lot more
comfortable if the OS were also feeding in keyboard and mouse entropy.
Building something like that for every major architecture would be a
significantly bigger challenge.

If we have good assurance as to the real amount of entropy provided by
each of these sources, then one might think the only real issue is how
fast you can get Yarrow (or whatever) into a secure state.  However, I
think people will want as many sources as possible, just in case
entropy estimates on one of them turn out to be way too high in
practice.

I'd love some input here.  Do people believe the asserted entropy
estimation for TrueRand on all platforms?  What other easily ported
techniques have good CONSERVATIVE entropy estimates attached that
people have some assurance in?

John