• RSS
  • Twitter
  • FaceBook

Security Forums

Log in

FAQ | Search | Usergroups | Profile | Register | RSS | Posting Guidelines | Recent Posts

Cryptanalysis Walkthrough #1 - Weakened RC5

Users browsing this topic:0 Security Fans, 0 Stealth Security Fans
Registered Security Fans: None
Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

View previous topic :: View next topic  
Author Message
mxb
Trusted SF Member
Trusted SF Member


Joined: 30 Mar 2004
Posts: 6


Offline

PostPosted: Thu Dec 23, 2004 3:12 pm    Post subject: Cryptanalysis Walkthrough #1 - Weakened RC5 Reply with quote

Introduction

For many years now I have been very interested in cryptography, and cryptanalysis in particular, and I was pleasantly surprised when I found 'A Self-Study Course in Block Cipher Cryptanalysis' by the established cryptographer Bruce Schneier. I downloaded this paper, and after brushing up on my mathematical theory decided to have a go at the first challenge - the cryptanalysis of 8-round RC5 without any rotations. This paper was written to document my experiences, and if the outcome of this is that only one person is interested enough to take cryptography seriously, it has done its job. I hope you will find this paper useful.

- Martin

Stage 1 - Learning the cipher

As this was my first attempt at some serious cryptanalysis, I wasn't too sure where I was supposed to start. The only resource I had was the original RC5 paper, and a brief one liner in Schneier's paper instructing me to perform cryptanalysis on a weakened version of eight rounds with no rotations. I thought that the best place to start was with the full RC5 and to first learn how this worked.

I printed the RC5 paper, and proceeded to read it thoroughly a few times to make sure I understood it fully. With no distractions, this took approximately a few hours. It was one of the first scientific papers that I had read, and it took some time to get used to the layout and method of writing. However I feel that to be a competent cryptographer you will have to read a large number of papers in this style, so time and effort spent at this stage would improve things later.

Stage 2 - Finding an idea

After understanding how the full RC5 worked, I re-read the paper, this time jotting down notes along the side about how the weakened version differed. While I was doing this, my first idea came to me. My idea was that as the only operation performed in the weakened version was only addition, the plaintext and ciphertext pairs should be fairly resemblant. By this I mean that changing the lower bits of a plaintext word should only affect the lower bits of the ciphertext words. I also wrote this down on the paper, and carried on reading, in case any other ideas came to me. They didn't, but I was left with one idea that I felt must be true. This stage probably took another couple of hours of slow reading and heavy thinking.

Stage 3 - Implementation in code

To check this idea I needed to implement it on the computer. Starting with the original rc5ref.c I converted the key from bytes to words. If I knew more advanced C this step would probably have been unnecessary, but I was sticking to what I knew, and decided it would be worth it. At this stage I also removed the unneeded rotations and slightly changed the format. These were done after checking a full version of RC5 using words against the test vectors given in the paper. Below is the final version of rc5word.c:

Code:
rc5-word.c

#include <stdio.h>
typedef unsigned long int WORD; /* Should be 32-bit = 4 bytes        */
#define w        32             /* word size in bits                 */
#define r        8              /* number of rounds                  */
#define b        16             /* number of bytes in key            */
#define c         4             /* number  words in key = ceil(8*b/w)*/
#define t        18             /* size of table S = 2*(r+1) words   */
WORD S[t];                      /* expanded key table                */
WORD P = 0xb7e15163, Q = 0x9e3779b9;  /* magic constants             */

void RC5_ENCRYPT(WORD *pt, WORD *ct) { /* 2 WORD input pt/output ct  */
 
        WORD i, A=pt[0]+S[0], B=pt[1]+S[1];
 
        for (i=1; i<=r; i++) {
                A = (A^B)+S[2*i];
                B = (B^A)+S[2*i+1];
        }
 
        ct[0] = A; ct[1] = B;
}

void RC5_DECRYPT(WORD *ct, WORD *pt) { /* 2 WORD input ct/output pt  */
 
        WORD i, B=ct[1], A=ct[0];
 
        for (i=r; i>0; i--) {
                B = (B-S[2*i+1])^A;
                A = (A-S[2*i])^B;
        }
 
        pt[1] = B-S[1]; pt[0] = A-S[0];
}

void RC5_SETUP(WORD *K[4]) { /* secret input key K[0...b-1]    */
 
        WORD i, j, k, u=w/8, A, B, L[c];
 
        /* NB: L[] == K[] in this instance */
 
        for (S[0]=P,i=1; i<t; i++) {
                S[i] = S[i-1]+Q;
        }

        L[0]=K[0];
        L[1]=K[1];
        L[2]=K[2];
        L[3]=K[3];

        for (A=B=i=j=k=0; k<3*t; k++,i=(i+1)%t,j=(j+1)%c) { /* 3*t times */
                A = S[i] = S[i]+(A+B);
                B = L[j] = L[j]+(A+B);
        }
}

void main() {

        WORD pt[2] = {0,0};
        WORD ct[2] = {0,0};
        WORD key[c] = {0,0,0,0};
        int iw,pw;


        /* check WORD size */
        if (sizeof(WORD)!=4) {
                printf("RC5 error: WORD has %d bytes.\n",sizeof(WORD));
                return(0);
        }

        RC5_SETUP(&key);
        RC5_ENCRYPT(pt,ct);
        printf("%.8lX%.8lX%.8lX%.8lX,",key[0],key[1],key[2],key[3]);
        printf("%.8lX%.8lX\n",ct[0],ct[1]);
}


After making some minor changes to the code, rc5-bitsweep.c was born. This program swept though the keyspace, setting the entire key to zero, except one single bit, whose position swept through the key from right to left.

Code:
rc5-bitsweep.c

#include <stdio.h>
typedef unsigned long int WORD; /* Should be 32-bit = 4 bytes        */
#define w        32             /* word size in bits                 */
#define r        8              /* number of rounds                  */
#define b        16             /* number of bytes in key            */
#define c         4             /* number  words in key = ceil(8*b/w)*/
#define t        18             /* size of table S = 2*(r+1) words   */
WORD S[t];                      /* expanded key table                */
WORD P = 0xb7e15163, Q = 0x9e3779b9;  /* magic constants             */

void RC5_ENCRYPT(WORD *pt, WORD *ct) { /* 2 WORD input pt/output ct  */

        WORD i, A=pt[0]+S[0], B=pt[1]+S[1];

        for (i=1; i<=r; i++) {
                A = (A^B)+S[2*i];
                B = (B^A)+S[2*i+1];
        }

        ct[0] = A; ct[1] = B;
}

void RC5_DECRYPT(WORD *ct, WORD *pt) { /* 2 WORD input ct/output pt  */

        WORD i, B=ct[1], A=ct[0];

        for (i=r; i>0; i--) {
                B = (B-S[2*i+1])^A;
                A = (A-S[2*i])^B;
        }

        pt[1] = B-S[1]; pt[0] = A-S[0];
}

void RC5_SETUP(WORD *K[4]) { /* secret input key K[0...b-1]    */

        WORD i, j, k, u=w/8, A, B, L[c];

        /* NB: L[] == K[] in this instance */

        for (S[0]=P,i=1; i<t; i++) {
                S[i] = S[i-1]+Q;
        }

        L[0]=K[0];
        L[1]=K[1];
        L[2]=K[2];
        L[3]=K[3];

        for (A=B=i=j=k=0; k<3*t; k++,i=(i+1)%t,j=(j+1)%c) { /* 3*t times */
                A = S[i] = S[i]+(A+B);
                B = L[j] = L[j]+(A+B);
        }
}

void main() {

        WORD pt[2] = {0,0};
        WORD ct[2] = {0,0};
        WORD key[c] = {0,0,0,0};
        int iw,pw;


        /* check WORD size */
        if (sizeof(WORD)!=4) {
                printf("RC5 error: WORD has %d bytes.\n",sizeof(WORD));
                return(0);
        }

   key[0]=key[1]=key[2]=key[3]=0;
        RC5_SETUP(&key);
        RC5_ENCRYPT(pt,ct);
        printf("%.8lX%.8lX%.8lX%.8lX,",key[0],key[1],key[2],key[3]);
        printf("%.8lX%.8lX\n",ct[0],ct[1]);

        for (pw=3; pw>-1; pw--) {
                for (iw=0; iw<32; iw++) {
                        key[0]=key[1]=key[2]=key[3]=0;
                        key[pw]=(1<<iw);
                        RC5_SETUP(&key);
                        RC5_ENCRYPT(pt,ct);
                        printf("%.8lX%.8lX%.8lX%.8lX,",key[0],key[1],key[2],key[3]);
                        printf("%.8lX%.8lX\n",ct[0],ct[1]);
                }
        }
}


If my original idea was correct, then when the lower bits of words one and three were modified, only the lower bits of the ciphertext words should change. Only words one and three would change them as both words zero and one, and two and three are taken as pairs. The results were as follows:

Quote:
rc5-bitsweep.c results:

00000000000000000000000000000000,FB6286344868FD57
00000000000000000000000000000001,160EBEBC61C38363
00000000000000000000000000000002,6C8246C81A1EB773
00000000000000000000000000000004,A5B198246521EA6F
00000000000000000000000000000008,9AC017840EEF96F7
00000000000000000000000000000010,B298FBD49DB32717
00000000000000000000000000000020,D66955F4398EDB17
00000000000000000000000000000040,D12E61B44C809257
00000000000000000000000000000080,08767234445EDC57
00000000000000000000000000000100,8CA9FE348ADB0357
00000000000000000000000000000200,11284634D222ED57
00000000000000000000000000000400,7C0FA63483D31D57
00000000000000000000000000000800,3AA2263453CDAD57
00000000000000000000000000001000,19644634FC4D5D57
00000000000000000000000000002000,DBDB463404FEBD57
00000000000000000000000000004000,3C930634BC41FD57
00000000000000000000000000008000,00F186349D4EFD57
00000000000000000000000000010000,95848634FB82FD57
00000000000000000000000000020000,443686348BD0FD57
00000000000000000000000000040000,C60286349640FD57
00000000000000000000000000080000,9282863452B8FD57
00000000000000000000000000100000,D7428634D408FD57
00000000000000000000000000200000,3B2286346828FD57
00000000000000000000000000400000,68628634B268FD57
00000000000000000000000000800000,CA628634D068FD57
00000000000000000000000001000000,1D628634A868FD57
00000000000000000000000002000000,4F6286341C68FD57
00000000000000000000000004000000,E36286349868FD57
00000000000000000000000008000000,9B628634D868FD57
00000000000000000000000010000000,9B6286340868FD57
00000000000000000000000020000000,FB628634C868FD57
00000000000000000000000040000000,FB628634C868FD57
00000000000000000000000080000000,FB6286344868FD57
00000000000000000000000100000000,99FC5B48DB4C4856
00000000000000000000000200000000,F7DD4CC8F7C66325
00000000000000000000000400000000,AE198B749885A083
00000000000000000000000800000000,E5DA4004055FBDDF
00000000000000000000001000000000,D9BAF2B4700EA307
00000000000000000000002000000000,39DDBDB40F6A5DF7
00000000000000000000004000000000,4CA4B9B44BA6B597
00000000000000000000008000000000,593A0D349BCBA2D7
00000000000000000000010000000000,4304D63488FB9057
00000000000000000000020000000000,F8E63A34EBDDF757
00000000000000000000040000000000,5699F634D98CD157
00000000000000000000080000000000,B241C634F339C557
00000000000000000000100000000000,5453C634D2FAED57
00000000000000000000200000000000,7D3846344EE49D57
00000000000000000000400000000000,4ABC86343A213D57
00000000000000000000800000000000,68418634ED027D57
00000000000000000001000000000000,14348634B17FFD57
00000000000000000002000000000000,1F8A8634DF9EFD57
00000000000000000004000000000000,E5528634A24CFD57
00000000000000000008000000000000,8B228634A630FD57
00000000000000000010000000000000,132286342478FD57
00000000000000000020000000000000,C8E286347688FD57
00000000000000000040000000000000,2262863469A8FD57
00000000000000000080000000000000,056286343AE8FD57
00000000000000000100000000000000,076286348D68FD57
00000000000000000200000000000000,036286342E68FD57
00000000000000000400000000000000,7B6286344C68FD57
00000000000000000800000000000000,1B628634E068FD57
00000000000000001000000000000000,5B6286341868FD57
00000000000000002000000000000000,7B6286346868FD57
00000000000000004000000000000000,FB6286348868FD57
00000000000000008000000000000000,FB628634C868FD57
00000000000000010000000000000000,B9DF81C9E0E7477B
00000000000000020000000000000000,0CC6F98630E75E37
00000000000000040000000000000000,97E005B072E69EA7
00000000000000080000000000000000,EE32569C72129F67
00000000000000100000000000000000,3B8B5B849E618E17
00000000000000200000000000000000,D40705D4F2D2AA97
00000000000000400000000000000000,62BA4074FB6198D7
00000000000000800000000000000000,66EB08B42B801657
00000000000001000000000000000000,9A45213461465357
00000000000002000000000000000000,86B5D03403C2A157
00000000000004000000000000000000,FFEBDA34B7CBFD57
00000000000008000000000000000000,52997E34CCF75D57
00000000000010000000000000000000,726076349EF63D57
00000000000020000000000000000000,984AE634913C7D57
00000000000040000000000000000000,1BEAC63496107D57
00000000000080000000000000000000,16F40634B320FD57
00000000000100000000000000000000,0257863413B2FD57
00000000000200000000000000000000,DB448634FD58FD57
00000000000400000000000000000000,40EE86341A38FD57
00000000000800000000000000000000,6E8A8634EDD8FD57
00000000001000000000000000000000,E09286345168FD57
00000000002000000000000000000000,CAC2863498E8FD57
00000000004000000000000000000000,D7A2863449E8FD57
00000000008000000000000000000000,8AE28634C668FD57
00000000010000000000000000000000,686286341468FD57
00000000020000000000000000000000,A9628634EC68FD57
00000000040000000000000000000000,4F6286344068FD57
00000000080000000000000000000000,03628634F868FD57
00000000100000000000000000000000,4B6286340868FD57
00000000200000000000000000000000,1B628634C868FD57
00000000400000000000000000000000,BB628634C868FD57
00000000800000000000000000000000,7B6286344868FD57
00000001000000000000000000000000,200D074580246F4B
00000002000000000000000000000000,982AA8CA7C7F153B
00000004000000000000000000000000,22A96450F4FE9CC7
00000008000000000000000000000000,9465944C250C2CE7
00000010000000000000000000000000,7C960844D9AE1CD7
00000020000000000000000000000000,B539E214CB95E597
00000040000000000000000000000000,2870D3747CBEECD7
00000080000000000000000000000000,48ECDFB460072057
00000100000000000000000000000000,95F70734446CD557
00000200000000000000000000000000,23E33C340D261D57
00000400000000000000000000000000,5659F234C5E9AD57
00000800000000000000000000000000,7EB29E34774B3D57
00001000000000000000000000000000,936976344F893D57
00002000000000000000000000000000,BC462634CD1C7D57
00004000000000000000000000000000,0401C63467B0FD57
00008000000000000000000000000000,CD7406348F89FD57
00010000000000000000000000000000,FACD863436D0FD57
00020000000000000000000000000000,6F3086349294FD57
00040000000000000000000000000000,67B68634B838FD57
00080000000000000000000000000000,9B5A86347808FD57
00100000000000000000000000000000,95D286347808FD57
00200000000000000000000000000000,650286340A28FD57
00400000000000000000000000000000,5D228634D7E8FD57
00800000000000000000000000000000,32E28634A868FD57
01000000000000000000000000000000,E06286349668FD57
02000000000000000000000000000000,3D6286342068FD57
04000000000000000000000000000000,77628634C068FD57
08000000000000000000000000000000,536286340868FD57
10000000000000000000000000000000,AB628634C868FD57
20000000000000000000000000000000,DB6286344868FD57
40000000000000000000000000000000,BB6286344868FD57
80000000000000000000000000000000,7B6286344868FD57


As you can easily see, my initial idea was close, but not completely true. It was true that high order bits of each word in the key only affected high order bits in the ciphertext words, but as you worked through the words towards the least significant bit, my idea seemed to break down. However, some part of my idea was correct, and this spurred me on to investigate more.

Stage 4 - Analysis of the new results

From more careful analysis of the results, I came to the conclusion that there was approximately four bits (one hexadecimal digit) from the odd plaintext words, that affected a corresponding four bits of the ciphertext words. Likewise for the even words. By this I mean that I thought that only the highest four bits of plaintext words one and three affected the highest four bits of both ciphertext words, and so on, jumping through the words from left to right by four bits every time. However, to verify each set of bits, you needed to know the original plaintext (to trial encrypt) and the correct ciphertext (for comparison). Hence, this was a known-plaintext attack. I now had my attack after approximately fifteen hours of concentrated analysis, coding and debugging.

Stage 5 - Breaking the cipher

To verify this analysis I decided to write a brute force password cracker, based upon this idea. However, it would start at the other side of the word (the lowest bits first) and work towards the left. It would try all possible combinations of a block of four bits in all four words of the key, running through the rc5 key expansion procedure, and comparing the appropriate four bits of ciphertext. It would store all correct combinations, and trial each of these combinations against all combinations of the next four bits, discarding any incorrect combinations while storing the correct combinations for the next four bits. I thought that by doing this the possible combinations of key values would gradually decrease until the correct key was found. This resulted in the horrible coding of rc5-crack1.c, with nested for's and if's of up to eight deep. The program generates a pseudo-random key and successfully brute forces it within a short period of time. The awful coding style made debugging incredibly difficult, and is something I would change (after learning better C skills) if I was to repeat.

Code:
rc5-crack1.c

#include <stdio.h>
typedef unsigned long int WORD; /* Should be 32-bit = 4 bytes        */
#define w        32             /* word size in bits                 */
#define r        8              /* number of rounds                  */ 
#define b        16             /* number of bytes in key            */
#define c         4             /* number  words in key = ceil(8*b/w)*/
#define t        18             /* size of table S = 2*(r+1) words   */
WORD S[t];                      /* expanded key table                */
WORD P = 0xb7e15163, Q = 0x9e3779b9;  /* magic constants             */

void RC5_ENCRYPT(WORD *pt, WORD *ct) { /* 2 WORD input pt/output ct  */
   
   WORD i, A=pt[0]+S[0], B=pt[1]+S[1];
   
   for (i=1; i<=r; i++) {
      A = (A^B)+S[2*i];
      B = (B^A)+S[2*i+1];
   }
 
   ct[0] = A; ct[1] = B; 
}

void RC5_DECRYPT(WORD *ct, WORD *pt) { /* 2 WORD input ct/output pt  */
   
   WORD i, B=ct[1], A=ct[0];
   
   for (i=r; i>0; i--) {
      B = (B-S[2*i+1])^A;
      A = (A-S[2*i])^B;
       }
   
     pt[1] = B-S[1]; pt[0] = A-S[0]; 
}

void RC5_SETUP(WORD *K[4]) { /* secret input key K[0...b-1]    */
   
   WORD i, j, k, u=w/8, A, B, L[c];
   
   /* NB: L[] == K[] in this instance */
   
   for (S[0]=P,i=1; i<t; i++) {
      S[i] = S[i-1]+Q;
   }

   L[0]=K[0];
   L[1]=K[1];
   L[2]=K[2];
   L[3]=K[3];

   for (A=B=i=j=k=0; k<3*t; k++,i=(i+1)%t,j=(j+1)%c) { /* 3*t times */
      A = S[i] = S[i]+(A+B); 
      B = L[j] = L[j]+(A+B);
   }
}

int main() {
   
   WORD pt[2] = {0,0};
          WORD ct[2] = {0,0};
   WORD key[c] = {0,0,0,0};
   WORD setkey[c] = {0,0,0,0};
   WORD setct[2] = {0,0,};

   int ia, ib, ic, id, ie;
   
   WORD stage1count = 0;
   WORD stage1[16384][c];
   WORD stage2count = 0;
   WORD stage2[16384][c];
   WORD stage3count = 0;
   WORD stage3[16384][c];
   WORD stage4count = 0;
   WORD stage4[16384][c];
   WORD stage5count = 0;
   WORD stage5[16384][c];
   WORD stage6count = 0;
   WORD stage6[16384][c];
   WORD stage7count = 0;
   WORD stage7[16384][c];
   WORD stage8count = 0;
   WORD stage8[16384][c];
   
   /* check WORD size */
   if (sizeof(WORD)!=4) {
          printf("RC5 error: WORD has %d bytes.\n",sizeof(WORD));
      return(1);
   }

   /* set the key to find */
   setkey[0]=0x18A5FA2C;
   setkey[1]=0x1097180A;
   setkey[2]=0x28AE9651;
   setkey[3]=0x892CDF4B;

   /* set the plaintext */

   printf("RC5 Cracker\n\n");
   printf("Information:\n");
   printf("    Pseudo-random key: ");
   printf("%.8lX%.8lX%.8lX%.8lX\n",setkey[0],setkey[1],setkey[2],setkey[3]);
   printf("    Plaintext        : ");
   printf("%.8lX%.8lX\n",pt[0],pt[1]);

   /* encrypt using pseudo-random key */
   RC5_SETUP(setkey);
   RC5_ENCRYPT(pt,setct);
   printf("    Ciphertext       : ");
   printf("%.8lX%.8lX\n\n",setct[0],setct[1]);


   /* crack the key, ignoring any result that is just zero's */
   
   printf("Calculating...\n");
   
   for (ia=0; ia<16; ia++) {
      for (ib=0; ib<16; ib++) {
         for (ic=0; ic<16; ic++) {
            for (id=0; id<16; id++) {
               key[3]=ia;
               key[2]=ib;
               key[1]=ic;
               key[0]=id;
               
               RC5_SETUP(key);
               RC5_ENCRYPT(pt,ct);

               if ((ct[1] & 0x0000000F) == (setct[1] & 0x0000000F)) {
                  if ((ct[0] & 0x0000000F) == (setct[0] & 0x0000000F)) {
                     stage1count++;
                     stage1[stage1count][0]=key[0];
                     stage1[stage1count][1]=key[1];
                     stage1[stage1count][2]=key[2];
                     stage1[stage1count][3]=key[3];
                  }
               }
            }
         }
      }
   }

   printf("    Found %d combinations to get 1 correct byte\n", stage1count);

   for (ia=0; ia<16; ia++) {
      for (ib=0; ib<16; ib++) {
         for (ic=0; ic<16; ic++) {
            for (id=0; id<16; id++) {
               key[3]=(ia<<4);
               key[2]=(ib<<4);
               key[1]=(ic<<4);
               key[0]=(id<<4);
               
               RC5_SETUP(key);
               RC5_ENCRYPT(pt,ct);

               if ((ct[1] & 0x000000F0) == (setct[1] & 0x000000F0)) {
                  if ((ct[0] & 0x000000F0) == (setct[0] & 0x000000F0)) {
                     
                     for (ie=0; ie<stage1count; ie++) {
                        key[3]=stage1[ie][3] + (ia<<4);
                        key[2]=stage1[ie][2] + (ib<<4);
                        key[1]=stage1[ie][1] + (ic<<4);
                        key[0]=stage1[ie][0] + (id<<4);

                        RC5_SETUP(key);
                        RC5_ENCRYPT(pt,ct);

                        if ((ct[1] & 0x000000FF) == (setct[1] & 0x000000FF)) {
                           if ((ct[0] & 0x000000FF) == (setct[0] & 0x000000FF)) {
                              stage2count++;
                              stage2[stage2count][0]=key[0];
                              stage2[stage2count][1]=key[1];
                              stage2[stage2count][2]=key[2];
                              stage2[stage2count][3]=key[3];
                           }
                        }
                     }
                  }
               }
            }
         }
      }
   }
   
   printf("    Found %d combinations to get 2 correct bytes\n", stage2count);

   for (ia=0; ia<16; ia++) {
      for (ib=0; ib<16; ib++) {
         for (ic=0; ic<16; ic++) {
            for (id=0; id<16; id++) {
               key[3] = (ia<<8);
               key[2] = (ib<<8);
               key[1] = (ic<<8);
               key[0] = (id<<8);

               RC5_SETUP(key);
               RC5_ENCRYPT(pt,ct);
               
               if ((ct[1] & 0x00000F00) == (setct[1] & 0x00000F00)) {
                  if ((ct[0] & 0x00000F00) == (setct[0] & 0x00000F00)) {
                     for (ie=0; ie<stage2count; ie++) {
                  
                        key[3]=stage2[ie][3] + (ia<<8);
                        key[2]=stage2[ie][2] + (ib<<8);
                        key[1]=stage2[ie][1] + (ic<<8);
                        key[0]=stage2[ie][0] + (id<<8);

                        RC5_SETUP(key);
                        RC5_ENCRYPT(pt,ct);
                  
                        if ((ct[1] & 0x00000FFF) == (setct[1] & 0x00000FFF)) {
                           if ((ct[0] & 0x00000FFF) == (setct[0] & 0x00000FFF)) {
                              stage3count++;
                              stage3[stage3count][0]=key[0];
                              stage3[stage3count][1]=key[1];
                              stage3[stage3count][2]=key[2];
                              stage3[stage3count][3]=key[3];
                           }
                        }
                     }
                  }
               }
            }
         }
      }
   }

   printf("    Found %d combinations to get 3 correct bytes\n", stage3count);

   for (ia=0; ia<16; ia++) {
      for (ib=0; ib<16; ib++) {
         for (ic=0; ic<16; ic++) {
            for (id=0; id<16; id++) {
               key[3]=(ia<<12);
               key[2]=(ib<<12);
               key[1]=(ic<<12);
               key[0]=(id<<12);

               RC5_SETUP(key);
               RC5_ENCRYPT(pt,ct);

               if ((ct[1] & 0x0000F000) == (setct[1] & 0x0000F000)) {
                  if ((ct[0] & 0x0000F000) == (setct[0] & 0x0000F000)) {
                     for (ie=0; ie<stage3count; ie++) {
                        key[3]=(stage3[ie][3] + (ia<<12));
                        key[2]=(stage3[ie][2] + (ib<<12));
                        key[1]=(stage3[ie][1] + (ic<<12));
                        key[0]=(stage3[ie][0] + (id<<12));

                        RC5_SETUP(key);
                        RC5_ENCRYPT(pt,ct);

                        if ((ct[1] & 0x0000FFFF) == (setct[1] & 0x0000FFFF)) {
                           if ((ct[0] & 0x0000FFFF) == (setct[0] & 0x0000FFFF)) {
                              stage4count++;
                              stage4[stage4count][0]=key[0];
                              stage4[stage4count][1]=key[1];
                              stage4[stage4count][2]=key[2];
                              stage4[stage4count][3]=key[3];
                           }
                        }
                     }
                  }
               }
            }
         }
      }
   }

   printf("    Found %d combinations to get 4 correct bytes\n", stage4count);

   for (ia=0; ia<16; ia++) {
      for (ib=0; ib<16; ib++) {
         for (ic=0; ic<16; ic++) {
            for (id=0; id<16; id++) {
               key[3]=(ia<<16);
               key[2]=(ib<<16);
               key[1]=(ic<<16);
               key[0]=(id<<16);

               RC5_SETUP(key);
               RC5_ENCRYPT(pt,ct);

               if ((ct[1] & 0x000F0000) == (setct[1] & 0x000F0000)) {
                  if ((ct[0] & 0x000F0000) == (setct[0] & 0x000F0000)) {
                     for (ie=0; ie<stage4count; ie++) {
                        key[3]=(stage4[ie][3] + (ia<<16));
                        key[2]=(stage4[ie][2] + (ib<<16));
                        key[1]=(stage4[ie][1] + (ic<<16));
                        key[0]=(stage4[ie][0] + (id<<16));

                        RC5_SETUP(key);
                        RC5_ENCRYPT(pt,ct);

                        if ((ct[1] & 0x000FFFFF) == (setct[1] & 0x000FFFFF)) {
                           if ((ct[0] & 0x000FFFFF) == (setct[0] & 0x000FFFFF)) {
                              stage5count++;
                              stage5[stage5count][0]=key[0];
                              stage5[stage5count][1]=key[1];
                              stage5[stage5count][2]=key[2];
                              stage5[stage5count][3]=key[3];
                           }
                        }
                     }
                  }
               }
            }
         }
      }
   }

   printf("    Found %d combinations to get 5 correct bytes\n", stage5count);

   for (ia=0; ia<16; ia++) {
      for (ib=0; ib<16; ib++) {
         for (ic=0; ic<16; ic++) {
            for (id=0; id<16; id++) {
               key[3]=(ia<<20);
               key[2]=(ib<<20);
               key[1]=(ic<<20);
               key[0]=(id<<20);

               RC5_SETUP(key);
               RC5_ENCRYPT(pt,ct);

               if ((ct[1] & 0x00F00000) == (setct[1] & 0x00F00000)) {
                  if ((ct[0] & 0x00F00000) == (setct[0] & 0x00F00000)) {
                     for (ie=0; ie<stage5count; ie++) {
                        key[3]=(stage5[ie][3] + (ia<<20));
                        key[2]=(stage5[ie][2] + (ib<<20));
                        key[1]=(stage5[ie][1] + (ic<<20));
                        key[0]=(stage5[ie][0] + (id<<20));

                        RC5_SETUP(key);
                        RC5_ENCRYPT(pt,ct);

                        if ((ct[1] & 0x00FFFFFF) == (setct[1] & 0x00FFFFFF)) {
                           if ((ct[0] & 0x00FFFFFF) == (setct[0] & 0x00FFFFFF)) {
                              stage6count++;
                              stage6[stage6count][0]=key[0];
                              stage6[stage6count][1]=key[1];
                              stage6[stage6count][2]=key[2];
                              stage6[stage6count][3]=key[3];
                           }
                        }
                     }
                  }
               }
            }
         }
      }
   }

   printf("    Found %d combinations to get 6 correct bytes\n", stage6count);

   for (ia=0; ia<16; ia++) {
      for (ib=0; ib<16; ib++) {
         for (ic=0; ic<16; ic++) {
            for (id=0; id<16; id++) {
               key[3]=(ia<<24);
               key[2]=(ib<<24);
               key[1]=(ic<<24);
               key[0]=(id<<24);

               RC5_SETUP(key);
               RC5_ENCRYPT(pt,ct);

               if ((ct[1] & 0x0F000000) == (setct[1] & 0x0F000000)) {
                  if ((ct[0] & 0x0F000000) == (setct[0] & 0x0F000000)) {
                     for (ie=0; ie<stage6count; ie++) {
                        key[3]=(stage6[ie][3] + (ia<<24));
                        key[2]=(stage6[ie][2] + (ib<<24));
                        key[1]=(stage6[ie][1] + (ic<<24));
                        key[0]=(stage6[ie][0] + (id<<24));

                        RC5_SETUP(key);
                        RC5_ENCRYPT(pt,ct);

                        if ((ct[1] & 0x0FFFFFFF) == (setct[1] & 0x0FFFFFFF)) {
                           if ((ct[0] & 0x0FFFFFFF) == (setct[0] & 0x0FFFFFFF)) {
                              stage7count++;
                              stage7[stage7count][0]=key[0];
                              stage7[stage7count][1]=key[1];
                              stage7[stage7count][2]=key[2];
                              stage7[stage7count][3]=key[3];
                           }
                        }
                     }
                  }
               }
            }
         }
      }
   }

   printf("    Found %d combinations to get 7 correct bytes\n", stage7count);

   for (ia=0; ia<16; ia++) {
      for (ib=0; ib<16; ib++) {
         for (ic=0; ic<16; ic++) {
            for (id=0; id<16; id++) {
               key[3]=(ia<<28);
               key[2]=(ib<<28);
               key[1]=(ic<<28);
               key[0]=(id<<28);

               RC5_SETUP(key);
               RC5_ENCRYPT(pt,ct);

               if ((ct[1] & 0xF0000000) == (setct[1] & 0xF0000000)) {
                  if ((ct[0] & 0xF0000000) == (setct[0] & 0xF0000000)) {
                     for (ie=0; ie<stage7count; ie++) {
                        key[3]=(stage7[ie][3] + (ia<<28));
                        key[2]=(stage7[ie][2] + (ib<<28));
                        key[1]=(stage7[ie][1] + (ic<<28));
                        key[0]=(stage7[ie][0] + (id<<28));

                        RC5_SETUP(key);
                        RC5_ENCRYPT(pt,ct);

                        if ((ct[1] & 0xFFFFFFFF) == (setct[1] & 0xFFFFFFFF)) {
                           if ((ct[0] & 0xFFFFFFFF) == (setct[0] & 0xFFFFFFFF)) {
                              stage8count++;
                              stage8[stage8count][0]=key[0];
                              stage8[stage8count][1]=key[1];
                              stage8[stage8count][2]=key[2];
                              stage8[stage8count][3]=key[3];
                           }
                        }
                     }
                  }
               }
            }
         }
      }
   }

   printf("    Found %d combinations to get 8 correct bytes\n\n", stage8count);

   printf("Results:\n");
   for (ia=0; ia<stage8count; ia++) {
      key[0]=stage8[ia][0];
      key[1]=stage8[ia][1];
      key[2]=stage8[ia][2];
      key[3]=stage8[ia][3];
      RC5_SETUP(key);
      RC5_ENCRYPT(pt,ct);
      printf("    Key: %.8lX%.8lX%.8lX%.8lX -> ",key[0],key[1],key[2],key[3]);
      printf("ciphertext: %.8lX%.8lX\n",ct[0],ct[1]);
      
   }
      
   return(0);
}


After compiling this program, it will generate an output such as this:

Quote:
RC5 Cracker

Information:
Pseudo-random key: 18A5FA2C1097180A28AE9651892CDF4B
Plaintext : 0000000000000000
Ciphertext : 8CA07222811CDE76

Calculating...
Found 256 combinations to get 1 correct byte
Found 252 combinations to get 2 correct bytes
Found 312 combinations to get 3 correct bytes
Found 500 combinations to get 4 correct bytes
Found 564 combinations to get 5 correct bytes
Found 460 combinations to get 6 correct bytes
Found 360 combinations to get 7 correct bytes
Found 304 combinations to get 8 correct bytes

Results:
Key: 00000000000000000000000000000000 -> ciphertext: FB6286344868FD57
Key: CCB62876197C388009D0AFA10CF84A99 -> ciphertext: 8CA07222811CDE76
Key: 4CB62876997C388009D0AFA10CF84A99 -> ciphertext: 8CA07222811CDE76
Key: 995308BF2A5150434D90AD23002823AF -> ciphertext: 8CA07222811CDE76
Key: 973F78BF20F5804349100D230F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 195308BFAA5150434D90AD23002823AF -> ciphertext: 8CA07222811CDE76
Key: 173F78BFA0F5804349100D230F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: B3BF78BF0475804389100D230F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: EC8D89E03BAB57168BD425290115EE0B -> ciphertext: 8CA07222811CDE76
Key: E942B3E0326A4D16855685290C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: E7F32876383138808194AFA10DAA4A99 -> ciphertext: 8CA07222811CDE76
Key: 217328767AB138808D94AFA10B2A4A99 -> ciphertext: 8CA07222811CDE76
Key: 27F32876783138808194AFA10DAA4A99 -> ciphertext: 8CA07222811CDE76
Key: 33BF78BF8475804389100D230F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 6C8D89E0BBAB57168BD425290115EE0B -> ciphertext: 8CA07222811CDE76
Key: 6942B3E0B26A4D16855685290C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 67F32876B83138808194AFA10DAA4A99 -> ciphertext: 8CA07222811CDE76
Key: A1732876FAB138808D94AFA10B2A4A99 -> ciphertext: 8CA07222811CDE76
Key: A7F32876F83138808194AFA10DAA4A99 -> ciphertext: 8CA07222811CDE76
Key: 51172E626A1D3EB4C550A3050CB4C658 -> ciphertext: 8CA07222811CDE76
Key: D1172E62EA1D3EB4C550A3050CB4C658 -> ciphertext: 8CA07222811CDE76
Key: 1B8D89E024AB57160DD425291A15EE0B -> ciphertext: 8CA07222811CDE76
Key: F17B7507423525D9095C698112416B78 -> ciphertext: 8CA07222811CDE76
Key: F9DBCB4346551D1D095C65811935B0F8 -> ciphertext: 8CA07222811CDE76
Key: F8D04A88419C1A5E019E298D1E09E5FA -> ciphertext: 8CA07222811CDE76
Key: 5B8D89E064AB57160DD425291A15EE0B -> ciphertext: 8CA07222811CDE76
Key: 9B8D89E0A4AB57160DD425291A15EE0B -> ciphertext: 8CA07222811CDE76
Key: 717B7507C23525D9095C698112416B78 -> ciphertext: 8CA07222811CDE76
Key: 79DBCB43C6551D1D095C65811935B0F8 -> ciphertext: 8CA07222811CDE76
Key: 78D04A88C19C1A5E019E298D1E09E5FA -> ciphertext: 8CA07222811CDE76
Key: DB8D89E0E4AB57160DD425291A15EE0B -> ciphertext: 8CA07222811CDE76
Key: 0942B3E0326A4D16255685291C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 48984A8877D41A5E23DE298D11DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 8942B3E0B26A4D16255685291C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: C8984A88F7D41A5E23DE298D11DDE5FA -> ciphertext: 8CA07222811CDE76
Key: EB7B7507183525D9655C698118416B78 -> ciphertext: 8CA07222811CDE76
Key: 2B7B7507583525D9655C698118416B78 -> ciphertext: 8CA07222811CDE76
Key: 2942B3E0526A4D16655685291C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 6B7B7507983525D9655C698118416B78 -> ciphertext: 8CA07222811CDE76
Key: AB7B7507D83525D9655C698118416B78 -> ciphertext: 8CA07222811CDE76
Key: A942B3E0D26A4D16655685291C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: BE7189E007B35716859C25291EA3EE0B -> ciphertext: 8CA07222811CDE76
Key: 3E7189E087B35716859C25291EA3EE0B -> ciphertext: 8CA07222811CDE76
Key: A4F328767B3138800B94AFA1252A4A99 -> ciphertext: 8CA07222811CDE76
Key: 24F32876FB3138800B94AFA1252A4A99 -> ciphertext: 8CA07222811CDE76
Key: FCB62876497C388049D0AFA12CF84A99 -> ciphertext: 8CA07222811CDE76
Key: 7CB62876C97C388049D0AFA12CF84A99 -> ciphertext: 8CA07222811CDE76
Key: 8B7B7507183525D9C55C698128416B78 -> ciphertext: 8CA07222811CDE76
Key: 89FAA2B41EB2320AC1566B692D4FFEC4 -> ciphertext: 8CA07222811CDE76
Key: 5B05A2B42083320ACD346B69242D7EC4 -> ciphertext: 8CA07222811CDE76
Key: 5DFE39172EB48F21C5100DE128183C5C -> ciphertext: 8CA07222811CDE76
Key: 44FB750759B525D9C15C698120C16B78 -> ciphertext: 8CA07222811CDE76
Key: 40FB750755B525D9C95C698128C16B78 -> ciphertext: 8CA07222811CDE76
Key: 4B904A885C1C1A5EC11E298D2D69E5FA -> ciphertext: 8CA07222811CDE76
Key: 4D7B75075A3525D9C95C69812DC16B78 -> ciphertext: 8CA07222811CDE76
Key: 0B7B7507983525D9C55C698128416B78 -> ciphertext: 8CA07222811CDE76
Key: 09FAA2B49EB2320AC1566B692D4FFEC4 -> ciphertext: 8CA07222811CDE76
Key: DB05A2B4A083320ACD346B69242D7EC4 -> ciphertext: 8CA07222811CDE76
Key: DDFE3917AEB48F21C5100DE128183C5C -> ciphertext: 8CA07222811CDE76
Key: C4FB7507D9B525D9C15C698120C16B78 -> ciphertext: 8CA07222811CDE76
Key: C0FB7507D5B525D9C95C698128C16B78 -> ciphertext: 8CA07222811CDE76
Key: CB904A88DC1C1A5EC11E298D2D69E5FA -> ciphertext: 8CA07222811CDE76
Key: CD7B7507DA3525D9C95C69812DC16B78 -> ciphertext: 8CA07222811CDE76
Key: 08984A8837D41A5E23DE298D31DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 0EF989E031BB57162F1C2529339BEE0B -> ciphertext: 8CA07222811CDE76
Key: C8984A8877D41A5E23DE298D31DDE5FA -> ciphertext: 8CA07222811CDE76
Key: CEF989E071BB57162F1C2529339BEE0B -> ciphertext: 8CA07222811CDE76
Key: CF3A689C7C7270A22D56EDE13437A7D8 -> ciphertext: 8CA07222811CDE76
Key: C5D04A88769C1A5E2D9E298D3B09E5FA -> ciphertext: 8CA07222811CDE76
Key: C942B3E0726A4D16255685293C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: CCD24B437D1A9D1D215665813E9FF0F8 -> ciphertext: 8CA07222811CDE76
Key: 88984A88B7D41A5E23DE298D31DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 8EF989E0B1BB57162F1C2529339BEE0B -> ciphertext: 8CA07222811CDE76
Key: 48984A88F7D41A5E23DE298D31DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 4EF989E0F1BB57162F1C2529339BEE0B -> ciphertext: 8CA07222811CDE76
Key: 4F3A689CFC7270A22D56EDE13437A7D8 -> ciphertext: 8CA07222811CDE76
Key: 45D04A88F69C1A5E2D9E298D3B09E5FA -> ciphertext: 8CA07222811CDE76
Key: 4942B3E0F26A4D16255685293C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 4CD24B43FD1A9D1D215665813E9FF0F8 -> ciphertext: 8CA07222811CDE76
Key: D1DBCB4326551D1D415C65813535B0F8 -> ciphertext: 8CA07222811CDE76
Key: D9DBCB4326551D1D495C65813935B0F8 -> ciphertext: 8CA07222811CDE76
Key: D89AE11721527F21419EA5E13EC3865C -> ciphertext: 8CA07222811CDE76
Key: 51DBCB43A6551D1D415C65813535B0F8 -> ciphertext: 8CA07222811CDE76
Key: 59DBCB43A6551D1D495C65813935B0F8 -> ciphertext: 8CA07222811CDE76
Key: 589AE117A1527F21419EA5E13EC3865C -> ciphertext: 8CA07222811CDE76
Key: 1813391763598F21C3D40DE13356BC5C -> ciphertext: 8CA07222811CDE76
Key: 173F78BF60F58043C9100D233F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 98133917E3598F21C3D40DE13356BC5C -> ciphertext: 8CA07222811CDE76
Key: 973F78BFE0F58043C9100D233F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: B3BF78BF0475804309100D234F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 8CB62876597C388009D0AFA14CF84A99 -> ciphertext: 8CA07222811CDE76
Key: 24FB750779B525D9015C698140C16B78 -> ciphertext: 8CA07222811CDE76
Key: 2DB00E887EFA565E0D50E98D43BABDFA -> ciphertext: 8CA07222811CDE76
Key: 217328767AB138800D94AFA14B2A4A99 -> ciphertext: 8CA07222811CDE76
Key: 33BF78BF8475804309100D234F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 0CB62876D97C388009D0AFA14CF84A99 -> ciphertext: 8CA07222811CDE76
Key: A4FB7507F9B525D9015C698140C16B78 -> ciphertext: 8CA07222811CDE76
Key: ADB00E88FEFA565E0D50E98D43BABDFA -> ciphertext: 8CA07222811CDE76
Key: A1732876FAB138800D94AFA14B2A4A99 -> ciphertext: 8CA07222811CDE76
Key: 195308BF2A5150434D90AD23402823AF -> ciphertext: 8CA07222811CDE76
Key: 11172E622A1D3EB44550A3054CB4C658 -> ciphertext: 8CA07222811CDE76
Key: 995308BFAA5150434D90AD23402823AF -> ciphertext: 8CA07222811CDE76
Key: 91172E62AA1D3EB44550A3054CB4C658 -> ciphertext: 8CA07222811CDE76
Key: 64FB750739B525D9815C698140C16B78 -> ciphertext: 8CA07222811CDE76
Key: 6C8D89E03BAB57168BD425294115EE0B -> ciphertext: 8CA07222811CDE76
Key: 6942B3E0326A4D16855685294C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: E4FB7507B9B525D9815C698140C16B78 -> ciphertext: 8CA07222811CDE76
Key: EC8D89E0BBAB57168BD425294115EE0B -> ciphertext: 8CA07222811CDE76
Key: E942B3E0B26A4D16855685294C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: A5D04A88569C1A5E6D9E298D5B09E5FA -> ciphertext: 8CA07222811CDE76
Key: A942B3E0526A4D16655685295C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 25D04A88D69C1A5E6D9E298D5B09E5FA -> ciphertext: 8CA07222811CDE76
Key: 2942B3E0D26A4D16655685295C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: F8D04A88419C1A5E819E298D5E09E5FA -> ciphertext: 8CA07222811CDE76
Key: 78D04A88C19C1A5E819E298D5E09E5FA -> ciphertext: 8CA07222811CDE76
Key: 08984A8837D41A5EA3DE298D51DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 0942B3E0326A4D16A55685295C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 88984A88B7D41A5EA3DE298D51DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 8942B3E0B26A4D16A55685295C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 3CB62876097C388049D0AFA16CF84A99 -> ciphertext: 8CA07222811CDE76
Key: 8B904A881C1C1A5E411E298D6D69E5FA -> ciphertext: 8CA07222811CDE76
Key: 8D7B75071A3525D9495C69816DC16B78 -> ciphertext: 8CA07222811CDE76
Key: BCB62876897C388049D0AFA16CF84A99 -> ciphertext: 8CA07222811CDE76
Key: 0B904A889C1C1A5E411E298D6D69E5FA -> ciphertext: 8CA07222811CDE76
Key: 0D7B75079A3525D9495C69816DC16B78 -> ciphertext: 8CA07222811CDE76
Key: AB7B7507783525D9855C698168416B78 -> ciphertext: 8CA07222811CDE76
Key: 2B7B7507F83525D9855C698168416B78 -> ciphertext: 8CA07222811CDE76
Key: 5EF989E021BB5716CF1C2529639BEE0B -> ciphertext: 8CA07222811CDE76
Key: 53BF78BF24758043C9100D236F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: CB7B7507583525D9C55C698168416B78 -> ciphertext: 8CA07222811CDE76
Key: 1EF989E061BB5716CF1C2529639BEE0B -> ciphertext: 8CA07222811CDE76
Key: 1B05A2B46083320ACD346B69642D7EC4 -> ciphertext: 8CA07222811CDE76
Key: DEF989E0A1BB5716CF1C2529639BEE0B -> ciphertext: 8CA07222811CDE76
Key: D3BF78BFA4758043C9100D236F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 4B7B7507D83525D9C55C698168416B78 -> ciphertext: 8CA07222811CDE76
Key: 9EF989E0E1BB5716CF1C2529639BEE0B -> ciphertext: 8CA07222811CDE76
Key: 9B05A2B4E083320ACD346B69642D7EC4 -> ciphertext: 8CA07222811CDE76
Key: 097B75073A3525D9295C698176416B78 -> ciphertext: 8CA07222811CDE76
Key: 09DBCB433E551D1D215C65817D35B0F8 -> ciphertext: 8CA07222811CDE76
Key: 6E7189E057B35716259C25297EA3EE0B -> ciphertext: 8CA07222811CDE76
Key: 897B7507BA3525D9295C698176416B78 -> ciphertext: 8CA07222811CDE76
Key: 89DBCB43BE551D1D215C65817D35B0F8 -> ciphertext: 8CA07222811CDE76
Key: EE7189E0D7B35716259C25297EA3EE0B -> ciphertext: 8CA07222811CDE76
Key: D73F78BF20F5804349100D237F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 99DBCB4366551D1D495C65817935B0F8 -> ciphertext: 8CA07222811CDE76
Key: 573F78BFA0F5804349100D237F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 19DBCB43E6551D1D495C65817935B0F8 -> ciphertext: 8CA07222811CDE76
Key: FF7B7507483525D9895C69817FC16B78 -> ciphertext: 8CA07222811CDE76
Key: 7F7B7507C83525D9895C69817FC16B78 -> ciphertext: 8CA07222811CDE76
Key: 297B75071A3525D9A95C698176416B78 -> ciphertext: 8CA07222811CDE76
Key: 45D04A88769C1A5EAD9E298D7B09E5FA -> ciphertext: 8CA07222811CDE76
Key: A97B75079A3525D9A95C698176416B78 -> ciphertext: 8CA07222811CDE76
Key: C5D04A88F69C1A5EAD9E298D7B09E5FA -> ciphertext: 8CA07222811CDE76
Key: CCB62876197C388009D0AFA18CF84A99 -> ciphertext: 8CA07222811CDE76
Key: 4CB62876997C388009D0AFA18CF84A99 -> ciphertext: 8CA07222811CDE76
Key: 995308BF2A5150434D90AD23802823AF -> ciphertext: 8CA07222811CDE76
Key: 973F78BF20F5804349100D238F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 195308BFAA5150434D90AD23802823AF -> ciphertext: 8CA07222811CDE76
Key: 173F78BFA0F5804349100D238F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: B3BF78BF0475804389100D238F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: EC8D89E03BAB57168BD425298115EE0B -> ciphertext: 8CA07222811CDE76
Key: E942B3E0326A4D16855685298C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: E7F32876383138808194AFA18DAA4A99 -> ciphertext: 8CA07222811CDE76
Key: 217328767AB138808D94AFA18B2A4A99 -> ciphertext: 8CA07222811CDE76
Key: 27F32876783138808194AFA18DAA4A99 -> ciphertext: 8CA07222811CDE76
Key: 33BF78BF8475804389100D238F2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 6C8D89E0BBAB57168BD425298115EE0B -> ciphertext: 8CA07222811CDE76
Key: 6942B3E0B26A4D16855685298C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 67F32876B83138808194AFA18DAA4A99 -> ciphertext: 8CA07222811CDE76
Key: A1732876FAB138808D94AFA18B2A4A99 -> ciphertext: 8CA07222811CDE76
Key: A7F32876F83138808194AFA18DAA4A99 -> ciphertext: 8CA07222811CDE76
Key: 51172E626A1D3EB4C550A3058CB4C658 -> ciphertext: 8CA07222811CDE76
Key: D1172E62EA1D3EB4C550A3058CB4C658 -> ciphertext: 8CA07222811CDE76
Key: 1B8D89E024AB57160DD425299A15EE0B -> ciphertext: 8CA07222811CDE76
Key: F17B7507423525D9095C698192416B78 -> ciphertext: 8CA07222811CDE76
Key: F9DBCB4346551D1D095C65819935B0F8 -> ciphertext: 8CA07222811CDE76
Key: F8D04A88419C1A5E019E298D9E09E5FA -> ciphertext: 8CA07222811CDE76
Key: 5B8D89E064AB57160DD425299A15EE0B -> ciphertext: 8CA07222811CDE76
Key: 9B8D89E0A4AB57160DD425299A15EE0B -> ciphertext: 8CA07222811CDE76
Key: 717B7507C23525D9095C698192416B78 -> ciphertext: 8CA07222811CDE76
Key: 79DBCB43C6551D1D095C65819935B0F8 -> ciphertext: 8CA07222811CDE76
Key: 78D04A88C19C1A5E019E298D9E09E5FA -> ciphertext: 8CA07222811CDE76
Key: DB8D89E0E4AB57160DD425299A15EE0B -> ciphertext: 8CA07222811CDE76
Key: 0942B3E0326A4D16255685299C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 48984A8877D41A5E23DE298D91DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 8942B3E0B26A4D16255685299C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: C8984A88F7D41A5E23DE298D91DDE5FA -> ciphertext: 8CA07222811CDE76
Key: EB7B7507183525D9655C698198416B78 -> ciphertext: 8CA07222811CDE76
Key: 2B7B7507583525D9655C698198416B78 -> ciphertext: 8CA07222811CDE76
Key: 2942B3E0526A4D16655685299C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 6B7B7507983525D9655C698198416B78 -> ciphertext: 8CA07222811CDE76
Key: AB7B7507D83525D9655C698198416B78 -> ciphertext: 8CA07222811CDE76
Key: A942B3E0D26A4D16655685299C1F5C0B -> ciphertext: 8CA07222811CDE76
Key: BE7189E007B35716859C25299EA3EE0B -> ciphertext: 8CA07222811CDE76
Key: 3E7189E087B35716859C25299EA3EE0B -> ciphertext: 8CA07222811CDE76
Key: A4F328767B3138800B94AFA1A52A4A99 -> ciphertext: 8CA07222811CDE76
Key: 24F32876FB3138800B94AFA1A52A4A99 -> ciphertext: 8CA07222811CDE76
Key: FCB62876497C388049D0AFA1ACF84A99 -> ciphertext: 8CA07222811CDE76
Key: 7CB62876C97C388049D0AFA1ACF84A99 -> ciphertext: 8CA07222811CDE76
Key: 8B7B7507183525D9C55C6981A8416B78 -> ciphertext: 8CA07222811CDE76
Key: 89FAA2B41EB2320AC1566B69AD4FFEC4 -> ciphertext: 8CA07222811CDE76
Key: 5B05A2B42083320ACD346B69A42D7EC4 -> ciphertext: 8CA07222811CDE76
Key: 5DFE39172EB48F21C5100DE1A8183C5C -> ciphertext: 8CA07222811CDE76
Key: 44FB750759B525D9C15C6981A0C16B78 -> ciphertext: 8CA07222811CDE76
Key: 40FB750755B525D9C95C6981A8C16B78 -> ciphertext: 8CA07222811CDE76
Key: 4B904A885C1C1A5EC11E298DAD69E5FA -> ciphertext: 8CA07222811CDE76
Key: 4D7B75075A3525D9C95C6981ADC16B78 -> ciphertext: 8CA07222811CDE76
Key: 0B7B7507983525D9C55C6981A8416B78 -> ciphertext: 8CA07222811CDE76
Key: 09FAA2B49EB2320AC1566B69AD4FFEC4 -> ciphertext: 8CA07222811CDE76
Key: DB05A2B4A083320ACD346B69A42D7EC4 -> ciphertext: 8CA07222811CDE76
Key: DDFE3917AEB48F21C5100DE1A8183C5C -> ciphertext: 8CA07222811CDE76
Key: C4FB7507D9B525D9C15C6981A0C16B78 -> ciphertext: 8CA07222811CDE76
Key: C0FB7507D5B525D9C95C6981A8C16B78 -> ciphertext: 8CA07222811CDE76
Key: CB904A88DC1C1A5EC11E298DAD69E5FA -> ciphertext: 8CA07222811CDE76
Key: CD7B7507DA3525D9C95C6981ADC16B78 -> ciphertext: 8CA07222811CDE76
Key: 08984A8837D41A5E23DE298DB1DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 0EF989E031BB57162F1C2529B39BEE0B -> ciphertext: 8CA07222811CDE76
Key: C8984A8877D41A5E23DE298DB1DDE5FA -> ciphertext: 8CA07222811CDE76
Key: CEF989E071BB57162F1C2529B39BEE0B -> ciphertext: 8CA07222811CDE76
Key: CF3A689C7C7270A22D56EDE1B437A7D8 -> ciphertext: 8CA07222811CDE76
Key: C5D04A88769C1A5E2D9E298DBB09E5FA -> ciphertext: 8CA07222811CDE76
Key: C942B3E0726A4D1625568529BC1F5C0B -> ciphertext: 8CA07222811CDE76
Key: CCD24B437D1A9D1D21566581BE9FF0F8 -> ciphertext: 8CA07222811CDE76
Key: 88984A88B7D41A5E23DE298DB1DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 8EF989E0B1BB57162F1C2529B39BEE0B -> ciphertext: 8CA07222811CDE76
Key: 48984A88F7D41A5E23DE298DB1DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 4EF989E0F1BB57162F1C2529B39BEE0B -> ciphertext: 8CA07222811CDE76
Key: 4F3A689CFC7270A22D56EDE1B437A7D8 -> ciphertext: 8CA07222811CDE76
Key: 45D04A88F69C1A5E2D9E298DBB09E5FA -> ciphertext: 8CA07222811CDE76
Key: 4942B3E0F26A4D1625568529BC1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 4CD24B43FD1A9D1D21566581BE9FF0F8 -> ciphertext: 8CA07222811CDE76
Key: D1DBCB4326551D1D415C6581B535B0F8 -> ciphertext: 8CA07222811CDE76
Key: D9DBCB4326551D1D495C6581B935B0F8 -> ciphertext: 8CA07222811CDE76
Key: D89AE11721527F21419EA5E1BEC3865C -> ciphertext: 8CA07222811CDE76
Key: 51DBCB43A6551D1D415C6581B535B0F8 -> ciphertext: 8CA07222811CDE76
Key: 59DBCB43A6551D1D495C6581B935B0F8 -> ciphertext: 8CA07222811CDE76
Key: 589AE117A1527F21419EA5E1BEC3865C -> ciphertext: 8CA07222811CDE76
Key: 1813391763598F21C3D40DE1B356BC5C -> ciphertext: 8CA07222811CDE76
Key: 173F78BF60F58043C9100D23BF2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 98133917E3598F21C3D40DE1B356BC5C -> ciphertext: 8CA07222811CDE76
Key: 973F78BFE0F58043C9100D23BF2C1BAF -> ciphertext: 8CA07222811CDE76
Key: B3BF78BF0475804309100D23CF2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 8CB62876597C388009D0AFA1CCF84A99 -> ciphertext: 8CA07222811CDE76
Key: 24FB750779B525D9015C6981C0C16B78 -> ciphertext: 8CA07222811CDE76
Key: 2DB00E887EFA565E0D50E98DC3BABDFA -> ciphertext: 8CA07222811CDE76
Key: 217328767AB138800D94AFA1CB2A4A99 -> ciphertext: 8CA07222811CDE76
Key: 33BF78BF8475804309100D23CF2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 0CB62876D97C388009D0AFA1CCF84A99 -> ciphertext: 8CA07222811CDE76
Key: A4FB7507F9B525D9015C6981C0C16B78 -> ciphertext: 8CA07222811CDE76
Key: ADB00E88FEFA565E0D50E98DC3BABDFA -> ciphertext: 8CA07222811CDE76
Key: A1732876FAB138800D94AFA1CB2A4A99 -> ciphertext: 8CA07222811CDE76
Key: 195308BF2A5150434D90AD23C02823AF -> ciphertext: 8CA07222811CDE76
Key: 11172E622A1D3EB44550A305CCB4C658 -> ciphertext: 8CA07222811CDE76
Key: 995308BFAA5150434D90AD23C02823AF -> ciphertext: 8CA07222811CDE76
Key: 91172E62AA1D3EB44550A305CCB4C658 -> ciphertext: 8CA07222811CDE76
Key: 64FB750739B525D9815C6981C0C16B78 -> ciphertext: 8CA07222811CDE76
Key: 6C8D89E03BAB57168BD42529C115EE0B -> ciphertext: 8CA07222811CDE76
Key: 6942B3E0326A4D1685568529CC1F5C0B -> ciphertext: 8CA07222811CDE76
Key: E4FB7507B9B525D9815C6981C0C16B78 -> ciphertext: 8CA07222811CDE76
Key: EC8D89E0BBAB57168BD42529C115EE0B -> ciphertext: 8CA07222811CDE76
Key: E942B3E0B26A4D1685568529CC1F5C0B -> ciphertext: 8CA07222811CDE76
Key: A5D04A88569C1A5E6D9E298DDB09E5FA -> ciphertext: 8CA07222811CDE76
Key: A942B3E0526A4D1665568529DC1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 25D04A88D69C1A5E6D9E298DDB09E5FA -> ciphertext: 8CA07222811CDE76
Key: 2942B3E0D26A4D1665568529DC1F5C0B -> ciphertext: 8CA07222811CDE76
Key: F8D04A88419C1A5E819E298DDE09E5FA -> ciphertext: 8CA07222811CDE76
Key: 78D04A88C19C1A5E819E298DDE09E5FA -> ciphertext: 8CA07222811CDE76
Key: 08984A8837D41A5EA3DE298DD1DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 0942B3E0326A4D16A5568529DC1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 88984A88B7D41A5EA3DE298DD1DDE5FA -> ciphertext: 8CA07222811CDE76
Key: 8942B3E0B26A4D16A5568529DC1F5C0B -> ciphertext: 8CA07222811CDE76
Key: 3CB62876097C388049D0AFA1ECF84A99 -> ciphertext: 8CA07222811CDE76
Key: 8B904A881C1C1A5E411E298DED69E5FA -> ciphertext: 8CA07222811CDE76
Key: 8D7B75071A3525D9495C6981EDC16B78 -> ciphertext: 8CA07222811CDE76
Key: BCB62876897C388049D0AFA1ECF84A99 -> ciphertext: 8CA07222811CDE76
Key: 0B904A889C1C1A5E411E298DED69E5FA -> ciphertext: 8CA07222811CDE76
Key: 0D7B75079A3525D9495C6981EDC16B78 -> ciphertext: 8CA07222811CDE76
Key: AB7B7507783525D9855C6981E8416B78 -> ciphertext: 8CA07222811CDE76
Key: 2B7B7507F83525D9855C6981E8416B78 -> ciphertext: 8CA07222811CDE76
Key: 5EF989E021BB5716CF1C2529E39BEE0B -> ciphertext: 8CA07222811CDE76
Key: 53BF78BF24758043C9100D23EF2C1BAF -> ciphertext: 8CA07222811CDE76
Key: CB7B7507583525D9C55C6981E8416B78 -> ciphertext: 8CA07222811CDE76
Key: 1EF989E061BB5716CF1C2529E39BEE0B -> ciphertext: 8CA07222811CDE76
Key: 1B05A2B46083320ACD346B69E42D7EC4 -> ciphertext: 8CA07222811CDE76
Key: DEF989E0A1BB5716CF1C2529E39BEE0B -> ciphertext: 8CA07222811CDE76
Key: D3BF78BFA4758043C9100D23EF2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 4B7B7507D83525D9C55C6981E8416B78 -> ciphertext: 8CA07222811CDE76
Key: 9EF989E0E1BB5716CF1C2529E39BEE0B -> ciphertext: 8CA07222811CDE76
Key: 9B05A2B4E083320ACD346B69E42D7EC4 -> ciphertext: 8CA07222811CDE76
Key: 097B75073A3525D9295C6981F6416B78 -> ciphertext: 8CA07222811CDE76
Key: 09DBCB433E551D1D215C6581FD35B0F8 -> ciphertext: 8CA07222811CDE76
Key: 6E7189E057B35716259C2529FEA3EE0B -> ciphertext: 8CA07222811CDE76
Key: 897B7507BA3525D9295C6981F6416B78 -> ciphertext: 8CA07222811CDE76
Key: 89DBCB43BE551D1D215C6581FD35B0F8 -> ciphertext: 8CA07222811CDE76
Key: EE7189E0D7B35716259C2529FEA3EE0B -> ciphertext: 8CA07222811CDE76
Key: D73F78BF20F5804349100D23FF2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 99DBCB4366551D1D495C6581F935B0F8 -> ciphertext: 8CA07222811CDE76
Key: 573F78BFA0F5804349100D23FF2C1BAF -> ciphertext: 8CA07222811CDE76
Key: 19DBCB43E6551D1D495C6581F935B0F8 -> ciphertext: 8CA07222811CDE76
Key: FF7B7507483525D9895C6981FFC16B78 -> ciphertext: 8CA07222811CDE76
Key: 7F7B7507C83525D9895C6981FFC16B78 -> ciphertext: 8CA07222811CDE76
Key: 297B75071A3525D9A95C6981F6416B78 -> ciphertext: 8CA07222811CDE76
Key: 45D04A88769C1A5EAD9E298DFB09E5FA -> ciphertext: 8CA07222811CDE76
Key: A97B75079A3525D9A95C6981F6416B78 -> ciphertext: 8CA07222811CDE76


Quote:
time `./rc5-crack > //[b][/b]dev[b][/b]/null`

real 0m3.069s
user 0m2.959s
sys 0m0.006s


Stage 6 - Conclusions

Obviously the cipher isn't safe to use, as this weakened version was designed to be broken. However, I found that the cipher was a good starting point to learn cryptanalysis, and many thanks to Bruce Schneier for creating the course. I will now be steadily working my was through the challenges in the cryptanalysis course and possibly documenting my experiences throughout.

One unexpected outcome from the cracking program was the result of many keys that gave the same correct ciphertext. This was not something that I expected, and means that there are further flaws in this weakened version of RC5. Certain different combinations of bits must ultimately have the same effect. I have not performed any analysis of these flaws as of yet, so updates to this paper may arise because of any more research I perform.

Overall, there is probably around twenty hours worth of concentrated work represented here. However, this time was spread over three or so weeks, so there has been much more thinking being done in 'idle' time. I would not yet be able to do all of this in just one or two consecutive days.

Thanks for reading, and I hope you found this an interesting insight into cryptanalysis.

Martin


Last edited by mxb on Mon Jun 11, 2007 6:51 pm; edited 2 times in total
Back to top
View user's profile Send private message
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Mon Jan 03, 2005 3:15 pm    Post subject: Reply with quote

hi,

Quote:
Information:
Pseudo-random key: 18A5FA2C1097180A28AE9651892CDF4B
Plaintext : 0000000000000000
Ciphertext : 8CA07222811CDE76

Calculating...
Found 256 combinations to get 1 correct byte
Found 252 combinations to get 2 correct bytes
Found 312 combinations to get 3 correct bytes
Found 500 combinations to get 4 correct bytes
Found 564 combinations to get 5 correct bytes
Found 460 combinations to get 6 correct bytes
Found 360 combinations to get 7 correct bytes
Found 304 combinations to get 8 correct bytes


Nice read. How many collisions did you find for actual rc5 algorithm?This is a tweaked version,right?

Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
mxb
Trusted SF Member
Trusted SF Member


Joined: 30 Mar 2004
Posts: 6


Offline

PostPosted: Mon Jan 03, 2005 5:12 pm    Post subject: Reply with quote

datah wrote:
Nice read. How many collisions did you find for actual rc5 algorithm?This is a tweaked version,right?


Cheers! I'm glad someone found it interesting! Very Happy

Yes, this is a tweaked version, the rotations have been removed from the original algorithm. From what I understand it is the rotations that give the security, so this modified variant is supposed to be weak, hence the collisions.

I have not expanded the analysis to the full rc5 algorithm, mainly due to a large work load from university. However, due to the rotations, I think that the full rc5 will be a lot stronger, with few collisions.

Hope this helps,
Martin
Back to top
View user's profile Send private message
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Tue Jan 04, 2005 8:34 am    Post subject: Nice. Reply with quote

mxb wrote:

Yes, this is a tweaked version, the rotations have been removed from the original algorithm. From what I understand it is the rotations that give the security, so this modified variant is supposed to be weak, hence the collisions.


That's correct; the variable rotations are the focal point of the design of RC5. While the modular addition and bit-wise XOR operations have respective effects on its security, these data-dependent (i.e., plaintext) rotations are the source of non-linearity in RC5; these rotations are to the non-linearity of RC5 what substitution tables are to the non-linearity of many other block ciphers, so perhaps that is the most obvious hint of their importance. Thus, it's easy to comprehend what is likely to happen when you remove the core of non-linearity.

If you haven't already, I would suggest researching the cryptanalysis of RC5 and numerous variants, by Kelsey, Schneier, and Wagner, Knudsen and Meier, Kaliski and Yin, Biryukov and Kushilevitz, and Borst, Preneel, and Vandewalle. These analyses may give you several methodologies for analyzing these variants, and RC5, as it is securely parameterized. By the way - excellent job on preparing a documented cryptanalysis that I hope sparks interest amongst fellow cryptography enthusiasts. I made it a "sticky", and look forward to further additions. Cheers.
Back to top
View user's profile Send private message Visit poster's website
St_Anger
Just Arrived
Just Arrived


Joined: 16 Apr 2005
Posts: 0
Location: UK

Offline

PostPosted: Sun May 29, 2005 5:24 pm    Post subject: Reply with quote

wow, all that looks pretty confusing. I have also been interested in all areas of cryptography, especially cryptanalysis. Is all of this difficult to learn? And do you have to be good at maths?
Back to top
View user's profile Send private message
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Sun May 29, 2005 7:13 pm    Post subject: Reply with quote

St_Anger wrote:
And do you have to be good at maths?


You just need to be interested Wink

Cheers,
Sarad.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
mxb
Trusted SF Member
Trusted SF Member


Joined: 30 Mar 2004
Posts: 6


Offline

PostPosted: Mon May 30, 2005 12:42 am    Post subject: Reply with quote

St_Anger wrote:
wow, all that looks pretty confusing. I have also been interested in all areas of cryptography, especially cryptanalysis. Is all of this difficult to learn? And do you have to be good at maths?


Well, actually I don't think it is that confusing. I'm not sure if others will agree with me though as I was the one who wrote it. Very Happy

I'm glad that you are interested in cryptography and cryptanalysis as there is always interesting work that can be done. As for answering whether it is difficult to learn depends on your background.

I got to where I am now, which is around the same point that I was when I wrote that post, by self learning. I too have an interest in cryptography and cryptanalysis. I got into cryptography through reading about how it was used throughout history, then progressing onto modern day cryptography which revolves around mathematics and computers. I went out and bought half a dozen or so cryptography books, after reading recommendations on various places around the net. I also self taught myself most of the necessary mathematics, but you may already know some of it through other means such as university. A large part of that post is also C code for analysis programs that I wrote to break the cipher. I already knew C from previous programming experience, but other methods exist if you do not know a programming language.

I don't think you can 'learn' to do cryptanalysis. This is one of the reasons I wrote the original post, to explain what I was doing and why. I found the self-study course on cryptanalysis on the net, and approached it as a series of independent assignments. I sat down with the cipher and just tried to understand it. Once you understand the cipher then you can eventually see why the weakened version in the course is weaker than the full version. You can see the differences and the effects that they have upon the security. Once you finally understand this you can go and poke these differences to observe their effects.

In this case it was actually rather simple. In the weakened cipher the rotations are removed. This means that the only operation on the plaintext is XOR. Therefore modification of the lower bits does not effect the upper bits, they are largely independent. I tried to explain this in my post, and how I followed through this thought into a full break.

In conclusion I would be hesitant to say you have to be good at maths, but an analytical train of thought is definitely an advantage. Like datah has mentioned, enthusiasm is probably the most important thing you could possess. However, I am glad you found it interesting, and feel free to post any other queries you may have. I wish you the best of luck with your adventures into cryptography, and don't feel nervous about posting any questions you have. There are a large number of very talented people on this forum, and they will assist you along the way.

Cheers,
Martin
Back to top
View user's profile Send private message
sasha1
Just Arrived
Just Arrived


Joined: 03 Mar 2006
Posts: 0
Location: Belgrade

Offline

PostPosted: Fri Mar 03, 2006 1:58 pm    Post subject: Reply with quote

Martin, your RC5 without rotations cryptanalysis is very instructive and wise.
I also took the Schneiers autotutorial journey, and solved the RC5 without rotations
in the exactly same way as you did. I suppose that's what Schneier expected
from this assigment. I also solved RC5 with number of rotations equal to the
round number, and 4 round DES and 6 round DES. The most difficult was
RC5 with number of rotations equal to the round number (for me).

Have worked on any other excersise that B.S. proposed?

I wrote all my solutions in LaTeX, but, I wrote it in my language, so there's
no point posting it here. If I have time, I'll translate it (but my english is not
very good so I'm worried how it will turn out).

Bye,
Sasa
Back to top
View user's profile Send private message
sasha1
Just Arrived
Just Arrived


Joined: 03 Mar 2006
Posts: 0
Location: Belgrade

Offline

PostPosted: Tue Apr 04, 2006 9:49 am    Post subject: Reply with quote

OK, I translated my paper concerning Bruce Schneiers autotutorial problems.
You can see it at http://alas.matf.bg.ac.yu/~mr98224
Comments are welcome.

Thank you
Sasha
Back to top
View user's profile Send private message
granite.crow
Just Arrived
Just Arrived


Joined: 24 May 2006
Posts: 0


Offline

PostPosted: Wed May 24, 2006 5:40 pm    Post subject: Reply with quote

Thanks for some code pointing in the right direction.

Last edited by granite.crow on Thu May 25, 2006 7:45 pm; edited 1 time in total
Back to top
View user's profile Send private message
mxb
Trusted SF Member
Trusted SF Member


Joined: 30 Mar 2004
Posts: 6


Offline

PostPosted: Thu May 25, 2006 10:14 am    Post subject: Reply with quote

granite.crow wrote:
I am still learning but I guess I have a few questions (if someone doesn't mind answering them).

So i was attempting the same sort of thing.
I kept my plaintext as 00000000000000
and the key started at all 0, and then i walked a one from right to left to see how that effected the ciphertext.

My output is very close but not the same as you show in rc5-bitsweep.c.

<data removed>

I broke it up by which word was being flipped. (easier on my eyes). Do you see how i have pockets, specifically word1 and word3 where no change is induced. I can post the code as well, i'm just confused why my output is so different.
Thanks.


Hi granite.cow, welcome to SFDC!

I'm glad you are interested in cryptography, there are a number of people here who are extremely talented in this area. Don't worry about your still-learning status, the majority of us are Smile . Remember that there is a lot of information available through past topics, so search before asking a question as it may have already been asked.

Indeed it does seem like there is a small problem with your code somewhere. Without you showing us the code we cannot really help you. As the code may be quite big I would recommend putting it on a web server somewhere and posting a link, rather than making this thread too long with large chunks of code.

I'm sure once you do this, someone will take a look and see if there are any problems.

Cheers,
Martin
Back to top
View user's profile Send private message
Elderan
Just Arrived
Just Arrived


Joined: 08 Jun 2007
Posts: 0


Offline

PostPosted: Sat Jun 09, 2007 6:38 pm    Post subject: Reply with quote

Hi,
nice tutorial, but I think your cryptanalysis is wrong (resp. your rc5-crack works wrong).
The key-collisions which where found works just for the plaintext 00 00 00 [...]

Example:
Plaintext: 715c761f 2d94622d
Key1: 18A5FA2C 1097180A 28AE9651 0x892CDF4B
Key2: CCB62876 197C3880 09D0AFA1 0CF84A99

Cipher1: 34a47fc7 ec5fb104
Cipher2: f831c2c7 98a6c618

Decipher: b246d553 cba1b47d


Key1 is the "pseudo random key" which you try to break. Key2 is the first collision of your rc5-crack program.

Cipher1 is the cipher of the plaintext with Key1 and Cipher2 is the cipher of the plaintext with Key2.
Decipher ist the decipher of the cipher1 but with Key2.

As you can see, you can't use the key-collision for decrypting of any cipherblock, it works just for 00 00 00 [...] and maybe for some other plaintexts/ciphertexts, but you can't encrypt a message with this key-collision.


And none of the found collision works.

Here a little bit code to test a collision:
Code:

rc5-crack.c
[The RC5-Algorithm]

//Returns:
    //1: Key-collision can be used
    //0: Key-collision cannot be used
int CheckCollision(WORD *Key[4], WORD *Collision[4]) {
    srand( time(NULL) );   
   
    WORD pt[2];
    WORD ctKey[2]; //Cipher1
    WORD ctColl[2]; //Cipher2
    WORD decipher[2];
   
    int i=0;
   
    // Run 100 000 tests
    for(i=0;i<100000;i++)
    {
        //Random input
        pt[0] = rand()<<16 | rand();
        pt[1] = rand()<<16 | rand();
       
        //Orginal key
        RC5_SETUP(Key);
        RC5_ENCRYPT(pt,ctKey);
       
        //The key-collision
        RC5_SETUP(Collision);
        RC5_ENCRYPT(pt,ctColl);
       

        RC5_DECRYPT(ctKey, decipher);
       
        //Are cipher from org. key and cipher from collision are different?
        if(ctKey[0] != ctColl[0] || ctKey[1] != ctColl[1])
        {
            //Some debug values
            /*printf("Wrong encryption detected\n");
            printf("Plaintext: %.8x %.8x\n", pt[0], pt[1]);
            printf("Cipher (with org. key): %.8x %.8x\n", ctKey[0], ctKey[1]);
            printf("Cipher (with collision): %.8x %.8x\n", ctColl[0], ctColl[1]);
            printf("Decipher (org. cipher with collision): %.8x %.8x\n", decipher[0], decipher[1]);
          */
            return 0; //Ciphers are differen
        }               
       
    }
    //Collision fits the test, return 0
    return 1;   
}

int main()  {
  //Old Code [...]


 printf("Results:\n");
   for (ia=0; ia<stage8count; ia++) {
      key[0]=stage8[ia][0];
      key[1]=stage8[ia][1];
      key[2]=stage8[ia][2];
      key[3]=stage8[ia][3];
      RC5_SETUP(key);
      RC5_ENCRYPT(pt,ct);
     
      //Can i use 'key' (collision) instead of 'setkey' (the orginal key)
      if(CheckCollision(setkey, key) == 1)
      {       
        printf("    Key: %.8lX%.8lX%.8lX%.8lX -> ",key[0],key[1],key[2],key[3]);
        printf("ciphertext: %.8lX%.8lX\n",ct[0],ct[1]);
      }     
   }
     
   return(0);
}


When you now run the rc5-crack programm, no result would be returned, because the orginal key (or a compatible one) wasn't found.


(Please check my result again, maybe there is somewhere a mistake in CheckCollsion())
Back to top
View user's profile Send private message
mxb
Trusted SF Member
Trusted SF Member


Joined: 30 Mar 2004
Posts: 6


Offline

PostPosted: Mon Jun 11, 2007 6:52 pm    Post subject: Reply with quote

Hi Elderan, welcome to Security Forums.


Thank you for your comments. As this was done a long time ago I will have to refresh my memory.

I'll dig out my notes and take a look to see if it is incorrect.

Thanks,
Martin
Back to top
View user's profile Send private message
Display posts from previous:   

Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security All times are GMT + 2 Hours
Page 1 of 1


 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Community Area

Log in | Register