Skip to content

Instantly share code, notes, and snippets.

@kelalaka153
Forked from pornin/find_collisions.c
Created August 17, 2020 13:54
Show Gist options
  • Save kelalaka153/083ef11c78b5c88c5b5e67394057b544 to your computer and use it in GitHub Desktop.
Save kelalaka153/083ef11c78b5c88c5b5e67394057b544 to your computer and use it in GitHub Desktop.
/*
* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment