differential.c

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]);
}