[rc5] keyspace flaw

Al Sutton al at alsutton.com
Thu May 29 12:16:16 EDT 1997

I think that the random search as opposed to a sequential search has a
lot of merrits, I know that each key has an equal likleyhood of being
the correct key, but there is the possibility of another cracking effort
working just ahead of us in the keyspace (as Benedikt suggests).

I have done some simple calculations and I have estimated that if
represented each block as a binary digit (1=searched, 0=notsearched) it
would take about 32MB of storage space to store all of the data relevant
to the keys, which is well within possibilies.

I would back the idea of developing servers which use the random search
method, but I can understand that even though its' a good idea, the
implementation may take some time.


Benedikt Eric Heinen wrote:
> > >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)?
> > No one else that we know of are actively working on RC5-56 other than us.
> > Note that the DES contests are different from this effort..
> OK, let me add to the case:
>   a) we *assume* there is no other effort running - which isn't sure
>      though. So, there *could* be others - Even though, I have to admit,
>      that if there is another effort, which we haven't heard about, than
>      this effort is most likely slower - since those people couldn't have
>      'recruited' CPU cycles without spreading the word of their effort...
>   b) I'd assume, that at least, the *WILL* be other competing efforts
>      sooner or later, and if we still supply keys sequentially, it'll be
>      easy for others to see, which keys they can skip, by just marking
>      the lowest 1.5% of the possible keys as checked (without spending
>      any CPU cycles on verifying that -- and bovine has already spent
>      quite a few cycles).
>      Even worse, a new effort could just add a little up to what we
>      have at the moment at a very low chance that they skipped the
>      real key and stay before us, so we'd only start checking keys
>      the other efforts did, i.e. if another effort would be starting
>      now at a computing speed similar to the bovine effort, it would
>      be a good move for them, not to check the lowest 1.5% of all keys
>      (we already did that for them), and even worse, start of by leaving
>      the lowest 4% of the possible keys out - which would leave us a
>      chance of finding the key in the currently 2.5% in between, but
>      would later leave us back at a 'safe' distance between our efforts
>      (by the time we have examined the low 4% of the keys, they'd be at
>      the 6.5% mark - and we'd just be following...
> If we start using random block distribution now, that'd mean any possible
> competing party cannot gain from what we do (unless they have access to
> the log on bovine).
> so much for my $0.02...
>   Benedikt
> signoff
>           Hiroshima '45           Chernobyl '86           Windows '95
> ----
> To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.

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

More information about the rc5 mailing list