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-----
participants (4)
-
Bill Stewart -
Christian Wettergren -
Jiri Baum -
Jiri Baum