[rc5] keyspace flaw

Henry W Miller mill0440 at gold.tc.umn.edu
Wed Jun 4 07:42:00 EDT 1997



On Tue, 3 Jun 1997, Sean Reifschneider wrote:

> On Wed, Jun 04, 1997 at 02:08:47AM +0100, Chris Carlin wrote:
> >Henry W Miller wrote:
> >> aren't searched, we should assume that unreturned blocks are partially
> >> searched.  Any server devoted to recycling keys *SHOULD* report half
> >
> >If we go all the way through the keyspace and don't find they magic key,
> >then when we begin recycling pre-distributed keyblocks, maybe we should
> >modify the clients to work them backwards to increase the chance that
> 
> Am I the only one who finds this discussion rather weird?  The only thing
> we *KNOW* about any key blocks that haven't been returned is that we don't
> know if the key exists anywhere in there.  We can't assume that half the
> block was searched because that would be an invalid assumption.

I'm trying to extrapulate an average.  I agree we know nothing about 
these blocks, othe then the ones that I have personally stoped at the end 
of the block.  While this average isn't numerically correct it is close 
enough.

> Searching the key-blocks wouldn't help shorten the time any.  The network
> is going through around 400 million keys per second.  On average, even
> if the key were EXACTLY at the end of a block of 288M keys, we'd be saving
> less than a second.  Since we don't know how much or even IF the keyblock was
> searched at all.  The key just as well could be at the beginning or the
> key-block.

But the key could be in any block.  This discussion is if the block is in 
one of the un searched blocks vs one so the un-returned blocks.  The 
unsearched blocks all have equal odds of having the keys, but the 
un-returned blocks don't since we know for a fact that some of them are 
partially searched.  Even if we assume that all un-returned blocks are 
unsearched except for the two that I  stoped after a full search, the 
un-returned blcoks (since we don't know which one I stoped) have a lower 
odds of having the key.    
----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.



More information about the rc5 mailing list