cangrepp

Some cryptographic attacks
Log | Files | Refs | README

bloomer.c (2754B)

      1 #include <errno.h>
      2 #include <flint.h>
      3 #include <fmpz.h>
      4 #include <fmpz_vec.h>
      5 #include <stdint.h>
      6 #include <stdio.h>
      7 #include <stdlib.h>
      8 
      9 #include "bloom.h"
     10 
     11 #define BIT_SIZE 4096
     12 
     13 static inline void
     14 print_usage(char *prog)
     15 {
     16   printf("Usage: %s k m n\n"
     17          "  k: number of hash functions\n"
     18          "  m: size of bit vector\n"
     19          "  n: number of entries to insert\n");
     20 }
     21 
     22 int
     23 main(int argc, char *argv[])
     24 {
     25   uint64_t k, m, n;
     26   size_t i;
     27   char *ep;
     28   bloom_t bloom;
     29 
     30   if (argc != 4) {
     31     print_usage(argv[0]);
     32     return 1;
     33   }
     34 
     35   errno = 0;
     36   k = strtoull(argv[1], &ep, 10);
     37   if (argv[1][0] == '\0' || *ep != '\0' ||
     38       (k == ULLONG_MAX && errno == ERANGE)) {
     39     fprintf(stderr,
     40             "Could not interpret k as a 64 bit integer in base 10.");
     41     return 1;
     42   }
     43 
     44   errno = 0;
     45   m = strtoull(argv[2], &ep, 10);
     46   if (argv[2][0] == '\0' || *ep != '\0' ||
     47       (m == ULLONG_MAX && errno == ERANGE)) {
     48     fprintf(stderr,
     49             "Could not interpret m as a 64 bit integer in base 10.");
     50     return 1;
     51   }
     52 
     53   errno = 0;
     54   n = strtoull(argv[3], &ep, 10);
     55   if (argv[3][0] == '\0' || *ep != '\0' ||
     56       (n == ULLONG_MAX && errno == ERANGE)) {
     57     fprintf(stderr,
     58             "Could not interpret n as a 64 bit integer in base 10.");
     59     return 1;
     60   }
     61 
     62   printf("[+] Running, with\n");
     63   printf("  k = %llu, m = %llu, n = %llu\n", k, m, n);
     64 
     65   bloom_init(&bloom, k, m);
     66 
     67   printf("[+] Generating n random %lld bit integers...\n", BIT_SIZE);
     68   flint_rand_t state;
     69   flint_randinit(state);
     70 
     71   fmpz *v = _fmpz_vec_init(n);
     72   for (i = 0; i < n; i++) {
     73     fmpz_randtest_unsigned(&v[i], state, BIT_SIZE);
     74   }
     75 
     76   printf("[+] Inserting the numbers in the Bloom filter...\n");
     77   for (i = 0; i < n; i++) {
     78     bloom_insert(&bloom, &v[i]);
     79   }
     80 
     81   printf("[+] Testing for the inserted numbers...\n");
     82   for (i = 0; i < n; i++) {
     83     if (!bloom_prob_contains(&bloom, &v[i])) {
     84       fprintf(stderr, "This is not a bloom filter, %zu\n", i);
     85       return 1;
     86     }
     87   }
     88 
     89   fmpz_t t;
     90   fmpz_init(t);
     91 
     92   printf("[+] Testing the rate of false positives...\n");
     93   size_t loops = 0;
     94   size_t false_pos = 0;
     95   int inlist;
     96   while (1) {
     97     fmpz_randtest_unsigned(t, state, BIT_SIZE);
     98     inlist = 0;
     99     for (i = 0; i < n; i++) {
    100       if (fmpz_cmp(t, &v[i]) == 0) {
    101         inlist = 1;
    102         break;
    103       }
    104     }
    105 
    106     if (inlist) {
    107       continue;
    108     }
    109 
    110     if (bloom_prob_contains(&bloom, t)) {
    111       false_pos++;
    112     }
    113 
    114     loops++;
    115     if (loops % 100000 == 0) {
    116       double x = (double)false_pos / (double)loops;
    117       printf("%zu out of %zu (%llf per cent) false positive\n",
    118              false_pos, loops, x * 100.0);
    119     }
    120   }
    121 
    122   fmpz_clear(t);
    123   flint_randclear(state);
    124 
    125   bloom_clear(&bloom);
    126   _fmpz_vec_clear(v, n);
    127 
    128   return 0;
    129 }