Re: netscape's response

On Sep 20, 12:29am, Christian Wettergren wrote:
>> Subject: Re: netscape's response
>> 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
>> most viewers connect to a number of servers, and all servers are
>> connected to by many clients, they would mix "randomness sources" with
>> each other, making it impossible to observe the local environment
>> only. And the random values would of course be encrypted under the
>> session key, making it impossible to "watch the wire".

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
information about the clients or servers connecting to it.
At minimum, only give out some of your randomness, XORed with some
arbitrary value to scramble the range and then hashed before sending,
so that the recipient can't find out the values you're using.

One valuable technique is to continually accumulate any randomness available,
rather than just going for what's available right when you need it.
However, one source of right-when-you-need-it randomness to contribute
to session keys is hashing the plaintext, or at least the first chunk of it;
if you use this carefully (e.g. by throwing it in with the rest of your
hash input), it should provide input unavailable to the attacker.

Also, while network boards and sound cards can provide useful randomness,
you can't depend on their existence, at least in the PC world; most home users
probably connect over modems and don't have LANs.  So any software that
would like to use these needs to include methods of detecting their existence
before trying to get data from them.  (Suns obviously all have network
interfaces,
and Sparcstations have /dev/audio, but not all Unix boxes are similarly
equipped.)
#---
# Bill Stewart, Freelance Information Architect, stewarts@ix.netcom.com
# Phone +1-510-247-0664 Pager/Voicemail 1-408-787-1281
#---

Christian (that's me) writes:
| I think it is important to bring together factors of the user _and_
| the environment, preferrable an environment that reaches as far from
| the local site as possible. This makes "jamming" of the random seed
| selection process harder. 
| 
| The other problem in gathering random bits for a seed is that most
| bits are visible by someone else close enough within your environment.
| Interarrival times of packets are fine, but anyone can observe them
| with quite a good accuracy. How do you escape the "local environment
| problem"? 
| 
|                               . - .
| 
| 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
| most viewers connect to a number of servers, and all servers are
| connected to by many clients, they would mix "randomness sources" with
| each other, making it impossible to observe the local environment
| only. And the random values would of course be encrypted under the
| session key, making it impossible to "watch the wire".
| 
| Problems:
| * watch out for "multiply by zero" attacks by a rogue server/client.
| * watch out for "almost singular values" in the same way.
| * only let one source contribute a certain amount of randomness, like
|   (key length)/(aver # of peers).
| * never reveal your current seed, only a non-trivially derived random 
|   value from it. (of course)
| * make sure your initial seed is good enough, or the whole thing is
|   broken.
| * perhaps save part of the previous session state into a protected
|   file, to be able to keep up the quality of the initial seed.
| 
| I think I like it, perhaps not from a practical point of view as much
| as the 'non-attackability' of it. Its quite cypher-a. 

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
| information about the clients or servers connecting to it.

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. Since
then I have realized that the 

   | * only let one source contribute a certain amount of randomness, like
   |   (key length)/(aver # of peers).

really should be

   | * only let one source contribute a certain amount of randomness, like
   |   (large entropy buffer)/(aver # of peers).

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

| At minimum, only give out some of your randomness, XORed with some
| arbitrary value to scramble the range and then hashed before sending,
| so that the recipient can't find out the values you're using.

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

Jeff's reply to this suggestion might be somewhat dangerous, if
the exchanged 'randomness bits' are the challenge/responses in the
exchange. (Based on his remark of not needing to change protocol.)
You would arguably not want to have the loop

         RNG --> "unguessable chall/resp" ---+
          /\                                 |
           +---------------------------------+

I would say that the only acceptable solution would be to have


(viewer)consumer <-------------------->consumer (srv)
          /\                             /\
           |                              |
   --->  RNG1 <---------------------->  RNG2 <----- RNGn
          /\                             /\
           |                              |
         RNGx                           RNGy

separating the "building up" of randomness from the 
consuming phase of that built up randomness, the actual
part which has to be totally unpredicate.

/Christian

-----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-----

| > 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.)

Giving out contribution: 
     MD5(select_bits(my_seed, start_bit, stop_bit)) -> remote
Taking in contribution : 
     my_seed = my_seed XOR 
     ((select_low_bits(remote_contrib, contrib_width) << contrib_area)

You also need to keep track of who has contributed what, and how much.
This might become a problem if you don't have a safe authentification
mechanism, like baseing the tracking on the IP-numbers etc.

But I don't believe this is a real problem, since you always
contribute 'entropy', not exact values. You need to know the exact
state of the random generator to be able to predict how your
contribution will affect the generator.

The boot-strap stage is actually the big problem still. But if the
initial stages are 'random enough' to withstand a total crack, I guess
the randomness gathered will increase rapidly, and increase the
safety a lot.

| 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?

This isn't a problem as I see it, he'll only know what bits he
flipped, not the actual state.

I guess someone could mount an attack on the remote_contrib, finding
the part of my_seed by bruting the remote_contrib that I submitted.
But even if that is done, you'll only know a small part of the total
seed. And the remote end can't choose which segment of my_seed that
will be revealed.

I also see a problem if an attacker is controlling the whole
environment, but this is no different from the original problem, and
a lot more unlikely.

| > 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.

Well, the reason would be that if someone bruted your contribution,
they would still have to guess the remaining part. Double safe! :-)

| ...
| > 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).

Yes, but if one assumes that the algorithm to gather the seed is
known, its quite possible for someone else to do it at the same time
as you do it, or even observe your ping packet req/reply. And how do
you determine which 'random host' to ping?

| 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.

Yes, I believe this is important too.

/Christian

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

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

Christian Wettergren <cwe@Csli.Stanford.EDU> wrote:
...
> | 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.)
> 
> Giving out contribution: 
>      MD5(select_bits(my_seed, start_bit, stop_bit)) -> remote
> Taking in contribution : 
>      my_seed = my_seed XOR 
>      ((select_low_bits(remote_contrib, contrib_width) << contrib_area)

Hmm, I use:
  taking-in:
	seed = MD5(seed,new-data)
  giving-out:
	MD5(seed)

(where every giving-out is preceded by a taking-in). Is that OK?
If not, why not and how can I improve it?

> You also need to keep track of who has contributed what, and how much.
...

Why? I guess to keep track of how much entropy I believe I have...

> This might become a problem if you don't have a safe authentification
> mechanism, like baseing the tracking on the IP-numbers etc.

That's a safe authentication mechanism? I don't think so.
But you need a secrecy mechanism, so I guess that's where you'd
add your auth.

...
> The boot-strap stage is actually the big problem still. But if the
...

The boot-strap is done only once (at install time) so it's not a big
problem to ask for lots of random text from user.

...
> | In any case, accepting donations of entropy cannot possibly reduce the
> | amount of entropy I have, can it?
> 
> This isn't a problem as I see it, he'll only know what bits he
> flipped, not the actual state.

Good, I thought so.

Sorry, have to go now, rest later...

Jiri
- --
<jirib@cs.monash.edu.au>     <jiri@melb.dialix.oz.au>     PGP 463A14D5

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

iQCVAwUBMGIpgixV6mvvBgf5AQGRggQAwEcY+5N0stTbWXfXg3zQ6FNdzv9Sckds
3xAjLbxr85jS98Sj0Nm++DwS674U8YfrNzTRg3HnOBUcS+i8UvP445jtj4UiyxU8
hyM2ZvzBWjFuj35jXF4KR5XotZyvAsAcICsssv0UQZ3JKWV+tU/pN8sZ3sgKRRWZ
ipvAFyY+rhA=
=1d8P
-----END PGP SIGNATURE-----