Re: Cryptosplit 2.0

Norm Hardy posted some code for Shamir secret sharing here about a month
ago, a nice short routine.  At around the same time, I created a program
to do the same thing and uploaded it to soda.  It is still in
/pub/cypherpunks/incoming as secsplit.zip.  It contains a DOS executable
and source for building under Unix or DOS.

I did the polynomial calculations a little differently from Norm and
Ray; their approaches may be more efficient.  But I did go to some
effort with the random-number generation on which the security of the
scheme depends.  My code uses the IDEA.C module from PGP for the
pseudo-random generator, seeding it with the time of day and an MD5
hash of the file being split.  So I think this should be pretty secure
in terms of the randomness involved.

The purpose of this program, as with Ray's and Norm's, is to split a file
into n pieces (all as big as the original file) such that any k of them
are sufficient to recover the original file, but k-1 pieces give you NO
information about the contents of the original file (other than its size).

One possible application is to split up your PGP secret key file this
way and distribute the pieces to trusted friends such that several of
them have to cooperate to recover your key.  Then if you accidentally lose
your key you can get the pieces back from your friends.

Hal

Hal Finney writes:
 > But I did go to some
 > effort with the random-number generation on which the security of the
 > scheme depends.  My code uses the IDEA.C module from PGP for the
 > pseudo-random generator, seeding it with the time of day and an MD5
 > hash of the file being split.  So I think this should be pretty secure
 > in terms of the randomness involved.

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)

Of course, one would want to ensure that no monitoring or logging
software (like the stuff I work on :-) keeps coherent snapshots around
anywhere... 

--
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)
> 
> Of course, one would want to ensure that no monitoring or logging
> software (like the stuff I work on :-) keeps coherent snapshots around
> anywhere... 
> 

Jim McCoy and I have been talking about this; the underylying question
is "how many bits of entropy are in a ps"?

Time of day, for instance, is very low entropy. The results of 'ps'
vary wildly in their entropy depending on the system and whether your
opponent has access to it or could make reasonable guesses about parts
of it.

ps is better than load average, because it always has an affect on the
system when run; load average is an *average* and is rather slow to
change. Still, we have argued over many a cup of coffee whether there's 
128 bits of entropy in ps. I think the answer is yes, or real close, for 
a system with lot of users, but not if things are slow or you don't
have many users. Of course, the more rapidly the opponent takes snapshots,
the more she perturbs the ps...

My point in all this, is that if your opponent knows the components you're
doing an MD5 of to get your random bits, and these components are low
entropy with respect to that attacker (she is on the same system and 
can monitor roughly the same statistics that you can) then this opponent
could search through the space of reasonable pertubations in the 'ps'
listing between snapshots, could extrapolate between snapshots of the
load average, etc. And feed them to MD5 herself. If you are running a
stock single user configuration, it wouldn't even be necessary for the 
opponent to be on the same system.

If there is something or somethings on any Unix system with sufficient 
entropy that can be reliably polled and fed to MD5 I'd love to know it.
(This strikes me also as something that is not going to be real portable...
I have visions of #ifdefs dancing in my head)

Some people think this is a little paranoid on my part. Ok, maybe,
but I want a lockable /dev/rand.

-- 
----------------                                             /\ 
Douglas Barnes            cman@illuminati.io.com            /  \ 
Chief Wizard         (512) 447-8950 (d), 447-7866 (v)      / () \
Illuminati Online          metaverse.io.com 7777          /______\

>One possible application is to split up your PGP secret key file this
>way and distribute the pieces to trusted friends such that several of
>them have to cooperate to recover your key.  Then if you accidentally lose
>your key you can get the pieces back from your friends.

I don't need to worry much about losing my secret key.  I can keep as
many backup copies as I like, in as many different places as I like --
all securely encrypted with my passphrase.

The application for secret sharing would be to allow some subset of
trusted people to regenerate your secret key *without your
assistance*. I could see several situations in which a voluntary
scheme like this could be useful, the main one being if you were to
die unexpectedly.

Phil