Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
Cipher Block Chaining Mode Challenge 2
Topic Started: Oct 11 2005, 10:08 PM (898 Views)
insecure
NSA worthy
[ *  *  *  *  *  * ]
IBC-02 is just like IBC-01 except for the following changes:

1) I now read the bytes eight at a time instead of four at a time. The eight bytes are split into two fours, which form the left and right halves of the Feistel network. This means that up to seven bytes at the end of the plaintext will remain unencrypted. (It might provide a tiny, almost insignificant, hook into the cipher, but far more importantly it keeps the source code simple!)
2) the 16-bit masking has been removed.
3) the number of rounds is no longer configurable via the command line.

The arithmetic weaknesses of the algorithm remain. (These will probably be removed in IBC-03, but we'll wait and see, shall we?)

The C source code for IBC-02 will be posted in the next article.

Here is the challenge ciphertext, expressed as a hex dump. If there is sufficient demand, I will supply source for a program to read a hex dump (in the following format) and write the corresponding binary file. (The plaintext is - more or less - English text.)

Code:
 

76 72 AF CA 5A 0E 6D 7E 02 1A 62 41 1B 19 A4 ED
6B FB 07 5B A6 45 0E 6F 0E 16 17 DB A7 93 D2 F5
60 36 61 C5 30 A1 53 C9 04 99 AA A3 4E 9F 56 5A
77 F8 00 65 0B 8A 76 B4 04 90 2D 3E 19 C4 B6 6D
60 F5 05 22 95 68 F0 6F 0E 94 2A FA DD 0B CE 32
61 FA EA 82 3E C4 59 FA 07 88 C9 2B AE 12 07 C8
27 C4 DD 31 77 2D 40 A1 41 AD 2F AD 82 81 BF B2
2E 43 3F AE 89 34 24 99 43 A6 4B C4 70 50 D1 82
64 D5 22 63 48 D4 73 94 26 BA 08 64 03 EF 84 E9
0F 9A 58 C4 80 B1 D2 42 60 F1 C8 7F 11 77 13 5F
40 70 45 F9 8A 83 A2 60 21 1E D5 4F 64 CD 98 76
44 B0 53 F5 1D A5 8D 0C 2B 42 C4 E9 BA EA 9C 8F
43 E2 37 28 5E 72 A5 73 36 41 62 90 D6 61 A3 F1
16 09 B5 58 1A CC 8C 12 64 68 60 BA 61 FF 0A FB
07 81 00 17 BD 85 D3 6A 6A E3 07 4A D5 22 12 F1
1E 86 26 15 49 51 6A CA 7B F5 DC 4E 6B 4A 0B 89
0E 87 FA 8C 66 49 ED F1 63 E8 E8 75 85 54 5E C2
0B 0D 3D 2C 27 DB 02 3F 6E 60 08 06 2C C6 0A F0
07 04 6B 36 F9 A0 EB 61 69 24 64 AB 5C 68 40 12
06 0F D8 CA 07 E9 A4 82 63 2F 62 E1 FB 94 BE 5C
0A 41 4D C9 B9 C9 01 C9 67 20 2C B6 79 F3 AD 8A
47 41 FC F9 A8 62 74 A3 28 27 24 1D F1 03 D4 C7
5C 54 D1 6B 47 74 A4 1C 3F 31 B5 85 56 40 E2 AF
4F 5D 2E 54 C3 C4 52 FF 3D 2F FA FF CD DA 38 BE
1D 4D BD CA CC A1 91 98 71 21 04 3C 84 F8 BC 7F
1C 00 6B 81 7C 11 95 57 6E 73 9B 8E 72 8B 00 6E
0C 11 00 30 59 81 5C 97 62 31 EE 23 71 09 B7 C2
06 44 05 2E 3D 70 BF 2B 69 29 05 E0 95 CB CA 0A
19 48 B2 6B F5 FF 99 B7 78 68 53 3D 2C AD 28 F1
11 0E 68 C6 44 89 AF B5 70 7A ED 91 59 CD 72 72
50 0E EC DB 52 1D D1 35 31 6C 4E A0 26 6E BB 2A
42 4C A5 2E 4D 17 07 64 2A AD 51 F1 60 67 0C 5D
53 0D 46 B7 1E 89 23 7A 36 AC 37 8F 96 B6 6C C4
44 4C C8 2E EF 20 EC 8C 25 6C A7 91 38 3E B3 CF
4C DE F5 60 08 57 74 43 6C B8 82 04 3D A8 B4 8A
09 98 78 7A 9E 32 C1 B1 03 F5 BD EC 7A CE CA 59
6D D5 3F E0 F9 C1 33 99 1E B5 2B 49 7E 21 C5 0D
6A DC 6D 0D 09 87 96 18 0C FC 6E F9 71 7C 20 71
6D 8F 2D DB FC A9 40 D0 19 E7 03 5B 9C 03 C9 8A
39 8A D0 0F A8 57 24 B6 55 EB 12 59 ED F9 1C 06
30 4D DE 42 F0 97 91 7A 55 6D 77 61 B9 0E 7D 5B
39 67 8F F7 90 68 F4 A7 4D 06 3D 53 03 E1 7F E0
6D 76 DB F0 87 6C 83 D1 41 56 3A 93 66 AF 81 B6
29 33 EE 6D 86 C2 0F C1 09 5D 21 2D 22 AA 5B 4A
61 2E 29 FC CC CC 94 9D 04 E4 65 A8 B6 28 46 43
24 87 5A 74 C1 1B 61 03 04 E6 8C 58 F9 79 20 43
70 46 70 53 E2 D5 73 1D 11 2F FA BB 81 03 C3 B7
78 C1 61 E0 4A 3B D7 1D 58 31 0F 10 96 47 4B 20
52 43 98 C0 6B 8B A6 B5 3E 3A 27 08 EA F4 AC 96
51 5F 5F FD 84 4C B5 B4 25 3E 26 F7 04 EE 72 8A
42 1E EC 13 2C 3C E0 91 62 EA 92 F8 50 4C 13 C2
07 4A CC 80 8D 9C C9 07 27 25 EE 31 5C 31 07 E6
53 85 E2 DE 2E C9 02 1B 73 F5 E3 AC 4C 53 E7 51
01 90 6F 20 A2 4E 46 D2 6E FE B7 3C EA 4E 26 A2
03 91 38 54 12 5A 82 9F 23 F6 49 16 E7 8F F1 E9
5A D6 61 08 4A 11 16 A5 37 34 7F F6 09 88 85 4C
17 40 6B FF 19 B1 54 87 62 25 40 6E 74 23 98 11
42 85 5F 0E 50 CA E3 09 62 F7 5F 28 6B 4E 52 24
4E 57 CC 20 23 34 06 27 6E 25 1B 13 6B 8D 26 65
4E 0B BF 57 23 CA 0D 76 39 63 2E 9A 0B 1E 1A AB
19 04 B0 92 2E D1 84 67 7C 20 C1 D2 8F 77 99 44
19 00 E4 02 A2 9A 2A 3E 39 72 CD D6 87 46 8E 4B
58 06 E1 2A 49 E2 02 3B 78 68 62 16 93 A7 81 8E
19 0E 96 C0 A1 20 7D A3 7C 2E B0 A4 0B A5 11 85
08 D9 4B EC 02 92 9F DD 7B F9 48 5B 26 A6 6E 3A
1E 9D 9E C1 B7 42 09 4C 7A F4 62 65 5F 65 F9 C1
1F 00 2A A9 5D D3 C3 B1 7A 60 E2 34 F0 16 A4 C4
0F 13 14 51 77 4F A5 DA 7A FE 2A F2 CD 1F DD 0F
2E 16 A7 47 89 3B C9 9D 13 B6 05 89 B2 4F DB 9C
33 05 1C 9D 82 75 48 76 13 37 78 DF A7 99 83 29
21 17 D2 64 14 55 7D 4F 01 2A 4F 9A B4 C7 F9 AC
2D 20 CE 6D 30 4D D0 08 0D 4F 2F AC DA C4 CB 5B
64 3C 21 D4 AB 1A 54 E9 01 1C D8 88 5A 26 52 B7
62 79 3A CC 27 EC 42 00 42 D6 CA 8F 0F F9 A4 20
2A B7 68 4D 67 5C 0C E5 4F C5 B2 22 B7 51 AE 4A
2A B7 07 61 8B EE 71 51 20 C7 F0 70 03 3D 81 D1
49 A2 40 E9 AA B0 0E 8A 3D D1 02 16 BD D4 E4 DE
54 B6 6A AB 09 6F 2A E8 74 C1 FE 2C FD 7D 54 37
54 B2 40 D0 00 26 0E 4B 26 C2 3F 8E 5B D7 12 9E
2C A3 1D A7 6F 37 A7 0E 58 CA 23 EB A4 78 76 10
1E 65 DF 1E 25 92 9C 76 7F 0B 08 7F 79 F9 DE F4
5F 6A 1F 55 7A 18 D9 BC 36 04 4B 8C BA B2 19 B4
5E 61 F0 FC 2B 10 26 D9 7E 02 76 FD B3 8C 9E 03
0C 08 F0 BB 9F 9F 0A AF 7F 6D 64 63 8E 6A 69 AC
1E C1 B7 1A 46 67 81 60 6A A9 BA 0B 7D 97 02 43
13 89 3B 8D 4D 3F E2 7F 33 EA 80 60 2D 09 DF C7
47 03 79 5F FC 6D 8A 22 21 65 1C C3 15 58 03 96
58 6F 63 D2 8D D5 11 45 78 2A B7 82 59 8C B8 AA
19 44 2B 67 75 56 00 80 70 30 35 46 23 6B 99 AF
03 10 AB 8A C1 F7 36 BE 23 58 E2 58 33 D9 FD C8
04 6B C2 6E 4E 19 E8 29 24 1B 48 B7 34 08 8D 81
2E EC A9 B7 7C 5F 1B 09 4D 89 F3 7F F9 8A DD 48
39 E1 C2 9D D0 03 56 30 4B 95 CB DE 63 58 B1 59
2D B5 64 0F E6 3A DB B7 4F 5A 45 05 75 45 29 34
3C 7F CB 3B C8 3B 1A F2 1C 13 02 A6 30 73 F3 E2
68 FB 34 61 6E D3 50 4A 48 8F 02 9D 22 61 CA 41
68 EA E9 EB 73 4A E5 8C 1B CA 9A A8 53 65 EF 11
75 BE 40 DB 1F 91 AB 25 6F 77 74 68 2E 0A 0A
Offline Profile Quote Post Goto Top
 
insecure
NSA worthy
[ *  *  *  *  *  * ]
Here is the IBC-02 source code:

Code:
 

/* Insecure Block Cipher - Version 2 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FEISTEL_ROUNDS 17

unsigned long PerformCrypto(unsigned long input, unsigned long key)
{
 return ((input ^ key) * 0x12345678UL + 0x9ABCDEF0UL) & 0xFFFFFFFF; /* keep it down to 32 bits */
}

/* Run a Feistel network on two unsigned integer values, using an unsigned integer key */
void PerformFeistel(unsigned long *Left,
                   unsigned long *Right,
                   size_t rounds,
                   unsigned long key)
{
 unsigned long t = 0;
 size_t i;
 for(i = 0; i < rounds; i++)
 {
   *Left ^= PerformCrypto(*Right, key);
   if(i < rounds - 1)
   {
     t = *Left; *Left = *Right; *Right = t;
   }
 }
}

unsigned long hash(const char *s)
{
 unsigned long h = 0;
 while(*s)
 {
   h *= 33;
   h += *s++;
 }

 return h & 0xFFFFFFFFUL; /* keep it to 32 bits */
}

int ibc02(const char *infilename, const char *outfilename, unsigned long key, unsigned long iv, int decrypt)
{
 int rc = 0;

 unsigned char Buffer[sizeof(unsigned long) * 2] = {0};
 unsigned char Ciphertext[sizeof Buffer / sizeof Buffer[0]] = {0};
 unsigned long Left   = 0;
 unsigned long Right  = 0;

 unsigned char Prev[sizeof Buffer / sizeof Buffer[0]] = {0};

 size_t Bytes = 0;

 FILE *in = fopen(infilename, "rb");
 if(in != NULL)
 {
   FILE *out = fopen(outfilename, "wb");
   if(out != NULL)
   {
     /* initialise the leftmost buffer */
     memcpy(Prev, &iv, sizeof iv);
     iv = ~iv;
     memcpy(Prev + sizeof iv, &iv, sizeof iv);

     while((Bytes = fread(Buffer, 1, sizeof Buffer, in)) == sizeof Buffer)
     {
       memcpy(Ciphertext, Buffer, sizeof Ciphertext);

       if(!decrypt)
       {
         size_t i = 0;
         for(i = 0; i < sizeof Prev; i++)
         {
           Buffer[i] ^= Prev[i];
         }
       }
       memcpy(&Right, Buffer, sizeof Right);
       memcpy(&Left, Buffer + sizeof Right, sizeof Left);
       /* Run the Feistel network */
       PerformFeistel(&Left, &Right, FEISTEL_ROUNDS, key);
       memcpy(Buffer, &Right, sizeof Right);
       memcpy(Buffer + sizeof Right, &Left, sizeof Left);
       if(decrypt)
       {
         size_t i = 0;
         for(i = 0; i < sizeof Prev; i++)
         {
           Buffer[i] ^= Prev[i];
         }
       }
       fwrite(Buffer, 1, sizeof Buffer, out);
       if(decrypt)
       {
         memcpy(Prev, Ciphertext, sizeof Prev);
       }
       else
       {
         memcpy(Prev, Buffer, sizeof Prev);
       }
     }
     if(Bytes > 0)
     {
       fwrite(Buffer, 1, Bytes, out);
     }
     if(ferror(out))
     {
       rc = 4; /* output error */
     }

     fclose(out);
   }
   else
   {
     rc = 3; /* couldn't open output file */
   }

   if(ferror(in))
   {
     rc = 2; /* input error */
   }
   fclose(in);
 }
 else
 {
   rc = 1; /* couldn't open input file */
 }
 return rc;
}

int main(int argc, char **argv)
{
 int rc = 0;

 unsigned long Key        = 0;
 unsigned long InitVector = 0;
 int           Decrypt    = 0;

 /* args are:
  * [0] - program
  * [1] - plaintext filename
  * [2] - ciphertext filename
  * [3] - keyphrase (will be hashed)
  * [4] - initialisation vector phrase (will be hashed)
  * [5] - optional -d (for decrypt)
  */

 /* Check that there are enough inputs */
 if(argc < 5)
 {
   puts("Insecure Block Cipher v2.0 - inputs are:");
   puts("inputfilename outputfilename keyphrase vectorphrase [-d]");
   puts("-d indicates that a decryption process is required.");
 }
 else
 {
   /* Convert inputs to unsigned at-least-32-bit integers */
   Key        = hash(argv[3]);
   InitVector = hash(argv[4]);

   if(argc > 5)
   {
     if(strcmp(argv[5], "-d") == 0)
     {
       Decrypt = 1;
     }
   }
   rc = ibc02(argv[1], argv[2], Key, InitVector, Decrypt);
   fprintf(stderr, "Result of %scryption operation (0 = success): %d\n", Decrypt ? "de" : "en", rc);
 }
 return 0;
}



Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
Is the IV the same as before, will you still give us the IV ?
Offline Profile Quote Post Goto Top
 
insecure
NSA worthy
[ *  *  *  *  *  * ]
Ah, good spot, sirrah!

The IV is: MorePepper

Sorry about that.
Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
Well, that wasn't too bad. I cracked it, and umm.. that ain't no fib. ;) The most amazing thing is that I cracked it with only 442 calls to icb02 and had a total of 22950 calls to PerformCrypto. I will wait a little while to post my program since other people would probably like to make some headway.

Basically, the real vulnerability I pointed out in icb01 is still a vulnerability in icb02, and it isn't the key length. First of all, the effective key length in icb02 is 29 bits, because everything still shifts over 3 bits ot the left, so the left 3 bits in the key are ignored.

The big flaw is that the bits in the key basically correspond to bits in the ciphertext. If you know N bits of the key, you can compute N+3 bits of the ciphertext. You can knock down bits if you proceed from right to left. Let me leave it at that for the moment, if you look at how I cracked icb01, maybe you can get an idea of how to crack icb02.
Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
I am posting a framework C program to help people try to crack this challenge. The program as it stands does a 29-bit brute-force attack on the cipher, and can solve it after several minutes. As insecure said before, anybody can brute force a 32-bit key, so this isn't meant as a crack of itself, other than showing that the upper 3 bits of the key are unused. The point is to start from this and try to add shortcuts for determining the key.

The last parameter of the ibc02 function indicates how many characters of each 32-bit word to examine for valid ascii. It starts on the right-hand side of the word, so if you pass a value of 1, it only looks at the right-most 8 bits. If you pass 2, it looks at the rightmost 16-bits, etc.

If you compare this program to the one I posted for icb01, you might get some idea of how to work on parts of the key.

Code:
 

/* Insecure Block Cipher - Version 2 cracker*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long num_perform_crypto;
long num_perform_ibc02;

#define FEISTEL_ROUNDS  17
unsigned long PerformCrypto(unsigned long input, unsigned long key)
{
   num_perform_crypto++;
return ((input ^ key) * 0x12345678UL + 0x9ABCDEF0UL)&0xffffffff; /* keep it down to 16 bits */
}

/* Run a Feistel network on two unsigned integer values, using an unsigned integer key */
void PerformFeistel(unsigned long *Left,
                  unsigned long *Right,
                  size_t rounds,
                  unsigned long key)
{
unsigned long t = 0;
size_t i;
for(i = 0; i < rounds; i++)
{
  *Left ^= PerformCrypto(*Right, key);
  if(i < rounds - 1)
  {
    t = *Left; *Left = *Right; *Right = t;
  }
}
}

// are either printable or tab, carriage return, or line feed
int is_good(unsigned long wordval, int bytes_to_check)
{
   int i, ch;
   for (i=0; i < bytes_to_check; i++)
   {
       ch = wordval & 0xff;
       if (ch & 0x80) return 0;
       if ((ch < 32) && (ch != 13) && (ch != 10) && (ch != 9)) return 0;
       wordval >>= 8;
   }
   return 1;
}

int ibc02(unsigned long *ctext, int ctext_len, unsigned long *ptext, unsigned long key, unsigned long iv, int bytes_to_check)
{
unsigned char Buffer[sizeof(unsigned long) * 2] = {0};
unsigned char Ciphertext[sizeof Buffer / sizeof Buffer[0]] = {0};
unsigned char Prev[sizeof Buffer / sizeof Buffer[0]] = {0};
unsigned long Left   = 0;
unsigned long Right  = 0;
int i, j;

num_perform_ibc02++;

memcpy(Prev, &iv, sizeof iv);
iv = ~iv;
memcpy(Prev + sizeof iv, &iv, sizeof iv);

for (i=0; i < ctext_len-2; i+=2)
{
    memcpy(Buffer, &ctext[i], 2 * (sizeof(long)));
    memcpy(Ciphertext, Buffer, sizeof(Ciphertext));
    memcpy(&Right, Buffer, sizeof Right);
    memcpy(&Left, Buffer + sizeof Right, sizeof Left);
    /* Run the Feistel network */
    PerformFeistel(&Left, &Right, FEISTEL_ROUNDS, key);
    memcpy(Buffer, &Right, sizeof Right);
    memcpy(Buffer + sizeof Right, &Left, sizeof Left);

    for(j = 0; j < sizeof Prev; j++)
    {
       Buffer[j] ^= Prev[j];
    }

    memcpy(&Right, Buffer, sizeof Right);
    memcpy(&Left, Buffer + sizeof Right, sizeof Left);
// Make sure the decrypted word contains only ASCII
      if (!is_good(Right, bytes_to_check)) return 0;
      if (!is_good(Left, bytes_to_check)) return 0;

      memcpy(&ptext[i], Buffer, 8);
      memcpy(Prev, Ciphertext, sizeof Prev);
    }
   return 1;
}

#define MAX_WORDS 8192
unsigned long ctext[MAX_WORDS];
unsigned long ptext[MAX_WORDS];
int ctext_len;

int main(int argc, char **argv)
{
   int i;
   FILE *infile;

unsigned long InitVector = 0xf2d1c3f;
   unsigned long key;

   if (argc < 2)
   {
       printf("format is: %s ctext_file\n", argv[0]);
       exit(1);
   }
   if ((infile = fopen(argv[1], "r")) == NULL)
   {
       fprintf(stderr, "Couldn't open ctext\n");
       perror("fopen");
       exit(1);
   }

   // Load the ciphertext
   ctext_len = 0;
   while ((ctext_len < MAX_WORDS-1) && (fread(&ctext[ctext_len], 1, 8, infile) > 0)) ctext_len+=2;

   // Try all possible values for 29 bits of the key
   for (key=0; key <= 0x1fffffffUL; key++)
   {
       // Check to make sure all 4 bytes decrypt to ascii
       if (ibc02(ctext, ctext_len, ptext, key, InitVector, 4))
       {
           printf("Key = %08x\n", key);
           for (i=0; i < ctext_len-1; i++)
           {
              fwrite(&ptext[i], 1, 4, stdout);
           }
           printf("\n");
           break;
       }
   }
   printf("Called ibc02 %d times\n", num_perform_ibc02);
   printf("Called perform_crypto %d times\n", num_perform_crypto);
}

Offline Profile Quote Post Goto Top
 
insecure
NSA worthy
[ *  *  *  *  *  * ]
Clearly, then, we need to fix the leakage of key bits for IBC-03. It seems to me that it's time to address the encryption algorithm itself. At present, it is as follows:

Code:
 

unsigned long PerformCrypto(unsigned long input, unsigned long key)
{
 return ((input ^ key) * 0x12345678UL + 0x9ABCDEF0UL) & 0xFFFFFFFF; /* keep it down to 32 bits */
}


Here are those constants again, this time in binary:

00010010001101000101011001111000

10011010101111001101111011110000

It's true that these constants leave the bottom three bits of the result of the XOR unaffected by the operation. It seems to me that we should at least set the bottom bit of each. In fact, I'm tempted to use prime numbers.

2527302203 (96A3923B) is one possibility.

2678482747 (9FA6673B) is another.

Binary:

10010110101000111001001000111011
10011111101001100110011100111011

So this would give us:

Code:
 

unsigned long PerformCrypto(unsigned long input, unsigned long key)
{
 return ((input ^ key) * 0x96A3923BUL + 0x9FA6673BUL) & 0xFFFFFFFF; /* keep it down to 32 bits */
}


But I'm not sure whether this significantly increases security. Opinions welcomed.

Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
I believe that would stop the leakage of bits two ways. First, it keeps the lower 3 bits of the plaintext from showing through, which it does currently. Second, it keeps you from losing the left 3 bits of the key, so you use all the key.

That being said, it isn't really any more secure. I was able to crack the new one (with 0x96A3923BUL and 0x9FA6673BUL) using 528 calls to ibc02. The problem is that you can just try all 256 possibilities for the rightmost 8 bits of the key. They alone determine the rightmost 8 bits of the ciphertext. Once you have that, then you try all 256 combos for the next 8 bits, and so on.

Maybe in your feistel round you could swap bytes, but do it in a way that by the end of some number of rounds, each byte has been touched by all 8 bytes of the block. For example, just rotate the block one byte to the left after each round. That would make it considerable harder than it is right now.
Offline Profile Quote Post Goto Top
 
insecure
NSA worthy
[ *  *  *  *  *  * ]
One way to increase diffusion around the block might be to use, say, an 8x4 S-box. Rotation is another obvious possibility (in fact, the first non-trivial algorithm I developed All By Myself used a combination of rotation and an 8x8 box - but no Feistel network!, so it all had to be reversible.)

Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · Challenges · Next Topic »
Add Reply