//Jon King //Differential Cryptanalysis Toy Implementation #include int sbox[16] = {3, 14, 1, 10, 4, 9, 5, 6, 8, 11, 15, 2, 13, 12, 0, 7}; int sboxRev[16] = {14, 2, 11, 0, 4, 6, 7, 15, 8, 5, 3, 9, 13, 12, 1, 10}; int chars[16][16]; int roundFunc(int input, int key) { return sbox[key ^ input]; } int encrypt(int input, int k0, int k1) { int x0 = roundFunc(input, k0); return x0 ^ k1; } void findDiffs() { printf("\nCreating XOR differential table:\n"); int c, d, e, f; for(c = 0; c < 16; c++) for(d = 0; d < 16; d++) chars[c ^ d][sbox[c] ^ sbox[d]]++; for(c = 0; c < 16; c++) { for(d = 0; d < 16; d++) printf(" %x ", chars[c][d]); printf("\n"); } printf("\nDisplaying most probable differentials:\n"); for(c = 0; c < 16; c++) for(d = 0; d < 16; d++) if (chars[c][d] == 6) printf(" 6/16: %i --> %i\n", c, d); } int knownP0[10000]; int knownP1[10000]; int knownC0[10000]; int knownC1[10000]; int goodP0, goodP1, goodC0, goodC1; int numPairs; //int realk0, realk1; int chardat0[16]; int chardatmax = 0; void genCharData(int indiff, int outdiff) { printf("\nGenerating possible intermediate values based on differential(%i --> %i):\n", indiff, outdiff); chardatmax = 0; int f; for(f = 0; f < 16; f++) { int myComp = f ^ indiff; if ((sbox[f] ^ sbox[myComp]) == outdiff) { printf(" Possibles: %i + %i --> %i + %i\n", f, myComp, sbox[f], sbox[myComp]); chardat0[chardatmax] = f; chardatmax++; } } } void genPairs(int indiff) { printf("\nGenerating %i known pairs with input differential of %i.\n", numPairs, indiff); int realk0 = rand() % 16; //Create random subkey0 int realk1 = rand() % 16; //Create random subkey0 printf(" Real K0 = %i\n", realk0); printf(" Real K1 = %i\n", realk1); int c; for(c = 0; c < numPairs; c++) //Create plaintext pairs with XOR difference of indiff { knownP0[c] = rand() % 16; knownP1[c] = knownP0[c] ^ indiff; knownC0[c] = encrypt(knownP0[c], realk0, realk1); knownC1[c] = encrypt(knownP1[c], realk0, realk1); } } void findGoodPair(int outdiff) { printf("\nSearching for good pair:\n"); int c; for(c = 0; c < numPairs; c++) if ((knownC0[c] ^ knownC1[c]) == outdiff) //Does the ciphertext pair fit the characteristic? { goodC0 = knownC0[c]; goodC1 = knownC1[c]; goodP0 = knownP0[c]; goodP1 = knownP1[c]; printf(" FOUND GOOD PAIR: (P0 = %i, P1 = %i) --> (C0 = %i, C1 = %i)\n", goodP0, goodP1, goodC0, goodC1); return; } printf("NO GOOD PAIR FOUND!\n"); } int testKey(int testK0, int testK1) { int c; int crap = 0; for(c = 0; c < numPairs; c++) { if ((encrypt(knownP0[c], testK0, testK1) != knownC0[c]) || (encrypt(knownP1[c], testK0, testK1) != knownC1[c])) { crap = 1; break; } } if (crap == 0) return 1; else return 0; } void crack() { printf("\nBrute forcing reduced keyspace:\n"); int f; for(f = 0; f < chardatmax; f++) //Test each possible value based on characteristic { int testK0 = chardat0[f] ^ goodP0; int testK1 = sbox[chardat0[f]] ^ goodC0; if (testKey(testK0, testK1) == 1) printf(" KEY! (%i, %i)\n", testK0, testK1); else printf(" (%i, %i)\n", testK0, testK1); } } int main() { srand(time(NULL)); //Randomize values per run findDiffs(); //Find some good differentials in the S-Boxes numPairs = 8; //Define number of known pairs genCharData(4, 7); //Find inputs that lead a certain characteristic genPairs(4); //Generate chosen-plaintext pairs findGoodPair(7); //Choose a known pair that satisfies the characteristic crack(); //Use charData and "good pair" in find key while(1){} return 0; }