xref: /unit/src/nxt_random.c (revision 138)
10Sigor@sysoev.ru 
20Sigor@sysoev.ru /*
30Sigor@sysoev.ru  * Copyright (C) Igor Sysoev
40Sigor@sysoev.ru  * Copyright (C) NGINX, Inc.
50Sigor@sysoev.ru  */
60Sigor@sysoev.ru 
70Sigor@sysoev.ru 
80Sigor@sysoev.ru #include <nxt_main.h>
90Sigor@sysoev.ru 
100Sigor@sysoev.ru 
110Sigor@sysoev.ru /*
120Sigor@sysoev.ru  * The pseudorandom generator based on OpenBSD arc4random.  Although it is
130Sigor@sysoev.ru  * usually stated that arc4random uses RC4 pseudorandom generation algorithm
140Sigor@sysoev.ru  * they are actually different in nxt_random_add().
150Sigor@sysoev.ru  */
160Sigor@sysoev.ru 
170Sigor@sysoev.ru 
180Sigor@sysoev.ru #define NXT_RANDOM_KEY_SIZE  128
190Sigor@sysoev.ru 
200Sigor@sysoev.ru 
210Sigor@sysoev.ru nxt_inline void nxt_random_start_schedule(nxt_random_t *r);
220Sigor@sysoev.ru static void nxt_random_stir(nxt_random_t *r);
230Sigor@sysoev.ru static void nxt_random_add(nxt_random_t *r, const u_char *key, uint32_t len);
240Sigor@sysoev.ru nxt_inline uint8_t nxt_random_byte(nxt_random_t *r);
250Sigor@sysoev.ru 
260Sigor@sysoev.ru 
270Sigor@sysoev.ru void
280Sigor@sysoev.ru nxt_random_init(nxt_random_t *r)
290Sigor@sysoev.ru {
300Sigor@sysoev.ru     nxt_random_start_schedule(r);
310Sigor@sysoev.ru 
320Sigor@sysoev.ru     nxt_random_stir(r);
330Sigor@sysoev.ru }
340Sigor@sysoev.ru 
350Sigor@sysoev.ru 
360Sigor@sysoev.ru nxt_inline void
370Sigor@sysoev.ru nxt_random_start_schedule(nxt_random_t *r)
380Sigor@sysoev.ru {
390Sigor@sysoev.ru     nxt_uint_t  i;
400Sigor@sysoev.ru 
410Sigor@sysoev.ru     r->i = 0;
420Sigor@sysoev.ru     r->j = 0;
430Sigor@sysoev.ru 
440Sigor@sysoev.ru     for (i = 0; i < 256; i++) {
450Sigor@sysoev.ru         r->s[i] = i;
460Sigor@sysoev.ru     }
470Sigor@sysoev.ru }
480Sigor@sysoev.ru 
490Sigor@sysoev.ru 
500Sigor@sysoev.ru static void
510Sigor@sysoev.ru nxt_random_stir(nxt_random_t *r)
520Sigor@sysoev.ru {
530Sigor@sysoev.ru     int             fd;
540Sigor@sysoev.ru     ssize_t         n;
550Sigor@sysoev.ru     struct timeval  tv;
560Sigor@sysoev.ru     union {
57*138Sigor@sysoev.ru         uint32_t    value[4];
580Sigor@sysoev.ru         u_char      bytes[NXT_RANDOM_KEY_SIZE];
590Sigor@sysoev.ru     } key;
600Sigor@sysoev.ru 
610Sigor@sysoev.ru     n = 0;
620Sigor@sysoev.ru 
630Sigor@sysoev.ru #if (NXT_HAVE_GETRANDOM)
640Sigor@sysoev.ru 
650Sigor@sysoev.ru     /* Linux 3.17 getrandom(). */
660Sigor@sysoev.ru 
670Sigor@sysoev.ru     n = getrandom(key, NXT_RANDOM_KEY_SIZE, 0);
680Sigor@sysoev.ru 
690Sigor@sysoev.ru #endif
700Sigor@sysoev.ru 
710Sigor@sysoev.ru     if (n != NXT_RANDOM_KEY_SIZE) {
720Sigor@sysoev.ru         fd = open("/dev/urandom", O_RDONLY);
730Sigor@sysoev.ru 
740Sigor@sysoev.ru         if (fd >= 0) {
750Sigor@sysoev.ru             n = read(fd, &key, NXT_RANDOM_KEY_SIZE);
760Sigor@sysoev.ru             (void) close(fd);
770Sigor@sysoev.ru         }
780Sigor@sysoev.ru     }
790Sigor@sysoev.ru 
800Sigor@sysoev.ru     if (n != NXT_RANDOM_KEY_SIZE) {
810Sigor@sysoev.ru         (void) gettimeofday(&tv, NULL);
820Sigor@sysoev.ru 
830Sigor@sysoev.ru         /* XOR with stack garbage. */
840Sigor@sysoev.ru 
850Sigor@sysoev.ru         key.value[0] ^= tv.tv_usec;
860Sigor@sysoev.ru         key.value[1] ^= tv.tv_sec;
870Sigor@sysoev.ru         key.value[2] ^= nxt_pid;
88*138Sigor@sysoev.ru         key.value[3] ^= nxt_thread_tid(NULL);
890Sigor@sysoev.ru     }
900Sigor@sysoev.ru 
910Sigor@sysoev.ru     nxt_random_add(r, key.bytes, NXT_RANDOM_KEY_SIZE);
920Sigor@sysoev.ru 
930Sigor@sysoev.ru     /* Drop the first 3072 bytes. */
940Sigor@sysoev.ru     for (n = 3072; n != 0; n--) {
950Sigor@sysoev.ru         (void) nxt_random_byte(r);
960Sigor@sysoev.ru     }
970Sigor@sysoev.ru 
980Sigor@sysoev.ru     /* Stir again after 1,600,000 bytes. */
990Sigor@sysoev.ru     r->count = 400000;
1000Sigor@sysoev.ru }
1010Sigor@sysoev.ru 
1020Sigor@sysoev.ru 
1030Sigor@sysoev.ru static void
1040Sigor@sysoev.ru nxt_random_add(nxt_random_t *r, const u_char *key, uint32_t len)
1050Sigor@sysoev.ru {
1060Sigor@sysoev.ru     uint8_t   val;
1070Sigor@sysoev.ru     uint32_t  n;
1080Sigor@sysoev.ru 
1090Sigor@sysoev.ru     for (n = 0; n < 256; n++) {
1100Sigor@sysoev.ru         val = r->s[r->i];
1110Sigor@sysoev.ru         r->j += val + key[n % len];
1120Sigor@sysoev.ru 
1130Sigor@sysoev.ru         r->s[r->i] = r->s[r->j];
1140Sigor@sysoev.ru         r->s[r->j] = val;
1150Sigor@sysoev.ru 
1160Sigor@sysoev.ru         r->i++;
1170Sigor@sysoev.ru     }
1180Sigor@sysoev.ru 
1190Sigor@sysoev.ru     /* This index is not decremented in RC4 algorithm. */
1200Sigor@sysoev.ru     r->i--;
1210Sigor@sysoev.ru 
1220Sigor@sysoev.ru     r->j = r->i;
1230Sigor@sysoev.ru }
1240Sigor@sysoev.ru 
1250Sigor@sysoev.ru 
1260Sigor@sysoev.ru uint32_t
1270Sigor@sysoev.ru nxt_random(nxt_random_t *r)
1280Sigor@sysoev.ru {
1290Sigor@sysoev.ru     uint32_t  val;
1300Sigor@sysoev.ru 
1310Sigor@sysoev.ru     r->count--;
1320Sigor@sysoev.ru 
1330Sigor@sysoev.ru     if (r->count <= 0) {
1340Sigor@sysoev.ru         nxt_random_stir(r);
1350Sigor@sysoev.ru     }
1360Sigor@sysoev.ru 
1370Sigor@sysoev.ru     val  = nxt_random_byte(r) << 24;
1380Sigor@sysoev.ru     val |= nxt_random_byte(r) << 16;
1390Sigor@sysoev.ru     val |= nxt_random_byte(r) << 8;
1400Sigor@sysoev.ru     val |= nxt_random_byte(r);
1410Sigor@sysoev.ru 
1420Sigor@sysoev.ru     return val;
1430Sigor@sysoev.ru }
1440Sigor@sysoev.ru 
1450Sigor@sysoev.ru 
1460Sigor@sysoev.ru nxt_inline uint8_t
1470Sigor@sysoev.ru nxt_random_byte(nxt_random_t *r)
1480Sigor@sysoev.ru {
1490Sigor@sysoev.ru     uint8_t  si, sj;
1500Sigor@sysoev.ru 
1510Sigor@sysoev.ru     r->i++;
1520Sigor@sysoev.ru     si = r->s[r->i];
1530Sigor@sysoev.ru     r->j += si;
1540Sigor@sysoev.ru 
1550Sigor@sysoev.ru     sj = r->s[r->j];
1560Sigor@sysoev.ru     r->s[r->i] = sj;
1570Sigor@sysoev.ru     r->s[r->j] = si;
1580Sigor@sysoev.ru 
1590Sigor@sysoev.ru     si += sj;
1600Sigor@sysoev.ru 
1610Sigor@sysoev.ru     return r->s[si];
1620Sigor@sysoev.ru }
1630Sigor@sysoev.ru 
1640Sigor@sysoev.ru 
1650Sigor@sysoev.ru #if (NXT_LIB_UNIT_TEST)
1660Sigor@sysoev.ru 
1670Sigor@sysoev.ru nxt_int_t
1680Sigor@sysoev.ru nxt_random_unit_test(nxt_thread_t *thr)
1690Sigor@sysoev.ru {
1700Sigor@sysoev.ru     nxt_uint_t    n;
1710Sigor@sysoev.ru     nxt_random_t  r;
1720Sigor@sysoev.ru 
1730Sigor@sysoev.ru     nxt_random_start_schedule(&r);
1740Sigor@sysoev.ru 
1750Sigor@sysoev.ru     r.count = 400000;
1760Sigor@sysoev.ru 
1770Sigor@sysoev.ru     nxt_random_add(&r, (u_char *) "arc4random", sizeof("arc4random") - 1);
1780Sigor@sysoev.ru 
1790Sigor@sysoev.ru     /*
1800Sigor@sysoev.ru      * Test arc4random() numbers.
1810Sigor@sysoev.ru      * RC4 pseudorandom numbers would be 0x4642AFC3 and 0xBAF0FFF0.
1820Sigor@sysoev.ru      */
1830Sigor@sysoev.ru 
1840Sigor@sysoev.ru     if (nxt_random(&r) == 0xD6270B27) {
1850Sigor@sysoev.ru 
1860Sigor@sysoev.ru         for (n = 100000; n != 0; n--) {
1870Sigor@sysoev.ru             (void) nxt_random(&r);
1880Sigor@sysoev.ru         }
1890Sigor@sysoev.ru 
1900Sigor@sysoev.ru         if (nxt_random(&r) == 0x6FCAE186) {
1910Sigor@sysoev.ru             nxt_log_error(NXT_LOG_NOTICE, thr->log,
1920Sigor@sysoev.ru                           "arc4random unit test passed");
1930Sigor@sysoev.ru 
1940Sigor@sysoev.ru             return NXT_OK;
1950Sigor@sysoev.ru         }
1960Sigor@sysoev.ru     }
1970Sigor@sysoev.ru 
1980Sigor@sysoev.ru     nxt_log_error(NXT_LOG_NOTICE, thr->log, "arc4random unit test failed");
1990Sigor@sysoev.ru 
2000Sigor@sysoev.ru     return NXT_ERROR;
2010Sigor@sysoev.ru }
2020Sigor@sysoev.ru 
2030Sigor@sysoev.ru #endif
204