Links und Funktionen
Sprachumschaltung

Navigationspfad
You are here: Home / Teaching / Summer 2017 / Cryptography / Exercises / exercise6_2.c


Inhaltsbereich

exercise6_2.c

C source code icon exercise6_2.c — C source code, 5 KB (5727 bytes)

File contents

/********************************************************************************
 * This program solves Excercise 6-2 by outputting the count for each candidate
 * of the key bits.
 ********************************************************************************/
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>

#define NROUNDS 3

/********************************************************************************
 * 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, // ...
  0x9f124566,
};

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 w) {
  return v == w;
}

word_t or_word(word_t v, word_t w) {
  return v | w;
}

word_t and_word(word_t v, word_t w) {
  return v & w;
}

word_t xor_word(word_t v, word_t w) {
  return v ^ 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;
}

/* 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;
}

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

/********************************************************************************
 * Counting differentials as described in Exercise 6-2.
 ********************************************************************************/

int main() {

  /* Initialisation */
  srand(time(NULL));
  inverse(sbox_inv, sbox, 16);
  inverse(perm_inv, perm, 32);

  word_t candidate[256];
  int count[256];

  word_t d = zero_word();
  int i = 0;
  do {
    candidate[i] = d;
    count[i] = 0;
    i++;
  } while (next_possibility(&d, 0x00800002));

  for (int i = 0; i < 100; i++) {
    word_t x1 = rand_word();
    word_t x2 = xor_word(x1, 0x0000b000);

    word_t e1 = encode(x1, &key);
    word_t e2 = encode(x2, &key);

    for (int j = 0; j < 256; j++) {
      word_t y1 = permute_bits(perm_inv, e1);
      y1 = xor_word(y1, candidate[j]);
      y1 = apply_sboxes(sbox_inv, y1);

      word_t y2 = permute_bits(perm_inv, e2);
      y2 = xor_word(y2, candidate[j]);
      y2 = apply_sboxes(sbox_inv, y2);

      if (xor_word(y1, y2) == 0x00800002) {
        count[j]++;
      }
    }
  }
  for (int j = 0; j < 256; j++) {
    printf(" %i : %08x \n", count[j], permute_bits(perm, candidate[j]));
  }

  printf("Correct key bits %08x\n", and_word(key.subkey[3], permute_bits(perm, 0x00f0000f)));
}

Document Actions


Funktionsleiste