md4-collision/md4-collision.c

   1 #include <stdio.h>
   2 #include <stdint.h>
   3 #include <sys/types.h>
   4 #include <sys/stat.h>
   5 #include <fcntl.h>
   6 #include <string.h>
   7 #include <stdlib.h>
   8 #include <unistd.h>
   9
  10 #define uint32 uint32_t
  11
  12 #include "mdfour.h"
  13
  14
  15 struct md4_result {
  16         unsigned data[16/sizeof(unsigned)];
  17 };
  18
  19 #define HASH_BITS 22
  20 #define BUCKETS 12
  21
  22 static struct md4_result results[1<<HASH_BITS][BUCKETS];
  23
  24 int main(void)
  25 {
  26         int fd;
  27         int count=0;
  28         char buf[1024];
  29         struct md4_result zero;
  30
  31         fd = open("/dev/urandom", O_RDONLY);
  32         if (fd == -1) {
  33                 perror("/dev/urandom");
  34                 return -1;
  35         }
  36
  37         memset(zero.data, 0, 16);
  38
  39         while (1) {
  40                 struct md4_result r;
  41                 int i, b;
  42
  43                 size_t size = 200 + random() % (sizeof(buf)-200);
  44                 if (read(fd, buf, size) != size) {
  45                         printf("failed to init random bytes\n");
  46                         exit(1);
  47                 }
  48
  49                 mdfour((unsigned char *)r.data, buf, size);
  50
  51                 i = r.data[0] & ((1<<HASH_BITS)-1);
  52                 for (b=0;b<BUCKETS;b++) {
  53                         struct md4_result *old = &results[i][b];
  54                         if (memcmp(old->data, zero.data, 16) == 0) {
  55                                 results[i][b] = r;
  56                                 break;
  57                         } else if (memcmp(old->data, r.data, 16) == 0) {
  58                                 printf("\nfound a collision after %d calls! (%d/%d)\n",
  59                                        count, i, b);
  60                                 exit(1);
  61                         }
  62                 }
  63                 if (b == BUCKETS) {
  64                         printf("\nout of buckets at %d\n", i);
  65                         exit(1);
  66                 }
  67
  68                 count++;
  69                 if (count % 1000 == 0) {
  70                         printf("%7d\r", count);
  71                         fflush(stdout);
  72                 }
  73         }
  74
  75 }
  76