###### Sprachumschaltung

You are here: Home / differential.c

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

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;
for (int i = 0; i < 8; i++) {
if (nibble(c.diff[NROUNDS -1], i) > 0) {
number_of_bits += 4;
}
}

if (number_of_bits > 16) {
printf("- too many bits to try.\n");
return;
}

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);
printf("- mask for key candidate bits after last permutation: ");

// Compute just so many samples that we can expect our target differential to
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++;

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

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 */
/* 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("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

###### Servicebereich
News and Events

For news and events please switch to the German page.