From: "Perry E. Metzger" <perry@piermont.com>
Date: Wed, 20 Sep 95 14:02:02 PDT
To: karlton@netscape.com (Phil Karlton)
Subject: Re: "random" number seeds vs. Netscape
In-Reply-To: <43psn2$6ug@tera.mcom.com>
Message-ID: <199509202101.RAA05534@frankenstein.piermont.com>
MIME-Version: 1.0
Content-Type: text/plain



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