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