From: Jiri Baum <jirib@sweeney.cs.monash.edu.au>
Date: Thu, 21 Sep 95 02:59:56 PDT
To: cwe@Csli.Stanford.EDU (Christian Wettergren)
Subject: Exchange random numbers (was: Re: netscape's response)
In-Reply-To: <199509210153.SAA25449@Csli.Stanford.EDU>
Message-ID: <199509210958.TAA10764@sweeney.cs.monash.edu.au>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

Hello Bill Stewart <stewarts@ix.netcom.com>
  and cypherpunks@toad.com, "Jeff Weinstein" <jsw@netscape.com>
  and Christian Wettergren <cwe@Csli.Stanford.EDU>

Christian Wettergren <cwe@Csli.Stanford.EDU> writes:
> Christian (that's me) writes:
> | One wild idea that I just got was to have servers and clients exchange
> | random numbers (not seeds of course), in a kind of chaining way. Since
...
> Bill Stewart answered:
> | Be _very_ careful with this approach - it's the kind of thing that a
> | rogue server or client might abuse to find out randomness or other state
...
> Of course you have to be very careful, as you say. Did you see my
> problem-section in the original letter? I included it above.
... [the referenced section elided by jirib] ...

If I only ever give out a hash of my seed, and only ever *add* any received
info to my seed (and stir it in well), how can anyone find out anything?
(Apart from hash weaknesses.)


The only thing that remains is that I cannot really count on a stranger
to actually give me something truly random. In fact, since at least
one other person knows it, I shouldn't count any entropy from it at all.

However, if I get e bits from each of n servers, and k of them are rogue,
then I have e*(n-k) bits, ie e*n*(1-k/n). With a suitably conservative
estimate of k/n, this should be acceptable.

In any case, accepting donations of entropy cannot possibly reduce the
amount of entropy I have, can it?


As well as the normal servers, there might be dedicated randomness servers
whose sole purpose is to give you a random number. For a toy example, see

  http://www.cs.monash.edu.au/cgi-bin/cgiwrap/~jirib/random?ToyRandValue

(where ToyRandValue should be replaced by whatever your random value is).

Again, one would connect to several and stir the results together,
confident in the statistics that say at least one is genuine.

Of course, we then have a chicken-and-egg problem of getting secure
connection to the randomness servers, but we have that anyway. Perhaps each
client could keep a pool of randomness, and whenever it runs low connect
to the randomness servers to re-fill, initially using "type random text".

...
> and that you should only give out approximately the same amount of 
> randomness to the neighbour, as you point out below.
...

I'm not sure I follow this one. Why?

If the neighbour is willing to trust me for more, and cannot possibly
deduce my seed from the numbers ('cause it's a strong 1-way hash),
the only thing it costs me is CPU time - it'd cost me more to keep
track of who asked for how much when.

...
> My approach solves part of the problem of "the observable local
> environment" problem. 
...

Then again, you can always ping. With a well-chosen target, you get
10 bits raw from the first packet... Perhaps about 7 or 8 of actual
usable entropy (and before you flame me, ping melb.dialix.oz.au).


Part of this is that once the sources of randomness are sufficiently
diverse, it's just easier for an attacker to modify your s/w.
Especially if you never throw out your seed, so that all your interactions
since the beginning are unfathomably stirred into your current key.

(Ie I might not mind if I have only 1 bit of entropy per transaction
provided that the total entropy is 128 bits. Provided I never reveal
my seed, of course. This would mean that the value risked on any
particular 128 bits are 128 of my transactions, not just one, but for
most people each of those transactions will involve the same CC number
so it makes no difference anyway.)


Hope that makes sense...

Jiri
- --
If you want an answer, please mail to <jirib@cs.monash.edu.au>.
On sweeney, I may delete without reading!
PGP 463A14D5 (but it's at home so it'll take a day or two)
PGP EF0607F9 (but it's at uni so don't rely on it too much)

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2i

iQCVAwUBMGE3JixV6mvvBgf5AQFcWwP/UMbLaF2IM7y8HAjVUOCRoE4xgp+XkAj9
zQAnd0XnW5nbwqoXJe/WiT/4QQ3Rx/2tV8OhskS1dhy/7WEZ1WtTsEu4Of3YUDJp
rOYf5omToxLVXWNUQrCYUtGUjJo2UdUg2N8NfIR+vXrsZG7HPhfXsrRD9C0W1HJw
yIfcZUzz+s4=
=KJsK
-----END PGP SIGNATURE-----