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 | |