differential.c
differential.c
—
C source code,
13 KB (13790 bytes)
File contents
#include <time.h> #include <stdlib.h> #include <stdio.h> #include <stdbool.h> #include <stdint.h> #include <string.h> /* Number of full rounds (not counting the xor-ing of the final subkey) */ #define NROUNDS 3 /* Consider only differentials with probability at least PRUNE_PROB. This makes * finding the most likely differential in the last round faster. If the * number of rounds is increased, this number may need to be decreased. */ #define PRUNE_PROB 0.0001 /******************************************************************************** * Type definitions ********************************************************************************/ /* Type of input and output words of sp-network. */ typedef int32_t word_t; /* Key consists of a subkey for each round, plus one key to xor after * the final round. */ struct key { word_t subkey[NROUNDS + 1]; }; /******************************************************************************** * Parameters of sp-network ********************************************************************************/ const struct key key = { 0x01234566, // subkey for round 0 0xafcefeff, // subkey for round 1 0x9f124576, // ... 0xde7ec7ed, }; const uint8_t sbox[16] = { 0xe, 0x4, 0x0, 0x1, 0x2, 0xf, 0x8, 0xb, 0x3, 0xa, 0x6, 0xc, 0x5, 0x9, 0xd, 0x7 }; const uint8_t perm[32] = { 15, 6, 19, 20, 28, 11, 27, 16, 0, 14, 22, 25, 4, 17, 30, 9, 1, 7, 23, 13, 31, 26, 2, 8, 18, 12, 29, 5, 21, 10, 3, 24 }; /* inverses of sbox and permutation will be computed */ uint8_t sbox_inv[16]; uint8_t perm_inv[32]; /* Function to compute the inverse of a permutation */ void inverse(uint8_t inv[], const uint8_t perm[], const int n) { for (uint8_t i = 0; i < n; i++) { int v = -1; for (uint8_t j = 0; j < n; j++) { if (perm[j] == i) { v = j; } } inv[i] = v; } } /******************************************************************************** * Functions for manipulating words ********************************************************************************/ bool bit(int32_t x, int i) { return (x >> i) & 1; } int nibble(word_t x, int i) { return (x >> (4 * i)) & 0xf; } void set_nibble(word_t *x, int i, uint8_t n) { *x &= ~(0xf << (4 * i)); // delete old bits *x |= (n & 0xf) << (4 * i); // set new bits } void print_word(word_t w) { printf("%08x\n", w); } word_t from_int32(int32_t x) { return x; } word_t zero_word() { return from_int32(0); } word_t rand_word() { word_t w; for (int i = 0; i < 8; i++) { set_nibble(&w, i, rand() & 0xf); } return w; } bool equal_word(word_t v, word_t k) { return v == k; } word_t or_word(word_t v, word_t k) { return v | k; } word_t and_word(word_t v, word_t k) { return v & k; } word_t xor_word(word_t v, word_t k) { return v ^ k; } /* This is slow. */ word_t permute_bits(const uint8_t perm[], const word_t v) { word_t w = zero_word(); for (int i = 0; i < 32; i++) { if (bit(v, i)) { w |= 1 << perm[i]; } } return w; } /* A function for iterating over all possible words, where some nibbles * are fixed to constant zero. * The argument zero_nibbles specifies which nibbles are constant zero. * If a nibble is 0 in zero_nibbles, then it will be constant 0 in the * iteration. Any nibble that is not 0 in zero_nibbles will take on all * possible values in the iteration. */ bool next_possibility(word_t *w, const word_t zero_nibbles) { int i = 0; while (i < 8) { while (nibble(zero_nibbles, i) == 0) { i++; if (i >= 8) return false; } int8_t wi = nibble(*w, i); if (wi < 15) { set_nibble(w, i, wi + 1); return true; } else { set_nibble(w, i, 0); i++; } } return false; } /******************************************************************************** * Implementation of encryption ********************************************************************************/ /* Apply eight S-Boxes in parallel to the input word */ word_t apply_sboxes(const uint8_t sbox[], word_t v) { word_t w = zero_word(); for (int i = 0; i < 8; i++) { set_nibble(&w, i, sbox[nibble(v, i)]); } return w; } word_t encode(const word_t input, const struct key *k) { word_t code = input; for (int j = 0; j < NROUNDS; j++) { code = xor_word(code, k->subkey[j]); code = apply_sboxes(sbox, code); code = permute_bits(perm, code); } // final round without s-boxes or permutation code = xor_word(code, k->subkey[NROUNDS]); return code; } /******************************************************************************** * Computing the difference statistics of the S-Box ********************************************************************************/ int sbox_diffstat[16][16]; void init_sbox_diffstat() { for (int i = 0; i < 16; i++) { for (int j = 0; j < 16; j++) { sbox_diffstat[i][j] = 0; } } for (uint8_t x1 = 0; x1 < 16; x1++) { for (uint8_t x2 = 0; x2 < 16; x2++) { int dx = x1 ^ x2; int dy = sbox[x1] ^ sbox[x2]; sbox_diffstat[dx][dy]++; } } } /******************************************************************************** * Computing a characteristic (the most likely differentials before all rounds) * for the network. ********************************************************************************/ struct word_prob { word_t wd; double prob; }; /* An iterator to iterate over possible output differential * of an S-Box-layer. */ struct iter { bool has_next; int poss[8][16 + 1]; // possible differences for each nibble, terminated with -1 double prob[8][16 + 1]; // probabilities of possibilities int n[8]; // indices of next tuple }; /* Returns an iterator that iterates over all possible output * differences of an S-Box-layer whose input difference is in_diff. */ struct iter out_diff_iter(word_t in_diff) { struct iter it; for (int i = 0; i < 8; i++) { int k = 0; for (int j = 0; j < 16; j++) { if (sbox_diffstat[nibble(in_diff, i)][j] > 0) { it.poss[i][k] = j; it.prob[i][k] = ((double)sbox_diffstat[nibble(in_diff, i)][j]) / 16.0; k++; } } it.poss[i][k] = -1; } for (int i = 0; i < 8; i++) { it.n[i] = 0; } it.has_next = true; return it; } struct word_prob next(struct iter *it) { struct word_prob next; next.prob = 1.0; for (int i = 0; i < 8; i++) { next.prob *= it->prob[i][it->n[i]]; set_nibble(&next.wd, i, it->poss[i][it->n[i]]); } it->n[0]++; if (it->poss[0][it->n[0]] == -1) { it->n[0] = 0; it->n[1]++; } if (it->poss[1][it->n[1]] == -1) { it->n[1] = 0; it->n[2]++; } if (it->poss[2][it->n[2]] == -1) { it->n[2] = 0; it->n[3]++; } if (it->poss[3][it->n[3]] == -1) { it->n[3] = 0; it->n[4]++; } if (it->poss[4][it->n[4]] == -1) { it->n[4] = 0; it->n[5]++; } if (it->poss[5][it->n[5]] == -1) { it->n[5] = 0; it->n[6]++; } if (it->poss[6][it->n[6]] == -1) { it->n[6] = 0; it->n[7]++; } if (it->poss[7][it->n[7]] == -1) { it->has_next = false; } return next; } struct characteristic { int start_round; word_t diff[NROUNDS]; double prob; }; /* * Compute the characteristic (i.e. the most likely differentials) for * the rounds from start_round to NROUNDS - 1 under the assumption that * the input differential of start_round is in_diff. */ struct characteristic max_likey_char(struct word_prob in_diff, int start_round) { struct characteristic best; if (start_round == NROUNDS - 1) { best.start_round = start_round; best.diff[start_round] = in_diff.wd; best.prob = in_diff.prob; return best; } struct iter it = out_diff_iter(in_diff.wd); best.prob = 0.0; while (it.has_next) { struct word_prob dnext = next(&it); dnext.prob *= in_diff.prob; if (dnext.prob < PRUNE_PROB) continue; dnext.wd = permute_bits(perm, dnext.wd); struct characteristic best_rest = max_likey_char(dnext, start_round + 1); if (best_rest.prob > best.prob) { best = best_rest; best.diff[start_round] = in_diff.wd; } } return best; } /******************************************************************************** * Differential cryptanalysis (essentially as in exercise6_2.c, only * with arbitrary numbers) *******************************************************************************/ struct partial_key { word_t key_bits; word_t bit_mask; }; void analyse(struct partial_key *result, struct characteristic c) { // Mask contains all the bits where last layer of S-Boxes has // non-zero output difference. It's easier (and faster) to // work with the words at this point (i.e. before the last permutation). int number_of_bits = 0; word_t mask = zero_word(); for (int i = 0; i < 8; i++) { if (nibble(c.diff[NROUNDS -1], i) > 0) { set_nibble(&mask, i, 0xf); number_of_bits += 4; } } if (number_of_bits > 16) { printf("- too many bits to try.\n"); return; } if (equal_word(result->bit_mask, or_word(result->bit_mask, permute_bits(perm, mask)))) { printf("- key bits already known.\n"); return; } // How many key candiates do we have to try? int candidate_count = 1 << number_of_bits; printf("- mask for key candidate bits before last permutation (%i bits to try): ", number_of_bits); print_word(mask); printf("- mask for key candidate bits after last permutation: "); print_word(permute_bits(perm, mask)); // Compute just so many samples that we can expect our target differential to // occur about 10 times. int nsamples = (int)(10.0 / c.prob); printf("- trying %i sample inputs, %i keys for each sample.\n ", nsamples, candidate_count); // Compute all candidates for the key bits at the outputs of the // last S-Boxes (before last permutation). // Set the count for each candidate to zero. word_t *key_candidates = malloc(candidate_count * sizeof(word_t)); int *counts = malloc(candidate_count * sizeof(int)); word_t key_cand = zero_word(); int i = 0; do { key_candidates[i] = key_cand; counts[i] = 0; i++; } while (next_possibility(&key_cand, mask)); // Randomly sample inputs with given input difference. int count_max = 0; for (int sample = 0; sample < nsamples; sample++) { if (sample % (nsamples / 20) == 0) { printf("."); fflush(stdout); } /* Generate random input pair (x1, x2) with input difference */ word_t x1 = rand_word(); word_t x2 = xor_word(x1, c.diff[0]); /* Encrypt the pair. */ word_t y1 = encode(x1, &key); word_t y2 = encode(x2, &key); /* For each candidate for the key bits, compute the difference at the * penultimate round. Permutation can be inverted outside the loop. */ y1 = permute_bits(perm_inv, y1); y2 = permute_bits(perm_inv, y2); for (int i = 0; i < candidate_count; i++) { word_t v1 = xor_word(key_candidates[i], y1); v1 = apply_sboxes(sbox_inv, v1); word_t v2 = xor_word(key_candidates[i], y2); v2 = apply_sboxes(sbox_inv, v2); word_t diff_penultimate_round = xor_word(v1, v2); if (equal_word(c.diff[NROUNDS - 1], diff_penultimate_round)) { counts[i]++; count_max = (counts[i] > count_max) ? counts[i] : count_max; } } } printf("\n"); int number_of_matches = 0; int best = -1; printf("- most likely key candidates:\n"); for (int j = 0; j < candidate_count; j++) { if (counts[j] == count_max) { number_of_matches++; best = j; printf(" - with %i samples of %i: ", counts[j], nsamples); print_word(permute_bits(perm, key_candidates[j])); } } // Only one candidate! Add the newly found bits to the result. if (number_of_matches == 1) { result->key_bits |= permute_bits(perm, key_candidates[best]); result->bit_mask |= permute_bits(perm, mask); } free(key_candidates); free(counts); } /******************************************************************************** * Main function with test inputs ********************************************************************************/ int main() { /* Initialisation */ srand(time(NULL)); inverse(sbox_inv, sbox, 16); inverse(perm_inv, perm, 32); /* Compute difference statistic */ init_sbox_diffstat(); printf("Difference statistics of S-Box (inputs in rows, outputs in columns)\n"); for (int i = 0; i < 16; i++) { for (int j = 0; j < 16; j++) { printf("%2i ", sbox_diffstat[i][j]); } printf("\n"); } printf("\n"); /* partial information about the final round key */ struct partial_key k = {0, 0}; /* Repeat until all of key is known */ while (k.bit_mask != 0xffffffff) { /* Choose a random input differential */ struct word_prob input = {zero_word(), 1.0}; set_nibble(&input.wd, rand() & 7, rand() & 15); /* Output status information */ printf("\n\n****************************\n"); printf("Mask of known bits: "); print_word(k.bit_mask); printf("Value of bits: "); print_word(k.key_bits); printf("\n"); printf("- input difference to analyse next "); print_word(input.wd); /* Compute the most likely differentials for the input * differential in variable input */ struct characteristic c = max_likey_char(input, 0); printf("- best characteristic has probability %f:\n", c.prob); for (int i = 0; i < NROUNDS; i++) { printf(" - difference before round %i: ", i); print_word(c.diff[i]); } if (c.prob == 0.0) continue; analyse(&k, c); } printf("\n\n****************************\n"); printf("Subkey recovered with differential cryptanalysis: "); print_word(k.key_bits); printf("Correct subkey: "); print_word(key.subkey[NROUNDS]); }
Document Actions