[rc5] Some thoughts on finding the key

Eric Gindrup 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 
     sample.
     
        I really do wonder what is the false positive rate for each kind of 
     probable key...
            -- 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 
distributed
> > >>                     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 
> wasn't?
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
     
> 
> Joseph
> 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
body.
     


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



More information about the rc5 mailing list