1#include <assert.h>
  2#include <stdint.h>
  3#include <string.h>
  4#include <unistd.h>
  5#include <stdlib.h>
  6
  7#define RNG_RESERVE_LEN 512
  8
  9#define CHACHA20_KEYBYTES 32
 10#define CHACHA20_BLOCKBYTES 64
 11
 12#define ROTL32(x, b) (uint32_t)(((x) << (b)) | ((x) >> (32 - (b))))
 13
 14#define CHACHA20_QUARTERROUND(A, B, C, D) \
 15    A += B;                               \
 16    D = ROTL32(D ^ A, 16);                \
 17    C += D;                               \
 18    B = ROTL32(B ^ C, 12);                \
 19    A += B;                               \
 20    D = ROTL32(D ^ A, 8);                 \
 21    C += D;                               \
 22    B = ROTL32(B ^ C, 7)
 23
 24static void CHACHA20_ROUNDS(uint32_t st[16])
 25{
 26    int i;
 27
 28    for (i = 0; i < 20; i += 2) {
 29        CHACHA20_QUARTERROUND(st[0], st[4], st[8], st[12]);
 30        CHACHA20_QUARTERROUND(st[1], st[5], st[9], st[13]);
 31        CHACHA20_QUARTERROUND(st[2], st[6], st[10], st[14]);
 32        CHACHA20_QUARTERROUND(st[3], st[7], st[11], st[15]);
 33        CHACHA20_QUARTERROUND(st[0], st[5], st[10], st[15]);
 34        CHACHA20_QUARTERROUND(st[1], st[6], st[11], st[12]);
 35        CHACHA20_QUARTERROUND(st[2], st[7], st[8], st[13]);
 36        CHACHA20_QUARTERROUND(st[3], st[4], st[9], st[14]);
 37    }
 38}
 39
 40static void chacha20_update(uint8_t out[CHACHA20_BLOCKBYTES], uint32_t st[16])
 41{
 42    uint32_t ks[16];
 43    int i;
 44
 45    memcpy(ks, st, 4 * 16);
 46    CHACHA20_ROUNDS(st);
 47    for (i = 0; i < 16; i++) {
 48        ks[i] += st[i];
 49    }
 50    memcpy(out, ks, CHACHA20_BLOCKBYTES);
 51    st[12]++;
 52}
 53
 54static void chacha20_init(uint32_t st[16], const uint8_t key[CHACHA20_KEYBYTES])
 55{
 56    static const uint32_t constants[4] = { 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574 };
 57    memcpy(&st[0], constants, 4 * 4);
 58    memcpy(&st[4], key, CHACHA20_KEYBYTES);
 59    memset(&st[12], 0, 4 * 4);
 60}
 61
 62static int chacha20_rng(uint8_t* out, size_t len, uint8_t key[CHACHA20_KEYBYTES])
 63{
 64    uint32_t st[16];
 65    size_t off;
 66
 67    chacha20_init(st, key);
 68    chacha20_update(&out[0], st);
 69    memcpy(key, out, CHACHA20_KEYBYTES);
 70    off = 0;
 71    while (len >= CHACHA20_BLOCKBYTES) {
 72        chacha20_update(&out[off], st);
 73        len -= CHACHA20_BLOCKBYTES;
 74        off += CHACHA20_BLOCKBYTES;
 75    }
 76    if (len > 0) {
 77        uint8_t tmp[CHACHA20_BLOCKBYTES];
 78        chacha20_update(tmp, st);
 79        memcpy(&out[off], tmp, len);
 80    }
 81    return 0;
 82}
 83
 84struct rng_state {
 85    int initialized;
 86    size_t off;
 87    uint8_t key[CHACHA20_KEYBYTES];
 88    uint8_t reserve[RNG_RESERVE_LEN];
 89};
 90
 91void arc4random_buf(void* buffer, size_t len)
 92{
 93    static _Thread_local struct rng_state rng_state;
 94
 95    unsigned char* buffer_ = (unsigned char*)buffer;
 96    size_t off;
 97    size_t remaining;
 98    size_t partial;
 99
100    if (!rng_state.initialized) {
101        if (getentropy(rng_state.key, sizeof rng_state.key) != 0) {
102            assert(0);
103        }
104        rng_state.off = RNG_RESERVE_LEN;
105        rng_state.initialized = 1;
106    }
107    off = 0;
108    remaining = len;
109    while (remaining > 0) {
110        if (rng_state.off == RNG_RESERVE_LEN) {
111            while (remaining >= RNG_RESERVE_LEN) {
112                chacha20_rng(&buffer_[off], RNG_RESERVE_LEN, rng_state.key);
113                off += RNG_RESERVE_LEN;
114                remaining -= RNG_RESERVE_LEN;
115            }
116            if (remaining == 0) {
117                break;
118            }
119            chacha20_rng(&rng_state.reserve[0], RNG_RESERVE_LEN, rng_state.key);
120            rng_state.off = 0;
121        }
122        partial = RNG_RESERVE_LEN - rng_state.off;
123        if (remaining < partial) {
124            partial = remaining;
125        }
126        memcpy(&buffer_[off], &rng_state.reserve[rng_state.off], partial);
127        memset(&rng_state.reserve[rng_state.off], 0, partial);
128        rng_state.off += partial;
129        remaining -= partial;
130        off += partial;
131    }
132}
133
134uint32_t arc4random(void)
135{
136    uint32_t v;
137
138    arc4random_buf(&v, sizeof v);
139
140    return v;
141}
142
143uint32_t arc4random_uniform(const uint32_t upper_bound)
144{
145    uint32_t min;
146    uint32_t r;
147
148    if (upper_bound < 2U) {
149        return 0;
150    }
151    min = (1U + ~upper_bound) % upper_bound; // = 2**32 mod upper_bound
152    do {
153        r = arc4random();
154    } while (r < min);
155
156    // r is now clamped to a set whose size mod upper_bound == 0.
157    // The worst case (2**31+1) requires 2 attempts on average.
158
159    return r % upper_bound;
160}