[rc5] keyspace flaw

Henry W Miller mill0440 at gold.tc.umn.edu
Thu May 29 07:27:53 EDT 1997

On Thu, 29 May 1997, Benedikt Eric Heinen wrote:

> > > it stands to reason that RSA selected keys that will fall at
> > > or beyond the 50% threshold of the keyspace.  has any thought
> > > been given to modify the servers to randomly select key ranges
> > > throughout the entire keyspace?
> > Actually it would stand to reason that any key would be just as unlikely
> > as any other key.  This is supposed to be a real test of rc5, and RSA
> > selecting one key over another can only reduce the security of
> > the algorithm (assuming no weak keys).
> Still, I think that this random blocks idea isn't bad. I mean, we're
> probably not the only effort to try and break the key, so as long as all
> the efforts plough through all possible combinations starting with key 0x0
> up to the maximum, that means, that only the fastest group has a chance of
> winning, since all the other efforts are checking keys that have been
> dealt with already.

Just beacuse we are doing it like that doen'st mean the others are.  In 
the end random chance favors us as much as hurts us.

> Now, can anybody round here prove, that we're the fastest of the
> competing groups? I mean, is there even a way to know which groups are
> competing (I do not refer to the email groups within our effort, but
> groups independent of bovine)?

I'm not aware of the existence of any other ones.  that doen'st mean they 
don't exist, but any potential compeating group is unlikely to have as 
much power as the umich group has got for instrance.  so I think we are 
safe to assume they don't exist.

> Selecting key blocks at random does seem somewhat reasonable, I think...

it is very reasonable in tree search and parrel processing theroy.

programing it right isn't easy though.  

I've accually suggested doing random searches, but there have always been 
more pressing concerns for the key servers.  Getting them stable was, as 
it should be, more important then random searching.

I advocate spliting the blocks into chunks, and have each server do a 
different chunk, that is rc5.best.net does 1xxxxxxx blocks while 
rc5.slackers.com does 2xxxxxxx blocks.  
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.

More information about the rc5 mailing list