Skip to content

Instantly share code, notes, and snippets.

@mfaerevaag
Last active September 21, 2017 07:56
Show Gist options
  • Save mfaerevaag/0d076fdb225075d05f7c7b12cbf35bb1 to your computer and use it in GitHub Desktop.
Save mfaerevaag/0d076fdb225075d05f7c7b12cbf35bb1 to your computer and use it in GitHub Desktop.
Cryptanalysis of DES
#ifndef DES_H
#define DES_H
/* width of s-box input width (bits) */
#define DES_SIN (6)
/* width of s-box output width (bits) */
#define DES_SOUT (4)
/* rows in each s-box */
#define DES_SROW (4)
/* columns in each s-box */
#define DES_SCOL (16)
/* number of s-boxes */
#define DES_SNUM (8)
/* s-boxes */
int DES_S1[DES_SROW][DES_SCOL] =
{{ 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7 },
{ 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8 },
{ 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0 },
{ 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13 }};
int DES_S2[DES_SROW][DES_SCOL] =
{{ 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10 },
{ 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5 },
{ 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15 },
{ 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9 }};
int DES_S3[DES_SROW][DES_SCOL] =
{{ 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8 },
{ 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1 },
{ 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7 },
{ 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12 }};
int DES_S4[DES_SROW][DES_SCOL] =
{{ 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15 },
{ 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9 },
{ 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4 },
{ 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14 }};
int DES_S5[DES_SROW][DES_SCOL] =
{{ 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9 },
{ 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6 },
{ 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14 },
{ 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3 }};
int DES_S6[DES_SROW][DES_SCOL] =
{{ 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11 },
{ 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8 },
{ 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6 },
{ 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13 }};
int DES_S7[DES_SROW][DES_SCOL] =
{{ 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 },
{ 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6 },
{ 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2 },
{ 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12 }};
int DES_S8[DES_SROW][DES_SCOL] =
{{ 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7 },
{ 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2 },
{ 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8 },
{ 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11 }};
#endif /* DES_H */

Cryptanalysis of DES

Calculate and XOR Distribution Tables (XDT) for S-Boxes and best 2-round iterative characteristic (1/234).

All output of program is written to output.txt, found in the current working directory.

Should be compiled with C99 support.

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include "des.h"
/* integer exponent (naive) */
int iexp(int base, unsigned int exp);
/* apply given value to s-box */
int sbox(int n, int x);
/* utility function for printing XDT to file */
void print_tab(int x_size, int y_size, int tab[][y_size], FILE *fp);
/* path of output file */
char *output_path = "output.txt";
int main(void)
{
int n, i, j, is, js, x, y;
FILE *fp;
int x_size = iexp(2, DES_SIN),
y_size = iexp(2, DES_SOUT),
t_size = DES_SNUM;
/* declare number of XDT tables */
int xdt[t_size][x_size][y_size];
/* reset table to zero */
memset(xdt, 0, sizeof(xdt));
/* open output file */
fp = fopen(output_path, "w");
if (fp == NULL) {
fprintf(stderr, "error opening file '%s'\n", output_path);
exit(1);
}
/* for each s-box */
for (n = 1; n <= t_size; ++n) {
/* calculate XDT */
for (i = 0; i < x_size; ++i) {
/* calculate S(i) */
is = sbox(n, i);
for (j = 0; j < x_size; ++j) {
/* calculate S(j) */
js = sbox(n, j);
/* calculate differences */
x = i ^ j;
y = is ^ js;
/* increment table */
xdt[n - 1][x][y]++;
}
}
}
/* print tables */
for (n = 0; n < t_size; ++n) {
fprintf(fp, "S-Box #%d\n", n + 1);
print_tab(x_size, y_size, xdt[n], fp);
fprintf(fp, "\n");
}
/* calculate best iterative characteristic */
fprintf(fp, "Best 2-round iterative characteristic:\n\n");
fprintf(fp, "Def. Om = (Op, Or, Ot),\n"
"\twhere Op, Ot are m-nit numbers and Or = (r_1, r_2),\n"
"\twhere r_i = (rIi, rOi),\n"
"\twhere rIi and rOi are m/2 bit numbers\n"
"\twhere m is the block size.\n\n");
fprintf(fp, "Given Op and Ot, we calculate rIi by\n"
"\trI1 = the right half of Op\n"
"\trI2 = the left half of Op XOR rO1\n"
"\trI2 = the right half of Ot\n"
"\trI1 = the left half of Ot XOR rO2.\n\n");
fprintf(fp, "It is well known that p_2 = 1/234 is the best characteristic\n"
"\twhere Op = 0x1960000000000000\n"
"\tand Ot = 0x0000000019600000\n\n");
fprintf(fp, "With Op and Ot, we set rIi and rOi to:\n"
"\trI1 = 0x00000000\n"
"\trI2 = 0x19600000\n"
"\trO1 = 0x00000000\n"
"\trO2 = 0x00000000\n\n");
uint32_t
rI1[] = { 0, 0, 0, 0, 0, 0, 0, 0 },
rI2[] = { 1, 9, 6, 0, 0, 0, 0, 0 },
rO1[] = { 0, 0, 0, 0, 0, 0, 0, 0 },
rO2[] = { 0, 0, 0, 0, 0, 0, 0, 0 };
fprintf(fp, "After extension, rI1 and rI2 are the inputs and rO1 and rO2 are the outputs to F-function.\n\n");
uint64_t eI1 = 0, eI2 = 0;
uint32_t erI1[8], erI2[8];
for(i = 0; i < 8; ++i) {
erI1[i] = (rI1[(i + 7) % 8] % 2) * 32 + rI1[i] * 2 + rI1[(i + 1) % 8] / 8;
erI2[i] = (rI2[(i + 7) % 8] % 2) * 32 + rI2[i] * 2 + rI2[(i + 1) % 8] / 8;
}
for(i = 0; i < 8; ++i) {
eI1 = 64 * eI1 + erI1[i];
eI2 = 64 * eI2 + erI2[i];
}
double p1 = 1.0f, p2 = 1.0f;
fprintf(fp, "Using XDTs, the probability of each tuple, p_1, becomes:\n\n");
fprintf(fp, "\tInput:\n"
"\trI1 = 0x%02x%02x%02x%02x%02x%02x%02x%02x\n"
"\trI02 = 0x%02x%02x%02x%02x%02x%02x%02x%02x\n\n",
erI1[0], erI1[1], erI1[2], erI1[3], erI1[4], erI1[5], erI1[6], erI1[7],
erI2[0], erI2[1], erI2[2], erI2[3], erI2[4], erI2[5], erI2[6], erI2[7]);
fprintf(fp, "\tOutput:\n");
for(i = 0; i < 8; ++i) {
fprintf(fp, "\tS-Box #%d: rI1[%d] = 0x%02x, rO1[%d] = 0x%02x -> XDT[%d][%d] = %d/64\n",
i+1, i+1, erI1[i], i+1, rO1[i], erI1[i], rO1[i], xdt[i][erI1[i]][rO1[i]]);
}
fprintf(fp, "\n\tResult:\n\tp_1 = ");
for(i = 0; i < 7; ++i) {
fprintf(fp, "%d/64 * ", xdt[i][erI1[i]][rO1[i]]);
}
fprintf(fp, "%d/64 = ", xdt[7][erI1[7]][rO1[7]]);
for(i = 0; i < 8; ++i) {
p1 *= (double) xdt[i][erI1[i]][rO1[i]] / (double) 64;
}
fprintf(fp, "%.6lf\n\n", p1);
fprintf(fp, "Again, using XDTs, the probability p_2 becomes:\n\n");
fprintf(fp, "\tInput:\n"
"\trI1 = 0x%02x%02x%02x%02x%02x%02x%02x%02x\n"
"\trI02 = 0x%02x%02x%02x%02x%02x%02x%02x%02x\n\n",
erI1[0], erI1[1], erI1[2], erI1[3], erI1[4], erI1[5], erI1[6], erI1[7],
erI2[0], erI2[1], erI2[2], erI2[3], erI2[4], erI2[5], erI2[6], erI2[7]);
fprintf(fp, "\tOutput:\n");
for(i = 0; i < 8; ++i) {
fprintf(fp, "\tS-Box #%d: rI2[%d] = 0x%02x, rO2[%d] = 0x%02x -> XDT[%d][%d] = %d/64\n",
i+1, i+1, erI2[i], i+1, rO2[i], erI2[i], rO2[i], xdt[i][erI2[i]][rO2[i]]);
}
fprintf(fp, "\n\tResult:\n\tp_2 = ");
for(i = 0; i < 7; ++i) {
fprintf(fp, "%d/64 * ", xdt[i][erI2[i]][rO2[i]]);
}
fprintf(fp, "%d/64 = ", xdt[7][erI2[7]][rO2[7]]);
for(i = 0; i < 8; ++i) {
p2 *= (double) xdt[i][erI2[i]][rO2[i]] / (double) 64;
}
fprintf(fp, "%.6lf\n\n", p2);
fprintf(fp, "The holding probability becomes:\n"
"\t p_1 * p_2 = %.6lf * %.6lf\n"
"\t = %.6lf\n"
"\t ~= 1/234\n\n",
p1, p2, p1 * p2);
fprintf(fp, "Thus, we have successfully verified the best iterative characteristic of DES to be 1/234.\n");
/* close file handle */
fclose(fp);
return 0;
}
int iexp(int base, unsigned int exp)
{
int i, result = 1;
for (i = 0; (unsigned) i < exp; i++)
result *= base;
return result;
}
int sbox(int n, int x)
{
int row, col;
/* calculate row and column in sbox */
/* SBOX[b0b5][b1b2b3b4], where b are the binary input */
row = ((x & 1) | ((x & (1 << 5)) >> 4));
col = ((x >> 1) & 0xf);
/* select correct sbox */
switch (n) {
case 1: return DES_S1[row][col];
case 2: return DES_S2[row][col];
case 3: return DES_S3[row][col];
case 4: return DES_S4[row][col];
case 5: return DES_S5[row][col];
case 6: return DES_S6[row][col];
case 7: return DES_S7[row][col];
case 8: return DES_S8[row][col];
default:
fprintf(stderr, "invalid sbox #%d", n);
exit(1);
}
}
void print_tab(int x_size, int y_size, int tab[][y_size], FILE *fp)
{
int i, j;
fprintf(fp, " ");
for (i = 0; i < y_size; i++) {
fprintf(fp, "x%02x ", i);
}
fprintf(fp, "\n");
for (i = 0; i < x_size; ++i) {
for (j = 0; j < y_size; j++) {
if (j == 0) fprintf(fp, "x%02x ", i);
fprintf(fp, "%3d ", tab[i][j]);
}
fprintf(fp, "\n");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment