Re: Exchange random numbers (was: Re: netscape's response)
In article <199509211852.LAA22259@Csli.Stanford.EDU> you write:
| 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)
People seem to think this kind of thing is obviously safe. I'm not yet convinced. By xoring in a quantity *chosen by your adversary*, you're essentially allowing related-key attacks on your stream cipher. (Your PRNG is just a stream cipher, keyed with my_seed.) Noone knows how secure most ciphers are against related-key attacks: related-key attacks are known to be very powerful (often more powerful than any other type); but very little research on this topic is available. You're treading on unknown ground. There's the also a small error in your specific algorithm. Let n = stop_bit - start_bit; presumably n is much less than the length of your seed. Then a brute-force search over n bits will recover n bits of the seed -- this is a much faster cryptanalysis than a brute force over all bits of the seed. This can probably be fixed by something like MD5(select_bits(MD5(my_seed))) -> remote, but the related-key uncertainties still remain.
| > 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) | > | | People seem to think this kind of thing is obviously safe. I'm not yet | convinced. Well, I'm not either, actually. But I think this might be better than the current state of affairs, where every bit of your seed is almost guessable. And it might also be an intermediate solution until there is a good random seed hardware generator in every computer. | By xoring in a quantity *chosen by your adversary*, you're essentially | allowing related-key attacks on your stream cipher. (Your PRNG is just | a stream cipher, keyed with my_seed.) I think you mustn't allow the any external partner to "contribute" at a known and/or chosen offset into the buffer. You mustn't either accept "too much" contribution. | Noone knows how secure most ciphers are against related-key attacks: | related-key attacks are known to be very powerful (often more powerful | than any other type); but very little research on this topic is available. | You're treading on unknown ground. Yes. But I wonder whether this isn't really about the battle between "the pragmatists" vs "the purists" point of view wrt security? I see so many very unsophisticated attacks out there that a related-key attack, although possible and powerful, still is rather unlikely. Could you quantify how powerful a related-key attack is, compared to some other kind of attack? I don't know anything about this kind of attack, do you have any references? | There's the also a small error in your specific algorithm. Let | n = stop_bit - start_bit; | presumably n is much less than the length of your seed. Then a brute-force | search over n bits will recover n bits of the seed -- this is a much faster | cryptanalysis than a brute force over all bits of the seed. This can | probably be fixed by something like | MD5(select_bits(MD5(my_seed))) -> remote, | but the related-key uncertainties still remain. Ok, noted. Maybe I should try to write down this "idea" for a proper review? Hmmm. /Christian
| > 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)
So here's another attack on this scheme which I noticed today. I'll assume you're using the Netscape/RSAREF PRNG: prng() { increment(my_seed); return(MD5(my_seed)); } Then an attacker can send you ``1'' as contribution. This will xor ``1 << contrib_area'' into your seed. With probability 1/2, this will be the same as subtracting ``1 << contrib_area'' from your seed -- and in this case, your PRNG will repeat after ``1 << contrib_area'' more outputs. This is much worse than the expected 1 << 128 cycle length. So this is an example of why it's dangerous to xor in values *chosen by your adversary* to your seed.
Could you quantify how powerful a related-key attack is, compared to some other kind of attack? I don't know anything about this kind of attack, do you have any references?
I don't know about any work on related-key attacks on stream ciphers. For block ciphers, related-key attacks are much stronger than other attacks. (e.g. DES can be broken with ~ 2^28 related key queries and about ~ 2^28 off-line computation steps) Here's some references on related key attacks on block ciphers. If anyone can find any other work in this area, let me know! @inproceedings{subkeys-important, author = {Edna K. Grossman and Bryant Tuckerman}, title = {Analysis of a Weakened {Feistel}-like Cipher}, booktitle = {1978 International Conference on Communications}, pages = {46.3.1--46.3.5}, publisher = {Alger Press Limited}, year = {1978}, annote = {Feistel ciphers with identical subkeys in each round are very weak} } @article{related-keys-1, author = {Robert Winternitz and Martin Hellman}, title = {Chosen-key Attacks on a Block Cipher}, journal = {Cryptologia}, year = {1987}, volume = {{XI}}, number = {1}, month = {January}, pages = {16--20} } @inproceedings{related-keys-2, author = {Eli Biham}, title = {New Types of Cryptanalytic Attacks Using Related Keys}, booktitle = {Advances in Cryptology: {EUROCRYPT} '93}, pages = {398--409}, publisher = {Springer-Verlag}, year = {1994} }
participants (2)
-
Christian Wettergren -
David_A Wagner