//Jon King //Impossible Differentials #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 pbox[8] = {1, 6, 0, 7, 2, 3, 5, 4}; int pboxRev[8] = {2, 0, 4, 5, 7, 6, 1, 3}; int mySPBox[256]; int chars[256][256]; int revSPBox(int input) { int c; for(c = 0; c < 256; c++) { if (mySPBox[c] == input) return c; } } int spBox(int input) { int lefthalf = input / 16; int righthalf = input & 15; lefthalf = sbox[lefthalf]; righthalf = sbox[righthalf]; int combined = lefthalf * 16 + righthalf; int total = 0; int c; for(c = 0; c < 8; c++) { int inBit = combined % (int)(pow(2, c + 1)); inBit = inBit / (int)(pow(2, c)); total += inBit * pow(2, pbox[c]); } return total; } void createSPBox() { int c; for(c = 0; c < 256; c++) mySPBox[c] = spBox(c); } int roundFunc(int input, int subkey) { return mySPBox[input ^ subkey]; } int encrypt(int input, int k0, int k1, int k2, int k3, int k4) { int r0 = roundFunc(input, k0); int r1 = roundFunc(r0, k1); int r2 = roundFunc(r1, k2); int r3 = roundFunc(r2, k3); return roundFunc(r3, k4); } void genChars() { printf("\nOne-round impossible differentials:\n"); int c, d; for(c = 0; c < 256; c++) for(d = 0; d < 256; d++) { int indiff = c ^ d; int outdiff = mySPBox[c] ^ mySPBox[d]; chars[indiff][outdiff]++; } for(c = 0; c < 256; c++) { for(d = 0; d < 256; d++) { if (chars[c][d] == 0) //if (c == 140) printf(" %i: %i --> %i\n", chars[c][d], c, d); } } } int goodP0, goodP1, goodC0, goodC1; int knownP0[10000]; int knownC0[10000]; int knownP1[10000]; int knownC1[10000]; int numPairs = 100; int k0, k1, k2, k3, k4; void chooseKey() { k0 = rand() % 256; k1 = rand() % 256; k2 = rand() % 256; k3 = rand() % 256; k4 = rand() % 256; printf("\nREAL KEY = %i, %i, %i, %i, %i\n\n", k0, k1, k2, k3, k4); } void choosePairs(int indiff, int pairs) { numPairs = pairs; int c; for(c = 0; c < numPairs; c++) { knownP0[c] = rand() % 256; knownP1[c] = knownP0[c] ^ indiff; knownC0[c] = encrypt(knownP0[c], k0, k1, k2, k3, k4); knownC1[c] = encrypt(knownP1[c], k0, k1, k2, k3, k4); knownC0[c] = revSPBox(knownC0[c]); knownC1[c] = revSPBox(knownC1[c]); } } int isPath(int src, int dest, int level) { if (level == 1) if (chars[src][dest] == 0) return 0; else return 1; else { int c; for(c = 0; c < 255; c++) { if (chars[src][c] > 0) { if (isPath(c, dest, level-1)) return 1; } } } return 0; } int impIn[10000]; int impOut[10000]; int numImp = 0; void findImpossible(int length) { printf("\n%i-round impossible differentials\n\n", length); int d; for(d = 1; d < 255; d++) { int c; for(c = 1; c < 255; c++) { if (isPath(d, c, length) == 0) { printf(" IMPOSSIBLE for %i rounds: %i -> %i\n",length, d , c); impIn[numImp] = d; impOut[numImp] = c; numImp++; } } } } int main() { srand(time(NULL)); //OFFLINE PHASE printf("OFFLINE PHASE\n"); printf("------------------------------\n\n"); createSPBox(); genChars(); findImpossible(3); //ONLINE PHASE chooseKey(); //genCharData(); int d; int keyCandidate[256]; for(d = 0; d < 255; d++) keyCandidate[d] = 0; printf("\n"); printf("ONLINE PHASE\n"); printf("------------------------------\n\n"); int pairs = 100; for(d = 0;d < numImp; d++) { choosePairs(impIn[d], pairs); printf(" Generating %i pairs...Ruling out subkeys using: %i --> %i\n", numPairs, impIn[d], impOut[d]); int e, f; for(e = 0; e < numPairs; e++) { for(f = 0; f < 255; f++) { int revKnownC0 = revSPBox(knownC0[e] ^ f); int revKnownC1 = revSPBox(knownC1[e] ^ f); if ((revKnownC0 ^ revKnownC1) == impOut[d]) { keyCandidate[f] = 1; } } } } for(d = 0; d < 255; d++) if (keyCandidate[d] == 0) printf("LAST ROUND SUBKEY CANDIDATE: %i\n", d); /* int s,t,u,v,w; for(s = 0; s < 255; s++) for(t = 0;t < 255; t++) for(u = 0; u < 255; u++) for(v = 0; v < 255; v++) for(w = 0; w < 255; w++) if (encrypt(knownP1[1], k0, k1, k2, k3, k4) == spBox(knownC1[1])) { } */ printf("DONE\n"); while(1){} return 0; }