lib/random.c

   1 /*
   2  * Copyright (C) 2012, 2013 Gregor Pintar <grpintar@gmail.com>
   3  *
   4  * Permission is granted to deal in this work without any restriction,
   5  * including unlimited rights to use, publicly perform, publish,
   6  * reproduce, relicence, modify, merge, and/or distribute in any form,
   7  * for any purpose, with or without fee, and by any means.
   8  *
   9  * This work is provided "AS IS" and WITHOUT WARRANTY of any kind,
  10  * to the utmost extent permitted by applicable law. In no event
  11  * shall a licensor, author or contributor be held liable for any
  12  * issues arising in any way out of dealing in the work.
  13  */
  14
  15 #include <assert.h>
  16
  17 #if defined(KRIPTO_UNIX)
  18
  19 #ifndef KRIPTO_DEV_RANDOM
  20 #define KRIPTO_DEV_RANDOM "/dev/urandom"
  21 #endif
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25
  26 #elif defined(KRIPTO_WINDOWS)
  27
  28 #if !defined(KRIPTO_RTLGENRANDOM) && !defined(KRIPTO_CRYPTGENRANDOM)
  29 #define KRIPTO_RTLGENRANDOM
  30 #endif
  31
  32 #include <windows.h>
  33
  34 #if defined(KRIPTO_RTLGENRANDOM)
  35 #include <stdlib.h>
  36 struct kripto_random
  37 {
  38         HMODULE lib;
  39         FARPROC rtlgenrandom;
  40 };
  41 #elif defined(KRIPTO_CRYPTGENRANDOM)
  42 #include <wincrypt.h>
  43 #endif
  44
  45 #else
  46
  47 #ifndef KRIPTO_RESEED_OUTPUT
  48 #define KRIPTO_RESEED_OUTPUT 5242880 /* 5MB */
  49 #endif
  50
  51 #ifndef KRIPTO_RESEED_TIME
  52 #define KRIPTO_RESEED_TIME 300 /* 5 min */
  53 #endif
  54
  55 #include <stdlib.h>
  56 #include <time.h>
  57
  58 /*#ifdef KRIPTO_UNIX
  59 #include <sys/time.h>
  60 #include <sys/resource.h>
  61 #endif*/
  62
  63 #include <kripto/memwipe.h>
  64 #include <kripto/stream.h>
  65 #include <kripto/scrypt.h>
  66 #include <kripto/stream/chacha.h>
  67 #include <kripto/mac.h>
  68 #include <kripto/mac.h>
  69 #include <kripto/mac/hmac.h>
  70 #include <kripto/hash.h>
  71 #include <kripto/hash/blake2s.h>
  72
  73 struct kripto_random
  74 {
  75         kripto_stream *stream;
  76         kripto_mac_desc *mac;
  77         time_t time;
  78         size_t output;
  79 };
  80
  81 #endif
  82
  83 #include <stdint.h>
  84 #include <string.h>
  85 #include <math.h>
  86
  87 #include <kripto/random.h>
  88
  89 #if !defined(KRIPTO_WINDOWS) && !defined(KRIPTO_UNIX)
  90
  91 static int seed(kripto_random *s, uint8_t *out, unsigned int len)
  92 {
  93         struct
  94         {
  95                 #if defined(KRIPTO_UNIX)
  96                 int pid;
  97                 struct timespec time;
  98                 struct rusage usage;
  99                 #else
 100                 time_t time;
 101                 clock_t clock;
 102                 #endif
 103                 uint8_t unassigned[4];
 104         } entropy;
 105
 106         s->mac = kripto_mac_hmac(kripto_hash_blake2s);
 107         if(!s->mac) return -1;
 108
 109         #if defined(KRIPTO_UNIX)
 110         entropy.pid = getpid();
 111         (void)clock_gettime(CLOCK_REALTIME, &entropy.time);
 112         (void)getrusage(RUSAGE_SELF, &entropy.usage);
 113         #else
 114         entropy.time = time(NULL);
 115         entropy.clock = clock();
 116         #endif
 117
 118         if(kripto_scrypt
 119         (
 120                 s->mac, 0,
 121                 1048576, 8, 1,
 122                 &entropy, sizeof(entropy),
 123                 0, 0,
 124                 out, len
 125         )) return -1;
 126
 127         memcpy(entropy.unassigned, &s, 4);
 128
 129         #if defined(KRIPTO_UNIX)
 130         (void)clock_gettime(CLOCK_REALTIME, &entropy.time);
 131         (void)getrusage(RUSAGE_SELF, &entropy.usage);
 132         #else
 133         entropy.time = time(NULL);
 134         entropy.clock = clock();
 135         #endif
 136
 137         if(kripto_scrypt
 138         (
 139                 s->mac, 0,
 140                 1048576, 8, 1,
 141                 &entropy, sizeof(entropy),
 142                 out, len,
 143                 out, len
 144         )) return -1;
 145
 146         kripto_memwipe(&entropy, sizeof(entropy));
 147
 148         s->output = 0;
 149         s->time = time(NULL);
 150
 151         return 0;
 152 }
 153
 154 static kripto_random *create(void)
 155 {
 156         kripto_random *s;
 157         uint8_t buf[32];
 158
 159         s = malloc(sizeof(kripto_random));
 160         if(!s) return 0;
 161
 162         if(seed(s, buf, 32)) goto err;
 163
 164         s->stream = kripto_stream_create
 165         (
 166                 kripto_stream_chacha, 0,
 167                 buf, 32,
 168                 0, 0
 169         );
 170         if(!s->stream) goto err;
 171
 172         return s;
 173
 174 err:
 175         free(s);
 176         return 0;
 177 }
 178
 179 #endif
 180
 181 kripto_random *kripto_random_create(void)
 182 {
 183         #if defined(KRIPTO_DEV_RANDOM)
 184
 185         const char *dev_random;
 186         /*FILE *fp;*/
 187
 188         dev_random = getenv("KRIPTO_RANDOM");
 189         if(!dev_random)
 190                 #ifdef KRIPTO_DEV_RANDOM
 191                 dev_random = KRIPTO_DEV_RANDOM;
 192                 #else
 193                 return create();
 194                 #endif
 195
 196         return (kripto_random *)fopen(dev_random, "rb");
 197
 198         /*fp = fopen(dev_random, "rb");
 199         if(fp) return (kripto_random *)fp;
 200         else return create();*/
 201
 202         #elif defined(KRIPTO_RTLGENRANDOM)
 203
 204         kripto_random *s;
 205
 206         s = malloc(sizeof(kripto_random));
 207         if(!s) return 0;
 208
 209         s->lib = LoadLibrary("advapi32.dll");
 210         if(!s->lib)
 211         {
 212                 free(s);
 213                 return 0;
 214         }
 215
 216         s->rtlgenrandom = GetProcAddress(s->lib, "SystemFunction036");
 217         if(!s->rtlgenrandom)
 218         {
 219                 FreeLibrary(s->lib);
 220                 free(s);
 221                 return 0;
 222         }
 223
 224         return s;
 225
 226         #elif defined(KRIPTO_CRYPTGENRANDOM)
 227         #if sizeof(kripto_random *) < sizeof(HCRYPTPROV)
 228         #error sizeof(kripto_random *) < sizeof(HCRYPTPROV)
 229         #endif
 230
 231         HCRYPTPROV prov = 0;
 232
 233         if(!CryptAcquireContext
 234         (
 235                 &prov,
 236                 NULL,
 237                 NULL,
 238                 PROV_RSA_FULL,
 239                 CRYPT_VERIFYCONTEXT | CRYPT_SILENT
 240         )) return 0;
 241
 242         return (kripto_random *)prov;
 243
 244         #else
 245
 246         return create();
 247
 248         #endif
 249 }
 250
 251 size_t kripto_random_gen(kripto_random *s, void *out, size_t len)
 252 {
 253         assert(s);
 254
 255         #if defined(KRIPTO_DEV_RANDOM)
 256
 257         return fread(out, sizeof(char), len, (FILE *)s);
 258
 259         #elif defined(KRIPTO_RTLGENRANDOM)
 260
 261         assert(s->rtlgenrandom);
 262         if(s->rtlgenrandom(out, len) == TRUE) return len;
 263         return 0;
 264
 265         #elif defined(KRIPTO_CRYPTGENRANDOM)
 266
 267         if(CryptGenRandom((HCRYPTPROV)s, len, out)) return len;
 268         return 0;
 269
 270         #else
 271
 272         uint8_t buf[32];
 273         uint8_t iv[8];
 274
 275         s->output += len;
 276
 277         if /* reseed */
 278         (
 279                 s->output > KRIPTO_RESEED_OUTPUT ||
 280                 time(NULL) - s->time > KRIPTO_RESEED_TIME
 281         )
 282         {
 283                 kripto_stream_prng(s->stream, iv, 8);
 284
 285                 if(seed(s, buf, 32)) goto err;
 286
 287                 s->stream = kripto_stream_recreate
 288                 (
 289                         s->stream, 0,
 290                         buf, 32,
 291                         iv, 8
 292                 );
 293                 if(!s->stream) goto err;
 294         }
 295
 296         kripto_stream_prng(s->stream, out, len);
 297
 298         return len;
 299
 300 err:
 301         kripto_memwipe(s, sizeof(kripto_random));
 302         free(s);
 303         return 0;
 304
 305         #endif
 306 }
 307
 308 void kripto_random_destroy(kripto_random *s)
 309 {
 310         assert(s);
 311
 312         #if defined(KRIPTO_DEV_RANDOM)
 313
 314         fclose((FILE *)s);
 315
 316         #elif defined(KRIPTO_RTLGENRANDOM)
 317
 318         assert(s->lib);
 319         FreeLibrary(s->lib);
 320
 321         #elif defined(KRIPTO_CRYPTGENRANDOM)
 322
 323         CryptReleaseContext((HCRYPTPROV)s, 0);
 324
 325         #else
 326
 327         kripto_stream_destroy(s->stream);
 328         free(s->mac);
 329
 330         kripto_memwipe(s, sizeof(kripto_random));
 331         free(s);
 332
 333         #endif
 334 }
 335
 336 #if !defined(__STDC_VERSION__) || __STDC_VERSION__ < 199901L || \
 337         (defined(__cplusplus) && __cplusplus < 201103L)
 338
 339 #define LOG2(X) (log(X) / log(2))
 340 #else
 341 #define LOG2(X) log2(X)
 342 #endif
 343
 344 static unsigned int bitcount(const uint8_t x)
 345 {
 346         unsigned int c = 0;
 347         uint8_t mask;
 348
 349         for(mask = 0x80; mask; mask >>= 1)
 350                 if(x & mask) c++;
 351
 352         return c;
 353 }
 354
 355 static unsigned int bitflips(const uint8_t prev, const uint8_t x)
 356 {
 357         unsigned int c = 0;
 358         uint8_t p = 0;
 359         uint8_t mask;
 360
 361         p = prev;
 362
 363         for(mask = 0x80; mask; mask >>= 1)
 364         {
 365                 if(!p && (x & mask))
 366                 {
 367                         p = 1;
 368                         c++;
 369                 }
 370                 else if(p && !(x & mask))
 371                 {
 372                         p = 0;
 373                         c++;
 374                 }
 375         }
 376
 377         return c;
 378 }
 379
 380 int kripto_random_test(kripto_random *s)
 381 {
 382         uint8_t sample[4096];
 383         unsigned int count[256];
 384         uint8_t prev = 0;
 385         double ent = 0.0;
 386         double chi = 0.0;
 387         double avg = 0.0;
 388         double avg_null = 0.0;
 389         unsigned int bits = 0;
 390         unsigned int bit_flips = 0;
 391
 392         /* distances */
 393         unsigned int dist[256];
 394         unsigned int dist_prev[256];
 395         unsigned int dist_zero = 0;
 396
 397         /* serial correlation */
 398         double corr;
 399         double corr1 = 0;
 400         double corr2 = 0;
 401         double corr3 = 0;
 402
 403         double t;
 404         unsigned int i;
 405
 406         if(kripto_random_gen(s, sample, 4096) != 4096) return 0;
 407
 408         memset(count, 0, sizeof(unsigned int) * 256);
 409         memset(dist, 0, sizeof(unsigned int) * 256);
 410         memset(dist_prev, 0, sizeof(unsigned int) * 256);
 411
 412         for(i = 0; i < 4096; i++)
 413         {
 414                 count[sample[i]]++;
 415
 416                 bits += bitcount(sample[i]);
 417
 418                 bit_flips += bitflips(prev & 1, sample[i]);
 419
 420                 /* distances */
 421                 if(prev == sample[i]) dist_zero++;
 422                 dist[sample[i]] += 4096 - dist_prev[sample[i]];
 423                 dist_prev[sample[i]] = 4096;
 424
 425                 /* serial correlation */
 426                 corr1 += prev * sample[i];
 427                 corr2 += sample[i];
 428                 corr3 += sample[i] * sample[i];
 429
 430                 prev = sample[i];
 431         }
 432
 433         for(i = 0; i < 256; i++)
 434         {
 435                 /* chi square */
 436                 t = count[i] - 16;
 437                 chi += t * t;
 438
 439                 /* entropy */
 440                 t = (double)count[i] / 4096.0;
 441                 if(t) ent -= t * LOG2(t);
 442
 443                 /* arithmetic mean */
 444                 avg += i * count[i];
 445
 446                 /* average null distance */
 447                 if(count[i]) avg_null += dist[i] / (double)count[i];
 448         }
 449         chi /= 16;
 450         avg /= 4096;
 451
 452         /* serial correlation */
 453         corr2 = corr2 * corr2;
 454         corr = (double)(4096 * corr1 - corr2)
 455                 / (double)(4096 * corr3 - corr2);
 456         if(corr < 0.0) corr = -corr; /* absolute */
 457
 458         /* check */
 459         if(ent < 7.9) return 0;
 460         if(avg < 125 || avg > 130.5) return 0;
 461         t = bits / 32768.0;
 462         if(t < 0.49 || t > 0.51) return 0;
 463         if(chi < 192 || chi > 320) return 0;
 464         t = bit_flips / 32768.0;
 465         if(t < 0.49 || t > 0.51) return 0;
 466         if(avg_null < 192 || avg_null > 320) return 0;
 467         if(dist_zero / 4096.0 > 0.1) return 0;
 468         if(corr > 0.1) return 0;
 469
 470         return -1;
 471 }