1 /* OPENBSD ORIGINAL: lib/libc/crypto/arc4random.c */
2
3 /* $OpenBSD: arc4random.c,v 1.25 2013/10/01 18:34:57 markus Exp $ */
4
5 /*
6 * Copyright (c) 1996, David Mazieres <dm@uun.org>
7 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
8 * Copyright (c) 2013, Markus Friedl <markus@openbsd.org>
9 *
10 * Permission to use, copy, modify, and distribute this software for any
11 * purpose with or without fee is hereby granted, provided that the above
12 * copyright notice and this permission notice appear in all copies.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
15 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
16 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
17 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
18 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
19 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
20 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 */
22
23 /*
24 * ChaCha based random number generator for OpenBSD.
25 */
26
27 #include "includes.h"
28
29 #include <stdlib.h>
30 #include <string.h>
31 #include <unistd.h>
32 #include <sys/types.h>
33
34 #ifndef HAVE_ARC4RANDOM
35
36 #include <openssl/rand.h>
37 #include <openssl/err.h>
38
39 #include "log.h"
40
41 #define KEYSTREAM_ONLY
42 #include "chacha_private.h"
43
44 #ifdef __GNUC__
45 #define inline __inline
46 #else /* !__GNUC__ */
47 #define inline
48 #endif /* !__GNUC__ */
49
50 /* OpenSMTPD isn't multithreaded */
51 #define _ARC4_LOCK()
52 #define _ARC4_UNLOCK()
53
54 #define KEYSZ 32
55 #define IVSZ 8
56 #define BLOCKSZ 64
57 #define RSBUFSZ (16*BLOCKSZ)
58 static int rs_initialized;
59 static pid_t rs_stir_pid;
60 static chacha_ctx rs; /* chacha context for random keystream */
61 static unsigned char rs_buf[RSBUFSZ]; /* keystream blocks */
62 static size_t rs_have; /* valid bytes at end of rs_buf */
63 static size_t rs_count; /* bytes till reseed */
64
65 static inline void _rs_rekey(unsigned char *dat, size_t datlen);
66
67 static inline void
_rs_init(unsigned char * buf,size_t n)68 _rs_init(unsigned char *buf, size_t n)
69 {
70 if (n < KEYSZ + IVSZ)
71 return;
72 chacha_keysetup(&rs, buf, KEYSZ * 8, 0);
73 chacha_ivsetup(&rs, buf + KEYSZ);
74 }
75
76 static void
_rs_stir(void)77 _rs_stir(void)
78 {
79 unsigned char rnd[KEYSZ + IVSZ];
80
81 if (RAND_bytes(rnd, sizeof(rnd)) <= 0)
82 fatal("Couldn't obtain random bytes (error %ld)",
83 ERR_get_error());
84
85 if (!rs_initialized) {
86 rs_initialized = 1;
87 _rs_init(rnd, sizeof(rnd));
88 } else
89 _rs_rekey(rnd, sizeof(rnd));
90 memset(rnd, 0, sizeof(rnd));
91
92 /* invalidate rs_buf */
93 rs_have = 0;
94 memset(rs_buf, 0, RSBUFSZ);
95
96 rs_count = 1600000;
97 }
98
99 static inline void
_rs_stir_if_needed(size_t len)100 _rs_stir_if_needed(size_t len)
101 {
102 pid_t pid = getpid();
103
104 if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) {
105 rs_stir_pid = pid;
106 _rs_stir();
107 } else
108 rs_count -= len;
109 }
110
111 static inline void
_rs_rekey(unsigned char * dat,size_t datlen)112 _rs_rekey(unsigned char *dat, size_t datlen)
113 {
114 #ifndef KEYSTREAM_ONLY
115 memset(rs_buf, 0,RSBUFSZ);
116 #endif
117 /* fill rs_buf with the keystream */
118 chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ);
119 /* mix in optional user provided data */
120 if (dat) {
121 size_t i, m;
122
123 m = MIN(datlen, KEYSZ + IVSZ);
124 for (i = 0; i < m; i++)
125 rs_buf[i] ^= dat[i];
126 }
127 /* immediately reinit for backtracking resistance */
128 _rs_init(rs_buf, KEYSZ + IVSZ);
129 memset(rs_buf, 0, KEYSZ + IVSZ);
130 rs_have = RSBUFSZ - KEYSZ - IVSZ;
131 }
132
133 static inline void
_rs_random_buf(void * _buf,size_t n)134 _rs_random_buf(void *_buf, size_t n)
135 {
136 unsigned char *buf = (unsigned char *)_buf;
137 size_t m;
138
139 _rs_stir_if_needed(n);
140 while (n > 0) {
141 if (rs_have > 0) {
142 m = MIN(n, rs_have);
143 memcpy(buf, rs_buf + RSBUFSZ - rs_have, m);
144 memset(rs_buf + RSBUFSZ - rs_have, 0, m);
145 buf += m;
146 n -= m;
147 rs_have -= m;
148 }
149 if (rs_have == 0)
150 _rs_rekey(NULL, 0);
151 }
152 }
153
154 static inline void
_rs_random_u32(uint32_t * val)155 _rs_random_u32(uint32_t *val)
156 {
157 _rs_stir_if_needed(sizeof(*val));
158 if (rs_have < sizeof(*val))
159 _rs_rekey(NULL, 0);
160 memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val));
161 memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val));
162 rs_have -= sizeof(*val);
163 return;
164 }
165
166 void
arc4random_stir(void)167 arc4random_stir(void)
168 {
169 _ARC4_LOCK();
170 _rs_stir();
171 _ARC4_UNLOCK();
172 }
173
174 void
arc4random_addrandom(unsigned char * dat,int datlen)175 arc4random_addrandom(unsigned char *dat, int datlen)
176 {
177 int m;
178
179 _ARC4_LOCK();
180 if (!rs_initialized)
181 _rs_stir();
182 while (datlen > 0) {
183 m = MIN(datlen, KEYSZ + IVSZ);
184 _rs_rekey(dat, m);
185 dat += m;
186 datlen -= m;
187 }
188 _ARC4_UNLOCK();
189 }
190
191 uint32_t
arc4random(void)192 arc4random(void)
193 {
194 uint32_t val;
195
196 _ARC4_LOCK();
197 _rs_random_u32(&val);
198 _ARC4_UNLOCK();
199 return val;
200 }
201 #endif /* !HAVE_ARC4RANDOM */
202
203 #ifndef HAVE_ARC4RANDOM_UNIFORM
204 /*
205 * Calculate a uniformly distributed random number less than upper_bound
206 * avoiding "modulo bias".
207 *
208 * Uniformity is achieved by generating new random numbers until the one
209 * returned is outside the range [0, 2**32 % upper_bound). This
210 * guarantees the selected random number will be inside
211 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
212 * after reduction modulo upper_bound.
213 */
214 uint32_t
arc4random_uniform(uint32_t upper_bound)215 arc4random_uniform(uint32_t upper_bound)
216 {
217 uint32_t r, min;
218
219 if (upper_bound < 2)
220 return 0;
221
222 /* 2**32 % x == (2**32 - x) % x */
223 min = -upper_bound % upper_bound;
224
225 /*
226 * This could theoretically loop forever but each retry has
227 * p > 0.5 (worst case, usually far better) of selecting a
228 * number inside the range we need, so it should rarely need
229 * to re-roll.
230 */
231 for (;;) {
232 r = arc4random();
233 if (r >= min)
234 break;
235 }
236
237 return r % upper_bound;
238 }
239 #endif /* !HAVE_ARC4RANDOM_UNIFORM */
240
241 #if 0
242 /*-------- Test code for i386 --------*/
243 #include <stdio.h>
244 #include <machine/pctr.h>
245 int
246 main(int argc, char **argv)
247 {
248 const int iter = 1000000;
249 int i;
250 pctrval v;
251
252 v = rdtsc();
253 for (i = 0; i < iter; i++)
254 arc4random();
255 v = rdtsc() - v;
256 v /= iter;
257
258 printf("%qd cycles\n", v);
259 exit(0);
260 }
261 #endif
262