find_collisions.c

/*
 * Let function f() be the DES confusion function, without the bit
 * permutation PC. It has two inputs (32-bit value x, which is the
 * right-half of the current DES block, and 48-bit subkey k) and
 * a 32-bit output.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

static const uint8_t Sdef[] = {
        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,

        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,

        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,

        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,

        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,

        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,

        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,

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

/*
 * S[i][x] is the 4-bit output of S-box i+1 (for 1 <= i+1 <= 8) on
 * 6-bit input x, left-shifted by 4*(7-i) bits so that the output is
 * already in its expected place.
 */
static uint32_t S[8][64];

static void
init_tables(void)
{
        int i;

        for (i = 0; i < 8; i ++) {
                int x, s;

                s = 4 * (7 - i);
                for (x = 0; x < 64; x ++) {
                        int row, col;

                        row = ((x & 32) >> 4) | (x & 1);
                        col = (x >> 1) & 15;
                        S[i][x] = (uint32_t)Sdef[64 * i + 16 * row + col] << s;
                }
        }
}

static inline uint32_t
rotl(uint32_t x, int n)
{
        return (x << n) | (x >> (32 - n));
}

static inline uint32_t
f(uint64_t k, uint32_t x)
{
        uint32_t y;
        int i;

        y = S[0][(rotl(x, 5) ^ (uint32_t)(k >> 42)) & 63];
        for (i = 1; i < 7; i ++) {
                uint32_t xb, kb;

                xb = x >> (27 - 4 * i);
                kb = k >> (42 - 6 * i);
                y |= S[i][(xb ^ kb) & 63];
        }
        y |= S[7][(rotl(x, 1) ^ (uint32_t)k) & 63];
        return y;
}

/*
 * Apply Floyd's cycle detection algorithm on function f() with a given
 * subkey k. Returned value is 1 on success, 0 on error. A success is
 * reported if a collision was found, in which case the collision is
 * written in *x1 and *x2; an error is reported if more than maxiter
 * iterations have been performed, and no collision was found.
 */
static int
find_collision(uint64_t k, uint32_t *x1, uint32_t *x2, uint32_t maxiter)
{
        uint32_t s, t, h;
        uint32_t n;

        n = 1;
        for (s = 0;; s ++) {
                t = s;
                h = s;
                while (n ++ <= maxiter) {
                        t = f(k, t);
                        h = f(k, h);
                        h = f(k, h);
                        if (t == h) {
                                break;
                        }
                }
                if (n > maxiter) {
                        return 0;
                }

                if (t == s) {
                        continue;
                }

                t = s;
                for (;;) {
                        uint32_t t2, h2;

                        t2 = f(k, t);
                        h2 = f(k, h);
                        if (t2 == h2) {
                                *x1 = t;
                                *x2 = h;
                                return 1;
                        }
                        t = t2;
                        h = h2;
                }
        }
}

int
main(void)
{
        uint32_t d;

        init_tables();
        for (d = 0; d < 0x10000; d ++) {
                uint64_t k;
                int i;
                uint32_t x1, x2;

                k = 0;
                for (i = 0; i < 8; i ++) {
                        k |= (uint64_t)((d >> (2 * (7 - i))) & 3)
                                << (46 - 6 * i);
                }
                if (find_collision(k, &x1, &x2, 1000000)) {
                        fprintf(stderr, "%012llx %08lx %08lx\n",
                                (unsigned long long)k,
                                (unsigned long)x1,
                                (unsigned long)x2);
                } else {
                        printf("\n%u\n", (unsigned)d);
                        fflush(stdout);
                }
                if (((d + 1) & 0xFF) == 0) {
                        printf(".");
                        fflush(stdout);
                }
        }
        printf("\n");
        return 0;
}