Re: Cryptosplit 2.0

From: m5@vail.tivoli.com (Mike McNally)
> On UNIX systems, where keystroke timing can be problematic, couldn't a
> collection of various system metrics be used to provide a bunch of
> reasonable pseudo-random bits?  Things like:
> 
> *	Disk space in /
> *	Network activity (in/out packet counts)
> *	load average
> *	swap space available
> *	time of day (duhh)

These can play a role in seeding a RNG, but there is probably not as
much randomness there as you might expect.  Knowledge of the approximate
time of day the program was run, plus some general information about the
characteristics of your system in terms of usage, can probably pin most
of those values down to within a factor of 5 or so.

I think multiple MD5 hashes of the total contents of /tmp (or, better,
/swap, if you can access that) would have more bits of randomness.  In
any case, Shamir sharing requires a LOT of random bits ("k" times the
size of the file) so at best these sources of randomness could seed a
RNG, which would then "amplify" the randomness (in a cryptographic
sense) to produce the random bits needed for the sharing algorithm.

I believe the RIPEM public key package by Mark Riordan has a fairly wide
repertoire of techniques for searching for randomness, including some of
the above ideas.  This code might be worth adapting to a general-purpose
entropy-seeking algorithm.  The problem is that these kinds of things are
highly system dependent.  If you have an audio port, for example, listening
to an unconnected microphone can produce a steady stream of noise.  Or if
you have a high-speed timer it can be used to get perhaps a couple dozen
bits of randomness at program-startup time, or to get many bits per keystroke.
So you have to have customization for each target system to be useful.
I do think the RIPEM code would be a good starting point, though.

I once proposed a DOS TSR (a "background" program) which would monitor
your keystrokes all day long and condense the timing data into a file
full of random bits.  Then you'd use up the bits when you needed to do
cryptography.  I haven't learned enough about DOS to write such a
thing, though.

Hal Finney
hfinney@shell.portal.com

From: m5@vail.tivoli.com (Mike McNally)
> On UNIX systems, where keystroke timing can be problematic, couldn't a
> collection of various system metrics be used to provide a bunch of
> reasonable pseudo-random bits?  Things like:

> I think multiple MD5 hashes of the total contents of /tmp (or, better,
> /swap, if you can access that) would have more bits of randomness.  In
> any case, Shamir sharing requires a LOT of random bits ("k" times the
> size of the file) so at best these sources of randomness could seed a
> RNG, which would then "amplify" the randomness (in a cryptographic
> sense) to produce the random bits needed for the sharing algorithm.

If I remember coorectly it's KerberosV uses an MD5 hash of /dev/mem.
This covers everything reported by "ps", "netstat", "iostat",
"vmstat", "pstat", and a lot more kernel stuff that's very difficult
to predict for any machine that's up and running on a busy network
for more than a few hours.

Still, probably not 128 bits worth of entropy.


brad

Brad Huntting writes:
 > If I remember coorectly it's KerberosV uses an MD5 hash of /dev/mem.
 > 
 > Still, probably not 128 bits worth of entropy.

Gee, that seems pretty amazing.  On a typical workstation, there's a
heck of a lot going on; in the megabytes of data in /dev/mem I'd think
it quite unlikely that there's a practical way to predict or recreate
a configuration.

Then again, I could be wrong.  I also wonder how, if the above is
true, one can really get 128 bits of entropy from keyboard timing
(especially from a small number of keypresses).

--
Mike McNally : m5@tivoli.com : Day Laborer : Tivoli Systems : Austin, TX
------------------------------------------------------------------------
Remember that all experimentation does not produce extrapolated results.
                                                           - k. pisichko

Brad Huntting writes:
> If I remember coorectly it's KerberosV uses an MD5 hash of /dev/mem.
> 
> Still, probably not 128 bits worth of entropy.

Mike responds:
> Gee, that seems pretty amazing.  On a typical workstation, there's a
> heck of a lot going on; in the megabytes of data in /dev/mem I'd think
> it quite unlikely that there's a practical way to predict or recreate
> a configuration.

Well, Assuming I was just creating a key and not doing something
else at the same time, it would be pretty easy to predict what
processes were running.  It has about 6000 pages of physical memory.
From knowing what processes are running, you could probably narrow
down the pages they would have in memory to at most half again that
number.  This gives you mabey 9000 choose 6000 posiblilitys for
what process memory looks like.  That gives about exp(3000*ln(7000))
or 2^37k posiblilities...  I suppose that is more than 128 bits.

So if you cant predict which pages will land where in memory (which
may be a false assumption), this is probably a good method for
getting a random number on a unix box.


brad

Brad Huntting writes:
 > > Still, probably not 128 bits worth of entropy.
 > 
 > Mike responds:
 > > Gee, that seems pretty amazing.
 > 
 > Well, Assuming I was just creating a key and not doing something
 > else at the same time, it would be pretty easy to predict what
 > processes were running...

I guess that's what I consider the amazing part.  Right now, I'm
sending mail via emacs.  I'm doing a big "make" in another window
(oh, it just finished).  I've got a FrameMaker session up.  I've got a
bug tracking database up.  I've got 4 local xterms and three rlogged
in to other systems.  I've got the Sun calendar tool running, and a
Lucid emacs window from another host.  I've got my own dynamic
X root window toy running.  I've got Tivoli's product up, I think, and
some other people are doing unknown things through that as part of a
test cycle.  (Yes, this ELC is maxed out.)

Given all that, it's hard for me to believe that some nefarious party
could be tracking system state thoroughly enough to be able to
reconstruct the contents of /dev/mem at any given time.

Of course, I could be thinking non-rigorously.  I suppose that,
strictly speaking, the blizzard of activity on my workstation gives me
no *real* protection.  Seems odd, but I guess I really can't make that
call.

--
Mike McNally : m5@tivoli.com : Day Laborer : Tivoli Systems : Austin, TX
------------------------------------------------------------------------
Remember that all experimentation does not produce extrapolated results.
                                                           - k. pisichko

Brad Huntting says:
> So if you cant predict which pages will land where in memory (which
> may be a false assumption), this is probably a good method for
> getting a random number on a unix box.

It might be a decent way to get *A* random number, but if you start
milking this source too frequently you will likely start getting more
and more correlation.

Myself, I'm still in search of a decent, inexpensive, high-quality
source for random numbers, and only hardware will REALLY do.

Perry