lib/random.c

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