Sprachumschaltung

You are here: Home / exercise6_2.c

exercise6_2.c

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