[rc5] Some thoughts on finding the key
gindrup at okway.okstate.edu
Mon Oct 27 17:44:22 EST 1997
Four characters is 32 bits. Thus there are (probably) 2^(56-32) =
2^24 ~= 16Mkeys that generate the target first four bytes for RC5-56
and 256 times as many that generate the target first four bytes in
RC5-64. Probabilistically, only one key generates the first eight
target bytes (until after RC5-64) for either effort.
This is probabilistic because it is known that RC5 does not form a
group under composition and therefore only has "evenly distributed"
statistics for a subset of its keyspace (which may be large or small
-- an unknown issue).
Since 1 in 2^32 keys probably generates a match on the first four
characters, there were probably 39 (4-byte) probable solutions on the
day that the key was found (7Mkey/s * 86400s/day * 2^-32 probable
sol'ns/key). Thus the number of (8-byte) probably solutions was
probably less than 1 for the entire effort.
I know that Nugget indicated that at least one 8-byte incorrect
probable solution was returned, but the uneven nature of RC5
properties and the smallness of the sample space (one out of all
possible plaintexts) speaks to the likelihood of having an unusual
I really do wonder what is the false positive rate for each kind of
-- Eric Gindrup ! gindrup at Okway.okstate.edu
______________________________ Reply Separator _________________________________
Subject: Re: [rc5] Some thoughts on finding the key
Author: <rc5 at llamas.net > at SMTP
Date: 1997/10/26 19:43
On Sun, 26 Oct 1997, Joseph Fisk wrote:
> > At 04:09 PM 10/23/97 -0400, you wrote:
> > >On Wed, 22 Oct 1997, David McNett wrote:
> > >> 19-Oct-1997 13:25 - Key 0x0x532B744CC20999 is submitted to the
> > >> net servers as a possible solution.
> > >> 20-Oct-1997 13:00 - I notice the success report in the logfile and track
> > >> down Tim Charron to test it fully.
> > >I notice that there is a full day's delay here. Why not have it mail you a
> > >message "We Got Da Key!" when a possible success is logged?
> Was more than one possible solution reported?
> What would be a case where a key could "possibly" be the right one, but
More then one possible solution was reported (I recall somebody mentioned
that), and I think it's theoreticly possible that there is more then one key
that would decrypt the first four (and eight) characters correctly.
However, for these handfull of keys (there certiantly shouldn't have been
more then a few), we can afford to raise false hopes for a bit or two.
Anyway, the master keyserver could check the possibles itself, and only send
out different mail (and log it to different files) depending on if it
compares out the whole "The unknown message is: " string.
-=- James Mastros
> mdmbkr at chillin.org
Current Bovine Rate: ~5894.11 mkeys/sec
If Keys were dollars, we could pay off the U.S.
National Debt in 14.70 minutes.
-=- http://rc5stats.distributed.net/statbar.html (Tue Oct 21 1997)
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.
More information about the rc5