arc4random.c (3611ec604864a7d4dcc9a3ea898c80eb35eef8a0) arc4random.c (c1e80940f3b4030df0aaed73028053af057e476d)
1/* $OpenBSD: arc4random.c,v 1.24 2013/06/11 16:59:50 deraadt Exp $ */
1/* $OpenBSD: arc4random.c,v 1.54 2015/09/13 08:31:47 guenther Exp $ */
2
3/*
4 * Copyright (c) 1996, David Mazieres <dm@uun.org>
5 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
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 * Copyright (c) 2014, Theo de Raadt <deraadt@openbsd.org>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19
20/*
8 *
9 * Permission to use, copy, modify, and distribute this software for any
10 * purpose with or without fee is hereby granted, provided that the above
11 * copyright notice and this permission notice appear in all copies.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
16 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
18 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
19 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 */
21
22/*
21 * Arc4 random number generator for OpenBSD.
22 *
23 * This code is derived from section 17.1 of Applied Cryptography,
24 * second edition, which describes a stream cipher allegedly
25 * compatible with RSA Labs "RC4" cipher (the actual description of
26 * which is a trade secret). The same algorithm is used as a stream
27 * cipher called "arcfour" in Tatu Ylonen's ssh package.
28 *
29 * RC4 is a registered trademark of RSA Laboratories.
23 * ChaCha based random number generator for OpenBSD.
30 */
31
32#include <sys/cdefs.h>
33__FBSDID("$FreeBSD$");
34
35#include "namespace.h"
36#include <fcntl.h>
37#include <limits.h>
24 */
25
26#include <sys/cdefs.h>
27__FBSDID("$FreeBSD$");
28
29#include "namespace.h"
30#include <fcntl.h>
31#include <limits.h>
32#include <pthread.h>
33#include <signal.h>
34#include <stdint.h>
38#include <stdlib.h>
35#include <stdlib.h>
36#include <string.h>
39#include <unistd.h>
37#include <unistd.h>
40#include <sys/param.h>
41#include <sys/sysctl.h>
38#include <sys/types.h>
42#include <sys/time.h>
39#include <sys/time.h>
43#include <pthread.h>
44
40
45#include "libc_private.h"
46#include "un-namespace.h"
47
41#include "libc_private.h"
42#include "un-namespace.h"
43
48#ifdef __GNUC__
44#define KEYSTREAM_ONLY
45#include "chacha.c"
46
47#define minimum(a, b) ((a) < (b) ? (a) : (b))
48
49#if defined(__GNUC__) || defined(_MSC_VER)
49#define inline __inline
50#define inline __inline
50#else /* !__GNUC__ */
51#else /* __GNUC__ || _MSC_VER */
51#define inline
52#define inline
52#endif /* !__GNUC__ */
53#endif /* !__GNUC__ && !_MSC_VER */
53
54
54struct arc4_stream {
55 u_int8_t i;
56 u_int8_t j;
57 u_int8_t s[256];
58};
55#define KEYSZ 32
56#define IVSZ 8
57#define BLOCKSZ 64
58#define RSBUFSZ (16*BLOCKSZ)
59
59
60static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
60/* Marked INHERIT_ZERO, so zero'd out in fork children. */
61static struct _rs {
62 size_t rs_have; /* valid bytes at end of rs_buf */
63 size_t rs_count; /* bytes till reseed */
64} *rs;
61
65
62#define KEYSIZE 128
63#define _ARC4_LOCK() \
64 do { \
65 if (__isthreaded) \
66 _pthread_mutex_lock(&arc4random_mtx); \
67 } while (0)
66/* Maybe be preserved in fork children, if _rs_allocate() decides. */
67static struct _rsx {
68 chacha_ctx rs_chacha; /* chacha context for random keystream */
69 u_char rs_buf[RSBUFSZ]; /* keystream blocks */
70} *rsx;
68
71
69#define _ARC4_UNLOCK() \
70 do { \
71 if (__isthreaded) \
72 _pthread_mutex_unlock(&arc4random_mtx); \
73 } while (0)
72static inline int _rs_allocate(struct _rs **, struct _rsx **);
73static inline void _rs_forkdetect(void);
74#include "arc4random.h"
74
75
75static int rs_initialized;
76static struct arc4_stream rs;
77static pid_t arc4_stir_pid;
78static int arc4_count;
76static inline void _rs_rekey(u_char *dat, size_t datlen);
79
77
80extern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp,
81 void *newp, size_t newlen);
82
83static inline u_int8_t arc4_getbyte(void);
84static void arc4_stir(void);
85
86static inline void
78static inline void
87arc4_init(void)
79_rs_init(u_char *buf, size_t n)
88{
80{
89 int n;
81 if (n < KEYSZ + IVSZ)
82 return;
90
83
91 for (n = 0; n < 256; n++)
92 rs.s[n] = n;
93 rs.i = 0;
94 rs.j = 0;
95}
96
97static inline void
98arc4_addrandom(u_char *dat, int datlen)
99{
100 int n;
101 u_int8_t si;
102
103 rs.i--;
104 for (n = 0; n < 256; n++) {
105 rs.i = (rs.i + 1);
106 si = rs.s[rs.i];
107 rs.j = (rs.j + si + dat[n % datlen]);
108 rs.s[rs.i] = rs.s[rs.j];
109 rs.s[rs.j] = si;
84 if (rs == NULL) {
85 if (_rs_allocate(&rs, &rsx) == -1)
86 abort();
110 }
87 }
111 rs.j = rs.i;
88
89 chacha_keysetup(&rsx->rs_chacha, buf, KEYSZ * 8);
90 chacha_ivsetup(&rsx->rs_chacha, buf + KEYSZ, NULL);
112}
113
91}
92
114size_t
115__arc4_sysctl(u_char *buf, size_t size)
93static void
94_rs_stir(void)
116{
95{
117 int mib[2];
118 size_t len, done;
96 u_char rnd[KEYSZ + IVSZ];
119
97
120 mib[0] = CTL_KERN;
121 mib[1] = KERN_ARND;
122 done = 0;
98 if (getentropy(rnd, sizeof rnd) == -1)
99 _getentropy_fail();
123
100
124 do {
125 len = size;
126 if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1)
127 return (done);
128 done += len;
129 buf += len;
130 size -= len;
131 } while (size > 0);
101 if (!rs)
102 _rs_init(rnd, sizeof(rnd));
103 else
104 _rs_rekey(rnd, sizeof(rnd));
105 explicit_bzero(rnd, sizeof(rnd)); /* discard source seed */
132
106
133 return (done);
107 /* invalidate rs_buf */
108 rs->rs_have = 0;
109 memset(rsx->rs_buf, 0, sizeof(rsx->rs_buf));
110
111 rs->rs_count = 1600000;
134}
135
112}
113
136static void
137arc4_stir(void)
114static inline void
115_rs_stir_if_needed(size_t len)
138{
116{
139 u_char rdat[KEYSIZE];
140 int i;
141
142 if (!rs_initialized) {
143 arc4_init();
144 rs_initialized = 1;
145 }
146 if (__arc4_sysctl(rdat, KEYSIZE) != KEYSIZE) {
147 /*
148 * The sysctl cannot fail. If it does fail on some FreeBSD
149 * derivative or after some future change, just abort so that
150 * the problem will be found and fixed. abort is not normally
151 * suitable for a library but makes sense here.
152 */
153 abort();
154 }
155
156 arc4_addrandom(rdat, KEYSIZE);
157
158 /*
159 * Discard early keystream, as per recommendations in:
160 * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
161 */
162 for (i = 0; i < 3072; i++)
163 (void)arc4_getbyte();
164 arc4_count = 1600000;
117 _rs_forkdetect();
118 if (!rs || rs->rs_count <= len)
119 _rs_stir();
120 if (rs->rs_count <= len)
121 rs->rs_count = 0;
122 else
123 rs->rs_count -= len;
165}
166
124}
125
167static void
168arc4_stir_if_needed(void)
126static inline void
127_rs_rekey(u_char *dat, size_t datlen)
169{
128{
170 pid_t pid = getpid();
129#ifndef KEYSTREAM_ONLY
130 memset(rsx->rs_buf, 0, sizeof(rsx->rs_buf));
131#endif
132 /* fill rs_buf with the keystream */
133 chacha_encrypt_bytes(&rsx->rs_chacha, rsx->rs_buf,
134 rsx->rs_buf, sizeof(rsx->rs_buf));
135 /* mix in optional user provided data */
136 if (dat) {
137 size_t i, m;
171
138
172 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) {
173 arc4_stir_pid = pid;
174 arc4_stir();
139 m = minimum(datlen, KEYSZ + IVSZ);
140 for (i = 0; i < m; i++)
141 rsx->rs_buf[i] ^= dat[i];
175 }
142 }
143 /* immediately reinit for backtracking resistance */
144 _rs_init(rsx->rs_buf, KEYSZ + IVSZ);
145 memset(rsx->rs_buf, 0, KEYSZ + IVSZ);
146 rs->rs_have = sizeof(rsx->rs_buf) - KEYSZ - IVSZ;
176}
177
147}
148
178static inline u_int8_t
179arc4_getbyte(void)
149static inline void
150_rs_random_buf(void *_buf, size_t n)
180{
151{
181 u_int8_t si, sj;
152 u_char *buf = (u_char *)_buf;
153 u_char *keystream;
154 size_t m;
182
155
183 rs.i = (rs.i + 1);
184 si = rs.s[rs.i];
185 rs.j = (rs.j + si);
186 sj = rs.s[rs.j];
187 rs.s[rs.i] = sj;
188 rs.s[rs.j] = si;
189 return (rs.s[(si + sj) & 0xff]);
156 _rs_stir_if_needed(n);
157 while (n > 0) {
158 if (rs->rs_have > 0) {
159 m = minimum(n, rs->rs_have);
160 keystream = rsx->rs_buf + sizeof(rsx->rs_buf)
161 - rs->rs_have;
162 memcpy(buf, keystream, m);
163 memset(keystream, 0, m);
164 buf += m;
165 n -= m;
166 rs->rs_have -= m;
167 }
168 if (rs->rs_have == 0)
169 _rs_rekey(NULL, 0);
170 }
190}
191
171}
172
192static inline u_int32_t
193arc4_getword(void)
173static inline void
174_rs_random_u32(uint32_t *val)
194{
175{
195 u_int32_t val;
196 val = arc4_getbyte() << 24;
197 val |= arc4_getbyte() << 16;
198 val |= arc4_getbyte() << 8;
199 val |= arc4_getbyte();
200 return val;
201}
176 u_char *keystream;
202
177
203void
204arc4random_stir(void)
205{
206 _ARC4_LOCK();
207 arc4_stir();
208 _ARC4_UNLOCK();
178 _rs_stir_if_needed(sizeof(*val));
179 if (rs->rs_have < sizeof(*val))
180 _rs_rekey(NULL, 0);
181 keystream = rsx->rs_buf + sizeof(rsx->rs_buf) - rs->rs_have;
182 memcpy(val, keystream, sizeof(*val));
183 memset(keystream, 0, sizeof(*val));
184 rs->rs_have -= sizeof(*val);
209}
210
185}
186
211void
212arc4random_addrandom(u_char *dat, int datlen)
213{
214 _ARC4_LOCK();
215 if (!rs_initialized)
216 arc4_stir();
217 arc4_addrandom(dat, datlen);
218 _ARC4_UNLOCK();
219}
220
221u_int32_t
187uint32_t
222arc4random(void)
223{
188arc4random(void)
189{
224 u_int32_t val;
190 uint32_t val;
191
225 _ARC4_LOCK();
192 _ARC4_LOCK();
226 arc4_count -= 4;
227 arc4_stir_if_needed();
228 val = arc4_getword();
193 _rs_random_u32(&val);
229 _ARC4_UNLOCK();
230 return val;
231}
232
233void
194 _ARC4_UNLOCK();
195 return val;
196}
197
198void
234arc4random_buf(void *_buf, size_t n)
199arc4random_buf(void *buf, size_t n)
235{
200{
236 u_char *buf = (u_char *)_buf;
237 _ARC4_LOCK();
201 _ARC4_LOCK();
238 arc4_stir_if_needed();
239 while (n--) {
240 if (--arc4_count <= 0)
241 arc4_stir();
242 buf[n] = arc4_getbyte();
243 }
202 _rs_random_buf(buf, n);
244 _ARC4_UNLOCK();
245}
203 _ARC4_UNLOCK();
204}
246
247#if 0
248/*-------- Test code for i386 --------*/
249#include <stdio.h>
250#include <machine/pctr.h>
251int
252main(int argc, char **argv)
253{
254 const int iter = 1000000;
255 int i;
256 pctrval v;
257
258 v = rdtsc();
259 for (i = 0; i < iter; i++)
260 arc4random();
261 v = rdtsc() - v;
262 v /= iter;
263
264 printf("%qd cycles\n", v);
265}
266#endif