[RC5] Do not forget about the cheaters :)

Elektron elektron_rc5 at yahoo.ca
Thu Jan 8 03:24:23 EST 2004


On 8 Jan, 2004, at 07:21, Richard Farmbrough wrote:

> I suggested something like this to Bovine in an email  Tue 18/07/2000
> 12:03.
> Slightly more succinct than the Stanford paper IMHO :-)
> (Clearly it doesn't cvoer quite as much ground.)
>
> ---------
> Jeff,
> 	One slight problem with a secondary plaintext for inline testing is 
> choice
> of a single solution in a block would still allow a stats inflator to 
> work
> at (on average) double speed, discarding any keys after the inline 
> block.
>  Two solutions are provision of multiple plaintexts (requiring 
> 1-1/(2^n) of
> the work to be done), and statistically providing plaintexts which may 
> or
> may not be in the text .  Combining the two approaches would provide 
> rapid
> identification of bogus clients.

This is untrue. We pick a random key x and decrypt the ciphertext to y. 
We send out the first 32 bits of y as a 'challenge', and require the 
client to return all keys X={x0,x1,...} which decrypt the ciphertext to 
y (as far as it knows, since it only knows about 32 bits). If x is one 
of those keys, the block can be considered valid, otherwise it isn't 
valid.

If we have three 'challenges', then you test more blocks than you get 
into stats (0.60714 keys actually tested, 0.48196 blocks into stats).

It's statistically possible to beat this if you code the client to know 
how keys are distributed, though (I haven't coded the simulator for 
this yet). But then, some blocks won't get into stats, and such clients 
will be found out.

> E.G.
>
> Plaintext (Public)  Position (private)
>
> p1 		P1	
> p2		Does not exist
> p3		P2
> p4		Does not exist.
>
> I can see no way of a client providing the private information back to 
> the
> server without either completing the block, or substantially 
> completing and
> guessing the remaining keys do not exist.
>
> Even a single "maybe" plaintext is very powerful over the course of a 
> small
> number of blocks.

This sounds promising, if we make for the allowance that the client may 
return a 'false' result.

If the client finds a solution for every challenge, though, it knows it 
can return the block without checking the rest of the keys.

We still have the problem of people sending falsified results under 
different emails (e.g. a new fake email per block). Some of them will 
get through (but, of course, there's always third-party verification).

- Purr



More information about the rc5 mailing list