Educational cryptanalysis competition (small prize)
-----BEGIN PGP SIGNED MESSAGE----- Educational Cryptanalysis Competition (opened 17 July 1996) ===================================== Cypherpunks teach. Here's your chance. I have a piece of code I wrote ages ago, before reading Schneier. Despite identifying these points as weaknesses I still cannot break it. weak keys rapid collapse in the case of chosen text attack reduced-round versions have a correlation attack Obviously my crytanalysis needs some serious help. The aim of this competition is: to show how to find AND EXPLOIT weaknesses in this cypher. Answers resembling "That's junk - use XXXXX." score zero. Well-prepared comprehensive answers could score highly. - - Entries will be judged on educational grounds as well as on raw results. - - All entries are placed by the entrant in the public domain, and there may be a compilation of good answers come out of this. (With entrants' names except where they state a prefernce for anonymity. ) - - Entries by teams are allowed. - - The number of entries is unlimited. - - The closing date is 30 Sept 1996. - - The judge is Peter Allan. (me) - - There is one prize (a box of chocolate coffee beans). A full pair of programs using this code can be collected from my mail filter. echo rlprm_2.0 | mail -s send_goodies peter.allan@aeat.co.uk Peter Allan peter.allan@aeat.co.uk #define RPT 15 #define CRYPT_DEPTH 4 /**********************************/ mkkey(origpass, key) /*** **** The pass (a text string) is used to produce **** a key. Chars used as int. Details in docs. **** 200000 passwords all gave different keys in my test. ***/ char origpass[9]; unsigned char key[8]; { char clearpass[9]; int i, j, k, l, m, ten; /*** make the key from the clearpass ***/ /*** unsigned char[8] from char[9] ***/ ten = FALSE; k = l = m = 0; strcpy(clearpass, origpass); for (i = 0; i < 8; i++) { if (clearpass[i] == '\n') ten = TRUE; if (ten) clearpass[i] = '\0'; } clearpass[8] = '\0'; for (i = 0; i < 8; i++) key[i] = (unsigned char) i; for (j = 1; j < 256; j++) { for (i = 0; i < 8; i++) key[i] = key[i] + clearpass[i] + j; /* swap bytes */ k = key[j % 8] % 8; l = key[k] % 8; m = key[k]; key[k] = key[l]; key[l] = m; /** this loop is redundant if chars are 8 bits *** and for all I know they are everywhere **/ for (i = 0; i < 8; i++) key[i] = key[i] % 256; m = m % 8; key[m] = 256 - key[m]; } /**** for (i = 0; i < 8; i++) printf("%d ", key[i]); puts(" "); ****/ } /**********************************/ sym_encrypt(abpos, key, authbuf, cipherbuf) int abpos; unsigned char key[8]; unsigned char authbuf[ABLEN]; unsigned char cipherbuf[MESSLEN]; { int i, j, k, ptr1, ptr2, rpt; int ka1, ka2, kk; unsigned char smoke[CRYPT_DEPTH][8]; unsigned char tmp; /*** **** From the key, make a set of keys to **** be used in order. ***/ for (j = 0; j < 8; j++) smoke[0][j] = key[j]; for (i = 1; i < CRYPT_DEPTH; i++) { for (j = 0; j < 8; j++) smoke[i][j] = smoke[i - 1][j]; for (j = 0; j < 8; j++) { if (j % 2) { smoke[i][j] = (smoke[i][j]) * 3; } else { smoke[i][j] = ((smoke[i][j]) * 3) / 4; } } } #ifndef NOCRYPT /*** **** see the tech waffle file for details ***/ for (rpt = RPT; rpt; rpt--) { if (cl_debug) printf("encryption repeat count is %d \n", rpt); for (i = 0; i < CRYPT_DEPTH; i++) { /**swap driven by values **/ for (k = 0; k < abpos - 1; k += 2) { kk = authbuf[k] ^ authbuf[k + 1]; ka1 = kk / 16; ka2 = kk % 16; kk = ka1 ^ ka2; if ((kk == 1) || (kk == 2) || (kk == 4) || (kk == 8) || (kk == 14) || (kk == 13) || (kk == 11) || (kk == 7)) { kk = authbuf[k]; authbuf[k] = authbuf[k + 1]; authbuf[k + 1] = kk; } } /** xor with key **/ for (k = 0; k < abpos; k++) authbuf[k] ^= (key[k % 8]); /**rotation **/ kk = authbuf[abpos - 1] / 32; ka1 = 0; for (k = 0; k < abpos; k++) { ka2 = authbuf[k] / 32; authbuf[k] = (authbuf[k] * 8) + ka1; ka1 = ka2; } authbuf[0] += kk; /**swap driven by key **/ if (cl_debug) printf(" depth is %d \n", i); for (j = 0; j < 8; j = j + 2) { ptr1 = smoke[i][j] % abpos; ptr2 = smoke[i][j + 1] % abpos; tmp = authbuf[ptr1]; authbuf[ptr1] = authbuf[ptr2]; authbuf[ptr2] = tmp; } } } #endif /*** Now that it has been encrypted it should **** be stored as 'hexabetical' [A-P]. ***/ for (i = 0; i < abpos; i++) { cipherbuf[i * 2] = (authbuf[i] % 16) + 'A'; cipherbuf[i * 2 + 1] = (authbuf[i] / 16) + 'A'; } cipherbuf[abpos * 2] = '\0'; } /********************************/ sym_decrypt(abpos, key, authbuf, cipherbuf) int abpos; unsigned char key[8]; unsigned char authbuf[ABLEN]; unsigned char cipherbuf[MESSLEN]; { int i, j, k, ptr1, ptr2, rpt; int ka1, ka2, kk; unsigned char smoke[CRYPT_DEPTH][8]; unsigned char tmp; for (i = 0; cipherbuf[i]; i = i + 2) { cipherbuf[i] = cipherbuf[i] - 'A'; cipherbuf[i + 1] = cipherbuf[i + 1] - 'A'; authbuf[i / 2] = cipherbuf[i] + cipherbuf[i + 1] * 16; } /*** **** From the key, make a set of keys to **** be used in order. ***/ for (j = 0; j < 8; j++) smoke[0][j] = key[j]; for (i = 1; i < CRYPT_DEPTH; i++) { for (j = 0; j < 8; j++) smoke[i][j] = smoke[i - 1][j]; for (j = 0; j < 8; j++) { if (j % 2) { smoke[i][j] = smoke[i][j] * 3; } else { smoke[i][j] = (smoke[i][j] * 3) / 4; } } } #ifndef NOCRYPT /*** **** repeat suitable number of times: **** first swap bytes in the authbuf **** then cycle bits round to prevent some swaps undoing others ***/ if (abpos == 0) return RUBBISH; /** zerodivide detected-avoided **/ for (rpt = RPT; rpt; rpt--) { /* printf("encryption repeat count is %d \n", rpt); */ for (i = CRYPT_DEPTH - 1; i > -1; i--) { for (j = 6; j > -1; j = j - 2) { /*** key-driven swap ***/ ptr1 = smoke[i][j] % abpos; ptr2 = smoke[i][j + 1] % abpos; tmp = authbuf[ptr1]; authbuf[ptr1] = authbuf[ptr2]; authbuf[ptr2] = tmp; } /**rotation **/ kk = authbuf[0] % 8; ka1 = 0; for (k = abpos - 1; k >= 0; k--) { ka2 = authbuf[k] % 8; authbuf[k] = (authbuf[k] / 8) + ka1; ka1 = ka2 * 32; } authbuf[abpos - 1] += (kk * 32); /** xor with key **/ for (k = 0; k < abpos; k++) authbuf[k] ^= (key[k % 8]); /*** value-driven swap ***/ for (k = 0; k < abpos - 1; k += 2) { kk = authbuf[k] ^ authbuf[k + 1]; ka1 = kk / 16; ka2 = kk % 16; kk = ka1 ^ ka2; if ((kk == 1) || (kk == 2) || (kk == 4) || (kk == 8) || (kk == 14) || (kk == 13) || (kk == 11) || (kk == 7)) { kk = authbuf[k]; authbuf[k] = authbuf[k + 1]; authbuf[k + 1] = kk; } } } } #endif } /**********************/ -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQCVAgUBMezfIB98EdWB2LS9AQFbwgP+Oq8zBlI5d1comIQ5S2+ysnSDLAN5W/L2 UgQyrYZ/Cchn9I8CEFn9UDevmInpABSL8yNQWUHrb4cvWxiTGNnFz54gicaPT7Ki qVETDC5o7nxWOT8qhWmGNTApJC8RBjEkY+90HyYKf2sLEd8hkGLwOGSAF/YWxqkY TKqYWVNKCjA= =3qEU -----END PGP SIGNATURE-----
In article <9607171243.AA26209@clare.risley.aeat.co.uk>, Peter M Allan <peter.allan@aeat.co.uk> wrote:
Obviously my crytanalysis needs some serious help. Answers resembling "That's junk - use XXXXX." score zero.
If you have a n-byte plaintext P[0..n-1], define f(P) as f(P) = P[0] ^ P[1] ^ P[2] ^ ... ^ P[n-1]. Now encrypt P[0..n-1] under your cipher to obtain C[0..n-1]. (Ignore the final reversible unkeyed transformation to hex, which has no impact on security.) My observation is that f(C) = rotate_byte(f(P), rot_constant) ^ key_dep_byte no matter how many rounds you use. Here rot_constant is a key-independent constant, and key_dep_byte depends only on the key (and not on the plaintext or anything). Therefore, (for example) knowing C[0..n-1] reveals f(P) when one known-plaintext is available. I'll leave it as an exercise to discover why and derive the values of the two constants. Hint: it's enough to prove it for one round. I think that I don't need to spend any more time on it (though I am sure there are many more weaknesses lurking in the code). In all fairness I can reasonably conclude that That's junk. Use triple DES. Take care, -- Dave Wagner
participants (2)
-
daw＠cs.berkeley.edu -
peter.allan＠aeat.co.uk