[rc5] Suggestion for protocol

Fedor Kouranov ted99 at ibm.net
Mon Jun 23 13:54:24 EDT 1997


On 06/22/97 Tristan Horn <tristan at camel.ethereal.net> said:

>Can you elaborate on that?

OK, most of the work was already done for me ;-)

I do not happen to know what exactly the clients check. I recall that rc5
operates on 32 bit blocks. So, it could be either 'The ' or 'The unkn'. I
assume that the result of decrypting with a wrong rc5 key leads to totally
random results. In the first case we will have a 1/2^32 probability of
matching. That is, one in 16 blocks (too often?). That is, 16 million
probable solutions. In the second case we will have a 1/2^64 probability,
or 1/256 in the whole keyspace. I heard that you usually get a 'correct'
solution once in a while. Hmmmm..... What is it in reality, anyway?

Anyway, we already have a few blocks that have passed pre-checking by the
clients, but failed the final check. They are the 'surprise' solutions.
Encrypting with a different key is a different 'surprise'. How can the
enemy spot it?

1) The block is 'behind' the previous one = in checked keyspace = already
checked. Check it and return the result. Solution: (at least some) random
distribution.

2) The block appears alsewhere, but not 'right after' (close to) the
previous one. This will trigger on random distribution by proxies if the
master server is down. Well, the bad guy has to save his butt... Random
distribution will help again.

3) The cyphertext is different. Easy.

Anything else?

Encrypting something in the block will give big processor overhead, and
letting the proxy ask random questions will place enormous demands on
memory. How about this: say, client checks the first 32 bits only. Then, it
will simply have to add all decrypted values together (1 extra op/key) and
submit the sum along with the report (then the sum is logged). This will
*guarantee* that the block was checked (because the sum cannot be
determined without cryptanalysis... and the first guy to crack rc5 will get
$100.000 from RSA). Certainly, confirming it will require rechecking the
block.

 /** Christ Is Risen ! *** __+__ ******  Fedor "Ted" Kouranov  *****/
 /* Xristos Voskrese ! **   \|    ** ted99 at ibm.net * fedor at bu.edu **/
 /** Xristos Anesti ! ****   |\  ** http://enz.siobc.ras.ru/~fedor */

----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.



More information about the rc5 mailing list