[RC5] First impressions

Bruce Ford b.ford at qut.edu.au
Wed Mar 4 10:23:44 EST 1998

> Date: Tue, 03 Mar 1998 10:42:58 -0500
> From: Mike Learn <learnm at nationwide.com>
> Subject: Re: [RC5] First impressions
> I came upon an interesting thought today.  I agree that the order in which  the
> blocks are handed out should not matter.  However, it could be information that
> could be used to a competitor's advantage.
> Were I to embark upon my own key space brute force search for DESII, I would have
> started at the top and gone down.  This would allow me to crunch more untouched
> blocks.  If d.net were handing out blocks randomly, however, I would have a larger
> chance of testing blocks that had already been checked and rejected.
> I guess what I am trying to say is that my chances would be better if I knew the
> order that d.net was checking.  It could be put to my advantage.  A couple days
> before the end of the contest, I could pretty much say where the key wasn't (even
> without crunching a single number myself!)

DES II-1 was linear because basically we were the only group 
attempting the challenge.  DESChall started with us and split off 
about half way through but did not get alot of support.

It was interesting to be able to tell how much keyspace had been 
handed out by looking at the key blocks you were receiving.  It was 
also possible to estimate outstanding blocks (about 35%) by comparing 
keyspace handed out with completed blocks from the stats. 

For RC5-64, blocks within a subspace (there are 256, 56 bit 
subspaces) are handed out in a random order.  This is historical, 
there being 3 different groups during RC5-56, and was done to avoid 
the very scenario you propose.

It is too early to tell which order the subspaces are currently being 
processed. We started at 0x64 but moved to 0x66 when the combined 
RC5/DES clients were released to prevent possible corruption of the 
85% complete 0x64 subspace by the new clients. Clients generating 
random blocks do so in the next subspace, 0x67 at present.

What happens during DES II-2 is anyones guess.  The stupidity of the
DES II contests is that we are just as likely to find the key in the
first 9% as in the last 9%.  Really it says little about the average
time to brute force DES (to a public/media which does not want to do 
maths) but how lucky or otherwise we were.  I know; it is RSA Labs 
money, they can make whatever rules they like.

So if you see DCTI starting at the bottom on DES II-2 start at the 
top.  With alot of luck you will find the key before we do.

Bruce Ford                                      b.ford at qut.edu.au
Systems Programmer
Teaching and Learning Support Services          Ph: +61 7 3864 3383
Queensland University of Technology
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list