[rc5] Some thoughts on finding the key

Rémi Guyomarch rguyom at mail.dotcom.fr
Sat Oct 25 13:03:02 EDT 1997


Jeff Woods wrote:
> 
> At 09:45 PM 10/23/97 -0500, you wrote:
> 
> >The client only compares the first 8 bytes of the decrypted text to
> >the known plaintext.  The algorithm encrypts/decrypts in multiples of
> >8 bytes, so there's no benefit to doing a smaller comparison.
> 
> I thought this was RC5-32/12/??, or 32-bit wordsize.   It SHOULD decrypt in
> FOUR byte chunks, no?  Or did I miss something in reading the RFC?  Of
> course, you're the expert....

Re-read the RFC (2040) :

-----------------------
6.  Description of RC5 Block Cipher

   This section describes the RC5 block cipher by explaining the steps
   required to perform an encryption of a single input block.  The
   decryption process is the reverse of these steps so it will not be
   explained.  The RC5 cipher is parameterized by a version number, V, a
   round count, R, and a word size in bits, W.  This description
   corresponds to original version of RC5 (V = 16 decimal) and covers
   any positive value for R and the values 16, 32, and 64 for W.

   The inputs to this process are the expanded key table, S, the number
   of rounds, R, the input buffer pointer, in, and the output buffer
   pointer, out.
[...]
  void RC5_Block_Encrypt (S, R, in, out)
    RC5_WORD    *S;
    int  R;
    char    *in;
    char    *out;
  {
    int  i;
    RC5_WORD    A, B;

    A  =  in[0] & 0xFF;
    A += (in[1] & 0xFF) << 8;
    A += (in[2] & 0xFF) << 16;
    A += (in[3] & 0xFF) << 24;
    B  =  in[4] & 0xFF;
    B += (in[5] & 0xFF) << 8;
    B += (in[6] & 0xFF) << 16;
    B += (in[7] & 0xFF) << 24;

    A = A + S[0];
    B = B + S[1];
    for (i = 1 ; i <= R ; i++) {
        A = A ^ B;
        A = ROTL(A, B, W) + S[2*i];
        B = B ^ A;
        B = ROTL(B, A, W) + S[(2*i)+1];
    }

    out[0] = (A >>  0) & 0xFF;
    out[1] = (A >>  8) & 0xFF;
    out[2] = (A >> 16) & 0xFF;
    out[3] = (A >> 24) & 0xFF;
    out[4] = (B >>  0) & 0xFF;
    out[5] = (B >>  8) & 0xFF;
    out[6] = (B >> 16) & 0xFF;
    out[7] = (B >> 24) & 0xFF;
    return;
  } /* End of RC5_Block_Encrypt */
-----------------------

>  I was more concerned with the algorithm to
> compare those 4 or 8 byte chunks to "The " and "The unkn"....   Compares
> are usually the SLOWEST things one can do in computing other than floating
> point emulation, and since Cyberian's clients are faster than ours, I was
> thinking of this as the most likely area for optimization.   I assume the
> coders have run a profiler on this thing to find out where most of the time
> is spent?

In the main decryption routine, there's only two compares (per key), and
the second one is executed only if the first one is true. But due to the
RC5 algorithm, we must decrypt 8 bytes at a time, and not 4 bytes.

About Cyberian beeing faster that Distributed.net, you should
double-check the client speed pages of Cyberian and D.N., you will see
that we're faster on most CPUs, and we're on pair on the others.

-- 
Rémi

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



More information about the rc5 mailing list