|
Cipher Block Chaining Mode Challenge 2
|
|
Topic Started: Oct 11 2005, 10:08 PM (898 Views)
|
|
insecure
|
Oct 11 2005, 10:08 PM
Post #1
|
- Posts:
- 550
- Group:
- Trusted Member
- Member
- #10
- Joined:
- September 9, 2005
|
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
|
|
|
| |
|
insecure
|
Oct 11 2005, 10:10 PM
Post #2
|
- Posts:
- 550
- Group:
- Trusted Member
- Member
- #10
- Joined:
- September 9, 2005
|
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; }
|
|
|
| |
|
rot13
|
Oct 11 2005, 10:29 PM
Post #3
|
- Posts:
- 306
- Group:
- Trusted Member
- Member
- #14
- Joined:
- September 29, 2005
|
Is the IV the same as before, will you still give us the IV ?
|
|
|
| |
|
insecure
|
Oct 11 2005, 11:01 PM
Post #4
|
- Posts:
- 550
- Group:
- Trusted Member
- Member
- #10
- Joined:
- September 9, 2005
|
Ah, good spot, sirrah!
The IV is: MorePepper
Sorry about that.
|
|
|
| |
|
rot13
|
Oct 12 2005, 02:47 AM
Post #5
|
- Posts:
- 306
- Group:
- Trusted Member
- Member
- #14
- Joined:
- September 29, 2005
|
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.
|
|
|
| |
|
rot13
|
Oct 12 2005, 02:34 PM
Post #6
|
- Posts:
- 306
- Group:
- Trusted Member
- Member
- #14
- Joined:
- September 29, 2005
|
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); }
|
|
|
| |
|
insecure
|
Oct 12 2005, 09:54 PM
Post #7
|
- Posts:
- 550
- Group:
- Trusted Member
- Member
- #10
- Joined:
- September 9, 2005
|
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.
|
|
|
| |
|
rot13
|
Oct 12 2005, 10:16 PM
Post #8
|
- Posts:
- 306
- Group:
- Trusted Member
- Member
- #14
- Joined:
- September 29, 2005
|
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.
|
|
|
| |
|
insecure
|
Oct 12 2005, 10:20 PM
Post #9
|
- Posts:
- 550
- Group:
- Trusted Member
- Member
- #10
- Joined:
- September 9, 2005
|
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.)
|
|
|
| |
| 1 user reading this topic (1 Guest and 0 Anonymous)
|