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

[Crispin Cowan <crispin () WIREX COM>]

John Viega wrote:

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

The above is correct.  We have not ported StackGuard off of Linux/x86
because we're not motivated to do so.  It's open source code, so anyone
is welcome to do the port if they wish.

The StackGuard patch is not intrinsically portable across processors
because it is low enough in the compiler to be manipulating the
individual instructions emitted to set up and tear down functions.
Porting StackGuard simply requires emitting the corresponding
instructions for different processors.  One StackGuard user told me that
they had ported StackGuard to Solaris/SPARC, but I never got the code
back.

Porting to many non-Linux x86 platforms should be trivial:  StackGuard
depends on:

   * gcc
   * x86
   * ELF

so it should work out of the box on *BSD.  I don't have any BSD
machines, so I don't claim that it works.  However, I have had people
tell me that they've used it on BSD platforms, but again, I never got
the code back.

The source of randomness issue is of no real import in StackGuard
portability.


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

Software randomness is intrinsically impossible.  Software is
deterministic.  You need an external source of entropy, and that means
you need access to I/O devices.  If you do it at a user level, it can be
spoofed.  Therefore, the only really good source of randomness is an OS
device.  /dev/random is a fine OS random source device in Linux.  If it
hasn't been ported to your favorite OS, then it should be.


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

/dev/random gives you as much bandwidth as it can; it blocks when the
entropy pool goes dry.  To get more bandwidth, you need a higher
bandwidth source of external entropy.

Intel at one point was planning to put a random bitstream generator in
an up-coming CPU.  However, because a random device is difficult to
deterministically test :-) this device was moved from the CPU to the
chip set.

I am told that /dev/random does not yet use this device because Intel
hasn't released the specs on accessing it.  This info is 3rd hand, so
persons more directly involved should confirm.


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

I find this claim difficult to believe.  If you start with a fixed-size
random seed and a fixed algorithm, and you output an arbitrary amount of
bits, then eventually you give the attacker enough bits to be able to
infer the initial random seed.  Once the seed has been disclosed, the
generator becomes a fixed pseudorandom number generator, and the
attacker can predict all future bits.

Caveat:  I am not a cryptographer.

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

/dev/random does do this.  On your favorite single-user Linux machine:

   * in one window, type "cat /dev/random | od -x"
   * notice that it blocks after a few lines
   * sit patiently, notice that it will output very few lines
   * type some stuff in another window:  notice the enhanced output
   * mouse around:  notice lots of output

These hooks are inside the kernel, because they are looking at entropy
in interrupt arrival time.  This can't be done in a user-level library.

More importantly, a user-level library can be spoofed.  Putting your
entropy source in a device ensurse that non-root users cannot spoof the
randomness source.

Note:  I'm not saying that /dev/random is perfect.  Certainly it seems
possible to enhance the algorithm so that it can streach the entropy
pool further.  It would definitely be a good idea to enhance the sources
of entropy, especially by accessing the Intel chip set entropy device.
I have also been told that Linux 2.4 will have a shorter time slice,
which may provodie additional sources of entropy (or maybe not,
depending on whether the scheduler is trusted to provide entropy).

Crispin

--
Crispin Cowan, Chief Scientist, WireX Communications, Inc.
http://wirex.com
Free Hardened Linux Distribution:
http://immunix.org