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