//Differential Cryptanalysis of FEAL-4 //Uses a chosen-plaintext attack to fully recover the key //For use with tutorial at http://theamazingking.com/crypto-feal.php #include #include #define MAX_CHOSEN_PAIRS 10000 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) int winner = 0; int loser = 0; unsigned long subkey[6]; unsigned char rotl2(unsigned char a) {return ((a << 2) | (a >> 6));} unsigned long leftHalf(unsigned long long a) {return (a >> 32LL);} unsigned long rightHalf(unsigned long long a) {return a;} unsigned char sepByte(unsigned long a, unsigned char index) {return a >> (8 * index);} unsigned long combineBytes(unsigned char b3, unsigned char b2, unsigned char b1, unsigned char b0) { return b3 << 24L | (b2 << 16L) | (b1 << 8L) | b0; } unsigned long long combineHalves(unsigned long leftHalf, unsigned long rightHalf) { return (((unsigned long long)(leftHalf)) << 32LL) | (((unsigned long long)(rightHalf)) & 0xFFFFFFFFLL); } unsigned char gBox(unsigned char a, unsigned char b, unsigned char mode) { return rotl2(a + b + mode); } unsigned long fBox(unsigned long plain) { unsigned char x0 = sepByte(plain, 0); unsigned char x1 = sepByte(plain, 1); unsigned char x2 = sepByte(plain, 2); unsigned char x3 = sepByte(plain, 3); unsigned char t0 = (x2 ^ x3); unsigned char y1 = gBox(x0 ^ x1, t0, 1); unsigned char y0 = gBox(x0, y1, 0); unsigned char y2 = gBox(t0, y1, 0); unsigned char y3 = gBox(x3, y2, 1); return combineBytes(y3, y2, y1, y0); } unsigned long long encrypt(unsigned long long plain) { unsigned long left = leftHalf(plain); unsigned long right = rightHalf(plain); left = left ^ subkey[4]; right = right ^ subkey[5]; unsigned long round2Left = left ^ right; unsigned long round2Right = left ^ fBox(round2Left ^ subkey[0]); unsigned long round3Left = round2Right; unsigned long round3Right = round2Left ^ fBox(round2Right ^ subkey[1]); unsigned long round4Left = round3Right; unsigned long round4Right = round3Left ^ fBox(round3Right ^ subkey[2]); unsigned long cipherLeft = round4Left ^ fBox(round4Right ^ subkey[3]); unsigned long cipherRight = cipherLeft ^ round4Right; return combineHalves(cipherLeft, cipherRight); } void generateSubkeys(int seed) { srand(seed); int c; for(c = 0; c < 6; c++) subkey[c] = (rand() << 16L) | (rand() & 0xFFFFL); } int numPlain; unsigned long long plain0[MAX_CHOSEN_PAIRS]; unsigned long long cipher0[MAX_CHOSEN_PAIRS]; unsigned long long plain1[MAX_CHOSEN_PAIRS]; unsigned long long cipher1[MAX_CHOSEN_PAIRS]; void undoFinalOperation() { int c; for(c = 0; c < numPlain; c++) { unsigned long cipherLeft0 = leftHalf(cipher0[c]); unsigned long cipherRight0 = rightHalf(cipher0[c]) ^ cipherLeft0; unsigned long cipherLeft1 = leftHalf(cipher1[c]); unsigned long cipherRight1 = rightHalf(cipher1[c]) ^ cipherLeft1; cipher0[c] = combineHalves(cipherLeft0, cipherRight0); cipher1[c] = combineHalves(cipherLeft1, cipherRight1); } } unsigned long crackLastRound(unsigned long outdiff) { printf(" Using output differential of 0x%08x\n", outdiff); printf(" Cracking..."); unsigned long fakeK; for(fakeK = 0x00000000L; fakeK < 0xFFFFFFFFL; fakeK++) { int score = 0; int c; for(c = 0; c < numPlain; c++) { unsigned long cipherLeft = (cipher0[c] >> 32LL); cipherLeft ^= (cipher1[c] >> 32LL); unsigned long cipherRight = cipher0[c] & 0xFFFFFFFFLL; cipherRight ^= (cipher1[c] & 0xFFFFFFFFLL); unsigned long Y = cipherRight; unsigned long Z = cipherLeft ^ outdiff; unsigned long fakeRight = cipher0[c] & 0xFFFFFFFFLL; unsigned long fakeLeft = cipher0[c] >> 32LL; unsigned long fakeRight2 = cipher1[c] & 0xFFFFFFFFLL; unsigned long fakeLeft2 = cipher1[c] >> 32LL; unsigned long Y0 = fakeRight; unsigned long Y1 = fakeRight2; unsigned long fakeInput0 = Y0 ^ fakeK; unsigned long fakeInput1 = Y1 ^ fakeK; unsigned long fakeOut0 = fBox(fakeInput0); unsigned long fakeOut1 = fBox(fakeInput1); unsigned long fakeDiff = fakeOut0 ^ fakeOut1; if (fakeDiff == Z) score++; else break; } if (score == numPlain) { printf("found subkey : 0x%08lx\n", fakeK); return fakeK; } } printf("failed\n"); return 0; } void chosenPlaintext(unsigned long long diff) { printf(" Generating %i chosen-plaintext pairs\n", numPlain); printf(" Using input differential of 0x%016llx\n", diff); srand(time(NULL)); int c; for(c = 0; c < numPlain; c++) { plain0[c] = (rand() & 0xFFFFLL) << 48LL; plain0[c] += (rand() & 0xFFFFLL) << 32LL; plain0[c] += (rand() & 0xFFFFLL) << 16LL; plain0[c] += (rand() & 0xFFFFLL); cipher0[c] = encrypt(plain0[c]); plain1[c] = plain0[c] ^ diff; cipher1[c] = encrypt(plain1[c]); } } void undoLastRound(unsigned long crackedSubkey) { int c; for(c = 0; c < numPlain; c++) { unsigned long cipherLeft0 = leftHalf(cipher0[c]); unsigned long cipherRight0 = rightHalf(cipher0[c]); unsigned long cipherLeft1 = leftHalf(cipher1[c]); unsigned long cipherRight1 = rightHalf(cipher1[c]); cipherLeft0 = cipherRight0; cipherLeft1 = cipherRight1; cipherRight0 = fBox(cipherLeft0 ^ crackedSubkey) ^ (cipher0[c] >> 32LL); cipherRight1 = fBox(cipherLeft1 ^ crackedSubkey) ^ (cipher1[c] >> 32LL); cipher0[c] = combineHalves(cipherLeft0, cipherRight0); cipher1[c] = combineHalves(cipherLeft1, cipherRight1); } } void prepForCrackingK0() { int c; for(c = 0; c < numPlain; c++) { unsigned long cipherLeft0 = leftHalf(cipher0[c]); unsigned long cipherRight0 = rightHalf(cipher0[c]); unsigned long cipherLeft1 = leftHalf(cipher1[c]); unsigned long cipherRight1 = rightHalf(cipher1[c]); unsigned long tempLeft0 = cipherLeft0; unsigned long tempLeft1 = cipherLeft1; cipherLeft0 = cipherRight0; cipherLeft1 = cipherRight1; cipherRight0 = tempLeft0; cipherRight1 = tempLeft1; cipher0[c] = combineHalves(cipherLeft0, cipherRight0); cipher1[c] = combineHalves(cipherLeft1, cipherRight1); } } int main() { printf("JK'S FEAL-4 DIFFERENTIAL CRYPTANALYSIS DEMO\n"); printf("-------------------------------------------\n"); printf("\n"); int graphData[20]; int c; generateSubkeys(time(NULL)); numPlain = 12; unsigned long long inputDiff1 = 0x8080000080800000LL; unsigned long long inputDiff2 = 0x0000000080800000LL; unsigned long long inputDiff3 = 0x0000000002000000LL; unsigned long outDiff = 0x02000000L; unsigned long fullStartTime = time(NULL); //CRACKING ROUND 4 printf("ROUND 4\n"); chosenPlaintext(inputDiff1); undoFinalOperation(); unsigned long startTime = time(NULL); unsigned long crackedSubkey3 = crackLastRound(outDiff); unsigned long endTime = time(NULL); printf(" Time to crack round #4 = %i seconds\n", (endTime - startTime)); //CRACKING ROUND 3 printf("ROUND 3\n"); chosenPlaintext(inputDiff2); undoFinalOperation(); undoLastRound(crackedSubkey3); startTime = time(NULL); unsigned long crackedSubkey2 = crackLastRound(outDiff); endTime = time(NULL); printf(" Time to crack round #3 = %i seconds\n", (endTime - startTime)); //CRACKING ROUND 2 printf("ROUND 2\n"); chosenPlaintext(inputDiff3); undoFinalOperation(); undoLastRound(crackedSubkey3); undoLastRound(crackedSubkey2); startTime = time(NULL); unsigned long crackedSubkey1 = crackLastRound(outDiff); endTime = time(NULL); printf(" Time to crack round #2 = %i seconds\n", (endTime - startTime)); //CRACK ROUND 1 printf("ROUND 1\n"); undoLastRound(crackedSubkey1); unsigned long crackedSubkey0 = 0; unsigned long crackedSubkey4 = 0; unsigned long crackedSubkey5 = 0; printf(" Cracking..."); startTime = time(NULL); unsigned long guessK0; for(guessK0 = 0; guessK0 < 0xFFFFFFFFL; guessK0++) { unsigned long guessK4 = 0; unsigned long guessK5 = 0; int c; for(c = 0; c < numPlain; c++) { unsigned long plainLeft0 = leftHalf(plain0[c]); unsigned long plainRight0 = rightHalf(plain0[c]); unsigned long cipherLeft0 = leftHalf(cipher0[c]); unsigned long cipherRight0 = rightHalf(cipher0[c]); unsigned long tempy0 = fBox(cipherRight0 ^ guessK0) ^ cipherLeft0; if (guessK4 == 0) { guessK4 = tempy0 ^ plainLeft0; guessK5 = tempy0 ^ cipherRight0 ^ plainRight0; } else if (((tempy0 ^ plainLeft0) != guessK4) || ((tempy0 ^ cipherRight0 ^ plainRight0) != guessK5)) { guessK4 = 0; guessK5 = 0; break; } } if (guessK4 != 0) { crackedSubkey0 = guessK0; crackedSubkey4 = guessK4; crackedSubkey5 = guessK5; endTime = time(NULL); printf("found subkeys : 0x%08lx 0x%08lx 0x%08lx\n", guessK0, guessK4, guessK5); printf(" Time to crack round #1 = %i seconds\n", (endTime - startTime)); break; } } printf("\n\n"); printf("0x%08lx - ", crackedSubkey0); if (crackedSubkey0 == subkey[0]) printf("Subkey 0 : GOOD!\n"); else printf("Subkey 0 : BAD\n"); printf("0x%08lx - ", crackedSubkey1); if (crackedSubkey1 == subkey[1]) printf("Subkey 1 : GOOD!\n"); else printf("Subkey 1 : BAD\n"); printf("0x%08lx - ", crackedSubkey2); if (crackedSubkey2 == subkey[2]) printf("Subkey 2 : GOOD!\n"); else printf("Subkey 2 : BAD\n"); printf("0x%08lx - ", crackedSubkey3); if (crackedSubkey3 == subkey[3]) printf("Subkey 3 : GOOD!\n"); else printf("Subkey 3 : BAD\n"); printf("0x%08lx - ", crackedSubkey4); if (crackedSubkey4 == subkey[4]) printf("Subkey 4 : GOOD!\n"); else printf("Subkey 4 : BAD\n"); printf("0x%08lx - ", crackedSubkey5); if (crackedSubkey5 == subkey[5]) printf("Subkey 5 : GOOD!\n"); else printf("Subkey 5 : BAD\n"); printf("\n"); unsigned long fullEndTime = time(NULL); printf("Total crack time = %i seconds\n", (fullEndTime - fullStartTime)); printf("FINISHED\n"); while(1){} return 0; }