Cryptanalysis of DES

des.h

#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 */

DES.md

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.

main.c

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