"random" number seeds vs. Netscape

Let me start off by saying that I speak for me and not Netscape. I
also tend to be UNIX centric since I know very little (nothing?) about
the internals of PCs and Macs.

I want to address the bug Netscape has with its currently released
product with respect to seed generation. For the most part this is not
a crypto issue, but rather a system issue.  Those bits of entropy can
only be gathered in a system dependent manner.

Assumption:

    We are relying on the MD5 hash algorithm to gather the string of
    potentially unpredictable sequences. I am assuming that feeding
    known bits along with the unknown will not compromise the
    "randomness" of the MD5 state.

    The basic idea is to feed a sequence of information into the MD5
    hash, expecting that some of the bits for each sub-sequence would
    be only be guessable. If we get enough unguessable bits into the mix,
    then the weak link in the chain would not be the seed generation.

Here is what the client will soon be doing:

    Netscape is available on Macs, Win-16 and Win-32 versions and
    8 different UNIX platforms. The exact details for each platform are
    quite system specific. The basic idea is to feed a sequence
    of information into the MD5 hash, expecting that some of the
    bits for each sub-sequence would be unguessable.

  At program start

    On all platforms:

	Start with the contents of the highest resolution clock we can
	find on the system. [For instance, an R4000 MIPS processor has
	a free-running instruction counter. At 100 Mhz this gets
	incremented every 10 nano-seconds. There are probably a good
	20 bits of unguessable value there.] On Macs and Win* systems
	there are "tick" counters that update 60 (or maybe only 16)
	times a second. We then push through the time of day, beacause
	on some sytems, the microsecond part of a time_val has some
	bits that are only guessable.

    For UNIX we feed the following into the MD5 hash:

	ps (-el or aux depending upon system)

	netstat -ni & netstat -na

	the user's environment. (We will certainly use this as well in
	the 2.0 release. The truly paranoid will be able to run
	whatever seed generator they want and stick the result into
	their environment. How you protect your environment from
	attack is up to you. ;-)

	System specific info such as hardware serial number or
	system id. If you have specific suggestions for any
	particular OS/hardware pair, please let me know.

    For PCs

	Cursor position

	Global memory status

	FreeSpace

	Drive configuration

	Number of running tasks

	Environment strings

	UUIDCreate if there is an ethernet card

	Clipboard owner and contents

	Current process, processID and window

	Free clusters on the disk

    For MACs:

	Machine location (longitude and latitude)

	User name

	Mouse location

	keyboard time threshhold

	last key pressed

	audio volume

	current directory

	current process

	process information for every task  on the system

	stack limits

	zones

	scrap sizes and counts

	event queue

    And then on all platforms

	The stat (file access, creation, modify times, size, inode
	equivalent) and contents of a number of "interesting" files.
	[Where is the PGP random number state file stored?]

	A portion of the contents of the screen.

	And finally, the contents of the highest resolution clock we
	can find.

  Each time the client goes idle

    Reinitialize the seed with the most recent user event (probably
    a button or key down) along with the mouse position, and and
    relatively high resolution clocks.

Known weaknesses:

    If your X display is not the local machine then the X protocol can
    be watched. Given that, the data for the reseeding of the MD5 hash
    will be compromised. [Any scheme that relies on random user input
    to generate a seed suffers from the same problem.]  This is not
    quite as bad as it might be. The exact time of the client becoming
    idle can only be guessed. We should be able to get a few
    unguessable bits from the microsecond part of the time-of-day
    clock each time. Enough cycles of user actions should help to make
    the hash less subject to a brute force attack.

    In fact, the entire X protocol issue is one that could take up
    another 3 pages. An SSLized version of the server would help,
    but how would anybody export it? You "xhost +" fans are doomed.

    If the user launches the client to a secure home page then there
    will be no user actions involved before the first need for a seed.

Thoughts on guessing:

    If Eve has root access to the user's workstation, all bets are off.
    Replacement of one of the system libraries or patching the client
    executable are among the attacks that would make it trivial to
    breach any part of the security. Specific measures (like computing
    a hash over the text of the program) could help against some of
    these attacks, but it is not realisitic to believe that we can
    prevent the attack from a sophisticated person with root access.

    Multi-user Unix machines present a special problem. There are those
    at Netscape that argue that anybody who has login access to your
    machine may as well be considered to have root access. There are
    enough known attacks that this is true to a large extent.  However,
    I think we can do better than just giving up. Unfortunately most of
    the sources of entropy available to the client are also available
    to the attacker. For instance, the output of "ps" is not much help
    against this form of attacker. As Jeff Weinstein said earlier and I
    echo here: specific suggestions are more than welcome.

    When Eve has access to the wire for all of the packets into and out
    of the user's workstation, then some of the networking information
    can be guessed. See above about known weaknesses if Eve has access
    to the X protocol stream.

    I am most comfortable about the "randomness" of the generated seed
    if Eve is outside a fire wall sniffing packets. The difficulty in
    guessing what processes/tasks are running on the target machine is
    quite a bit of help here.

What I would like:

    Any OS has access to a number of real-world physical sources of
    randomness. This information is not made available to a user level
    process. How long did that last seek take? Was there any noise on
    the microphone? It would be good if the OS could gather that
    information and make some set of bits available to any process that
    asks. Having this be part of all OSes would make my job easier.

    More specifically: A "getnoise()" system call in UNIX could be
    better than anything I can do and easier. Can we convince the UNIX
    vendors to start providing that?

    My life would have been simpler if this attack had been done after
    the 2.0 version of the client had been released. :-) Believe it or
    not, we were beginning to beef up the seed generation a couple of
    weeks ago. The time spent on patching the current release will not
    all go to waste, but it has cut down on my limited opportunities to
    sleep.

For those that curious: being responsible for helping to fix a bug that
is getting front page coverage in major newspapers is not nearly as
much fun as it sounds.

PK
--
Philip L. Karlton			karlton@netscape.com
Principal Curmudgeon			http://www.netscape.com/people/karlton
Netscape Communications Corporation

> 
> What I would like:
> 
>     Any OS has access to a number of real-world physical sources of
>     randomness. This information is not made available to a user level
>     process. How long did that last seek take? Was there any noise on
>     the microphone? It would be good if the OS could gather that
>     information and make some set of bits available to any process that
>     asks. Having this be part of all OSes would make my job easier.

We've got a *real* hardware random number generator that was developed
for our secure phones.  If you are seriously interested, we can
glue the RNG onto the end of a serial port for you.  It generates
about 8000 bits of uncorrelated noise / second.

Eric Blossom
COMSEC Partners
707-577-0409

Phil Karlton writes:
> I want to address the bug Netscape has with its currently released
> product with respect to seed generation. For the most part this is not
> a crypto issue, but rather a system issue.  Those bits of entropy can
> only be gathered in a system dependent manner.

Quite true.

> Assumption:
>     The basic idea is to feed a sequence of information into the MD5
>     hash, expecting that some of the bits for each sub-sequence would
>     be only be guessable. If we get enough unguessable bits into the mix,
>     then the weak link in the chain would not be the seed generation.

This is true. However, you must get 128 bits of entropy into the MD5
-- this can be accompanied by as much junk as you like, but if there
are at least 128 bits of entropy fed in, the MD5 process will distil
it into what you want.

You might want to read RFC 1750, and examine the code PGP uses for
doing its random generation. Clients do lots of fairly random things
while talking to netscape (click and keyboard press times, etc) that
can be incorporated in, along with other sources of bits. You should
grab bits whereever you can and keep them for when you need them, as
getting 128 bits takes a while.

> 	On Macs and Win* systems
> 	there are "tick" counters that update 60 (or maybe only 16)
> 	times a second.

PC timers inherently run at Mhz speed -- they interrupt every 100th of
a second but you can get finer resolution by querying the clock
chip. Does Windows let you do this?

By the way, starting with the time that the program was started is
okay but not great -- I think you probably can only safely assume a
few bits from this.

>     For UNIX we feed the following into the MD5 hash:
> 
> 	ps (-el or aux depending upon system)

I wouldn't do that, since it forces you to have a dependancy on
executing a subprocess. 

Were I you, I'd capture the timer on every single keystroke and mouse
click event and feed that in to your entropy generator a la PGP.

> 	System specific info such as hardware serial number or
> 	system id.

By definition, that isn't random. Don't use it.

There are other things you can mix in, besides keystroke and mouse
timings and positions, like system call timings for things that might
take a bit of time.

I can't speak to things on PCs, but...

> 	UUIDCreate if there is an ethernet card

No, sorry, this is very non-random.

>     For MACs:
> 	Machine location (longitude and latitude)

Non-random.

> 	User name

Non-random.

> 	audio volume

Doesn't change very often.

> Known weaknesses:
> 
>     If your X display is not the local machine then the X protocol can
>     be watched. Given that, the data for the reseeding of the MD5 hash
>     will be compromised. [Any scheme that relies on random user input
>     to generate a seed suffers from the same problem.]

Thats true, but its better than it could be, and most users will be
running local.

>     In fact, the entire X protocol issue is one that could take up
>     another 3 pages. An SSLized version of the server would help,
>     but how would anybody export it? You "xhost +" fans are doomed.

You guys should quit thinking of SSL as a good idea. It might be that
the concept is useful for backward compatibility, but don't think of
it as the universal solution just because you developed it.

>     Multi-user Unix machines present a special problem. There are those
>     at Netscape that argue that anybody who has login access to your
>     machine may as well be considered to have root access. There are
>     enough known attacks that this is true to a large extent.  However,
>     I think we can do better than just giving up.

I agree. Don't run on the assumption that everyone has root --
otherwise you'll build something that produces less safety than it could.

> What I would like:
> 
>     Any OS has access to a number of real-world physical sources of
>     randomness. This information is not made available to a user level
>     process. How long did that last seek take? Was there any noise on
>     the microphone? It would be good if the OS could gather that
>     information and make some set of bits available to any process that
>     asks. Having this be part of all OSes would make my job easier.
> 
>     More specifically: A "getnoise()" system call in UNIX could be
>     better than anything I can do and easier. Can we convince the UNIX
>     vendors to start providing that?

Actually, Ted Tso built a /dev/rand for Linux, and there are people
trying to port it to other platforms. This is probably a better idea
than a system call.

> For those that curious: being responsible for helping to fix a bug that
> is getting front page coverage in major newspapers is not nearly as
> much fun as it sounds.

I've lost my share of nights to security holes announced late in the
day that HAD to be fixed for clients within hours. Welcome to the real
world. You play with the big boys and you get big headaches every once
in a while.

Perry

Perry E. Metzger wrote:
> This is true. However, you must get 128 bits of entropy into the MD5
> -- this can be accompanied by as much junk as you like, but if there
> are at least 128 bits of entropy fed in, the MD5 process will distil
> it into what you want.

My assumption ws that if we conservatively counted at least 300 bits of entropy,
we would have 128 for sure. Not very scientific, 

> You might want to read RFC 1750,

Did that. It talks about a lot of the pitfalls. Unfortunately it does not address
(nor can it realistically be expected to address) details of what to look for
on a particular version of an OS running on some particular platform.

> and examine the code PGP uses for
> doing its random generation. Clients do lots of fairly random things
> while talking to netscape (click and keyboard press times, etc) that
> can be incorporated in, along with other sources of bits. You should
> grab bits whereever you can and keep them for when you need them, as
> getting 128 bits takes a while.

Gee, I thought I pointed out that we were putting that code in as part of
the going idle.

> PC timers inherently run at Mhz speed -- they interrupt every 100th of
> a second but you can get finer resolution by querying the clock
> chip. Does Windows let you do this?

I don't know, but I'll forward this on to our PC guys. It might be a portability
problem.

> I wouldn't do that, since it forces you to have a dependancy on
> executing a subprocess.

We try to be careful about dealing with the subprocess failing to run.

> Were I you, I'd capture the timer on every single keystroke and mouse
> click event and feed that in to your entropy generator a la PGP.

We are constantly trying to improve this area of our code. We are still taking
suggestions.

By the way, the security engineers are doing what we can to make sure that we
can expose as much of the seed generation algorithms as possible. There is a
chance we can get permission to post the code.

> >       System specific info such as hardware serial number or
> >       system id.

> By definition, that isn't random. Don't use it.

It doesn't hurt. It's also information that is not available to the external
evesdropper. Other than execution time, why should I remove it from the list
of bits being fed into the hash? Successfully getting this information probably
involves physical access to the machine.

> There are other things you can mix in, besides keystroke and mouse
> timings and positions, like system call timings for things that might
> take a bit of time.

We will check this one out also. For the really low resolution clocks, the
answer will be zero most of the time. :-)

> >     Multi-user Unix machines present a special problem. There are those
> >     at Netscape that argue that anybody who has login access to your
> >     machine may as well be considered to have root access. There are
> >     enough known attacks that this is true to a large extent.  However,
> >     I think we can do better than just giving up.
> 
> I agree. Don't run on the assumption that everyone has root --
> otherwise you'll build something that produces less safety than it could.

I agree, but I have a hard arguing with those that asser that the security
of UNIX is weak enough that given what we are doing for the patch it will
be easier to become root from a logged in account than to hack the seed.

PK
--
Philip L. Karlton			karlton@netscape.com
Principal Curmudgeon			http://www.netscape.com/people/karlton
Netscape Communications Corporation

Perry Metzger writes:
# You might want to read RFC 1750,

Phil Karlton writes:
> Did that. It talks about a lot of the pitfalls. Unfortunately it does not 
> address (nor can it realistically be expected to address) details of what
> to look for on a particular version of an OS running on some particular 
> platform.

Can someone point me to a compilation of such information ?  If not, I'm
definitely interested in starting a Web page to chronicle recommendations
about good, bad, and questionable random and pseudo-random sources for
specific architectures and operating systems. (It could also include
information on special-purpose plug-in hardware RNGs.)

-Futplex <futplex@pseudonym.com>

Phil Karlton writes:
> Perry E. Metzger wrote:
> > This is true. However, you must get 128 bits of entropy into the MD5
> > -- this can be accompanied by as much junk as you like, but if there
> > are at least 128 bits of entropy fed in, the MD5 process will distil
> > it into what you want.
> 
> My assumption ws that if we conservatively counted at least 300 bits
> of entropy, we would have 128 for sure. Not very scientific,

Its not a bad way to go. You have to make sure that you have at least
that many bits of ENTROPY, however. Stuff like keystroke timings
should only be thought of as handing you a bit or so per click.

> > You might want to read RFC 1750,
> 
> Did that. It talks about a lot of the pitfalls. Unfortunately it
> does not address (nor can it realistically be expected to address)
> details of what to look for on a particular version of an OS running
> on some particular platform.

That is true. 

> > PC timers inherently run at Mhz speed -- they interrupt every 100th of
> > a second but you can get finer resolution by querying the clock
> > chip. Does Windows let you do this?
> 
> I don't know, but I'll forward this on to our PC guys. It might be a
> portability problem.

It actually shouldn't be -- every PC has the same timer chip or a
compatible one. The real question is whether Windows lets you get the
data out.

> > I wouldn't do that, since it forces you to have a dependancy on
> > executing a subprocess.
> 
> We try to be careful about dealing with the subprocess failing to run.

Also be especially careful about how you run the thing! Don't use
popen or anything like it!

> > >       System specific info such as hardware serial number or
> > >       system id.
> 
> > By definition, that isn't random. Don't use it.
> 
> It doesn't hurt. It's also information that is not available to the external
> evesdropper. Other than execution time, why should I remove it from the list
> of bits being fed into the hash?

You have to build to the model of someone who knows everything there
is to know about the machine. Why? Well, many pieces of information
can in fact be extracted -- license servers and SNMP agents are a way
to extract things like system IDs. (Overly chatty SNMP extensions and
similar stuff make me nervious about using too much ps based entropy,
by the by.)

If you put PROM ID into the hash, don't count it as a source of bits
-- just think of it as something extra to throw in to make life harder
-- and heavily comment that it is not to be counted in the magic 300
bits you are trying to extract. Remember, plan for the worst, not the
best, and you will never have trouble if the threat model gets worse.

As a security consultant, I always emphasize to clients that you have
to plan for worst case -- always. That way you can sleep at
night. Always assume the adversary has a way to break the individual
components of your system.

When I build firewalls, I rig them so that both an outer filtering
router, a tightened down application gateway, and an inner filtering
router must all fail in order for people to break in. I build things
on the assumption of maximum hostility on all points. Because of this,
every time a security hole has been announced for the last couple of
years -- in CISCO firmware, in Sendmail, in anything -- I've been able
to sleep because I've known that only one of many layers of protection
has been breeched and I have a few hours to fix the one layer that is
broken.

When building things like this, BUILD PARANOID. It never hurts.

> > >     Multi-user Unix machines present a special problem. There are those
> > >     at Netscape that argue that anybody who has login access to your
> > >     machine may as well be considered to have root access. There are
> > >     enough known attacks that this is true to a large extent.  However,
> > >     I think we can do better than just giving up.
> > 
> > I agree. Don't run on the assumption that everyone has root --
> > otherwise you'll build something that produces less safety than it could.
> 
> I agree, but I have a hard arguing with those that asser that the security
> of UNIX is weak enough that given what we are doing for the patch it will
> be easier to become root from a logged in account than to hack the seed.

Always build belt-and-suspenders around any security system. Try to
make sure that there are as many ways as possible that things have to
fail before you get nuked. Throwing an impediment in the way of
non-root users is a good idea. You program it once and it protects
forever -- an excellent investment.

Perry

>     weeks ago. The time spent on patching the current release will not
>     all go to waste, but it has cut down on my limited opportunities to
>     sleep.
> 
> For those that curious: being responsible for helping to fix a bug that
> is getting front page coverage in major newspapers is not nearly as
> much fun as it sounds.
> 

	This looks really good. I only wish your PR people wouldn't
spout the garbage that they do.

	In terms of your amounts of sleep-- If netscape had waited a
month before releasing the patch it would not have been doing any
worse than most OS vendors. Netscape is to be congratulated on the
quick response.


-- 
sameer						Voice:   510-601-9777
Community ConneXion				FAX:	 510-601-9734
An Internet Privacy Provider			Dialin:  510-658-6376
http://www.c2.org (or login as "guest")			sameer@c2.org