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}