| @@ -1,14 +1,14 @@ | | | @@ -1,14 +1,14 @@ |
1 | /* $NetBSD: arc4random.c,v 1.12 2012/03/04 00:36:43 tls Exp $ */ | | 1 | /* $NetBSD: arc4random.c,v 1.13 2012/03/05 19:40:08 christos Exp $ */ |
2 | /* $OpenBSD: arc4random.c,v 1.6 2001/06/05 05:05:38 pvalchev Exp $ */ | | 2 | /* $OpenBSD: arc4random.c,v 1.6 2001/06/05 05:05:38 pvalchev Exp $ */ |
3 | | | 3 | |
4 | /* | | 4 | /* |
5 | * Arc4 random number generator for OpenBSD. | | 5 | * Arc4 random number generator for OpenBSD. |
6 | * Copyright 1996 David Mazieres <dm@lcs.mit.edu>. | | 6 | * Copyright 1996 David Mazieres <dm@lcs.mit.edu>. |
7 | * | | 7 | * |
8 | * Modification and redistribution in source and binary forms is | | 8 | * Modification and redistribution in source and binary forms is |
9 | * permitted provided that due credit is given to the author and the | | 9 | * permitted provided that due credit is given to the author and the |
10 | * OpenBSD project by leaving this copyright notice intact. | | 10 | * OpenBSD project by leaving this copyright notice intact. |
11 | */ | | 11 | */ |
12 | | | 12 | |
13 | /* | | 13 | /* |
14 | * This code is derived from section 17.1 of Applied Cryptography, | | 14 | * This code is derived from section 17.1 of Applied Cryptography, |
| @@ -17,126 +17,119 @@ | | | @@ -17,126 +17,119 @@ |
17 | * which is a trade secret). The same algorithm is used as a stream | | 17 | * which is a trade secret). The same algorithm is used as a stream |
18 | * cipher called "arcfour" in Tatu Ylonen's ssh package. | | 18 | * cipher called "arcfour" in Tatu Ylonen's ssh package. |
19 | * | | 19 | * |
20 | * Here the stream cipher has been modified always to include the time | | 20 | * Here the stream cipher has been modified always to include the time |
21 | * when initializing the state. That makes it impossible to | | 21 | * when initializing the state. That makes it impossible to |
22 | * regenerate the same random sequence twice, so this can't be used | | 22 | * regenerate the same random sequence twice, so this can't be used |
23 | * for encryption, but will generate good random numbers. | | 23 | * for encryption, but will generate good random numbers. |
24 | * | | 24 | * |
25 | * RC4 is a registered trademark of RSA Laboratories. | | 25 | * RC4 is a registered trademark of RSA Laboratories. |
26 | */ | | 26 | */ |
27 | | | 27 | |
28 | #include <sys/cdefs.h> | | 28 | #include <sys/cdefs.h> |
29 | #if defined(LIBC_SCCS) && !defined(lint) | | 29 | #if defined(LIBC_SCCS) && !defined(lint) |
30 | __RCSID("$NetBSD: arc4random.c,v 1.12 2012/03/04 00:36:43 tls Exp $"); | | 30 | __RCSID("$NetBSD: arc4random.c,v 1.13 2012/03/05 19:40:08 christos Exp $"); |
31 | #endif /* LIBC_SCCS and not lint */ | | 31 | #endif /* LIBC_SCCS and not lint */ |
32 | | | 32 | |
33 | #include "namespace.h" | | 33 | #include "namespace.h" |
34 | #include "reentrant.h" | | 34 | #include "reentrant.h" |
35 | #include <fcntl.h> | | 35 | #include <fcntl.h> |
36 | #include <stdlib.h> | | 36 | #include <stdlib.h> |
37 | #include <unistd.h> | | 37 | #include <unistd.h> |
38 | #include <sys/types.h> | | 38 | #include <sys/types.h> |
39 | #include <sys/param.h> | | 39 | #include <sys/param.h> |
40 | #include <sys/time.h> | | 40 | #include <sys/time.h> |
41 | #include <sys/sysctl.h> | | 41 | #include <sys/sysctl.h> |
42 | | | 42 | |
43 | #ifdef __weak_alias | | 43 | #ifdef __weak_alias |
44 | __weak_alias(arc4random,_arc4random) | | 44 | __weak_alias(arc4random,_arc4random) |
45 | #endif | | 45 | #endif |
46 | | | 46 | |
| | | 47 | #define RSIZE 256 |
47 | struct arc4_stream { | | 48 | struct arc4_stream { |
48 | mutex_t mtx; | | 49 | mutex_t mtx; |
49 | int initialized; | | 50 | int initialized; |
50 | uint8_t i; | | 51 | uint8_t i; |
51 | uint8_t j; | | 52 | uint8_t j; |
52 | uint8_t s[256]; | | 53 | uint8_t s[RSIZE]; |
53 | }; | | 54 | }; |
54 | | | 55 | |
55 | /* XXX lint explodes with an internal error if only mtx is initialized! */ | | 56 | /* XXX lint explodes with an internal error if only mtx is initialized! */ |
56 | static struct arc4_stream rs = { .i = 0, .mtx = MUTEX_INITIALIZER }; | | 57 | static struct arc4_stream rs = { .i = 0, .mtx = MUTEX_INITIALIZER }; |
57 | | | 58 | |
58 | static inline void arc4_init(struct arc4_stream *); | | 59 | static inline void arc4_init(struct arc4_stream *); |
59 | static inline void arc4_addrandom(struct arc4_stream *, u_char *, int); | | 60 | static inline void arc4_addrandom(struct arc4_stream *, u_char *, int); |
60 | static void arc4_stir(struct arc4_stream *); | | 61 | static void arc4_stir(struct arc4_stream *); |
61 | static inline uint8_t arc4_getbyte(struct arc4_stream *); | | 62 | static inline uint8_t arc4_getbyte(struct arc4_stream *); |
62 | static inline uint32_t arc4_getword(struct arc4_stream *); | | 63 | static inline uint32_t arc4_getword(struct arc4_stream *); |
63 | | | 64 | |
64 | static inline void | | 65 | static inline void |
65 | arc4_init(struct arc4_stream *as) | | 66 | arc4_init(struct arc4_stream *as) |
66 | { | | 67 | { |
67 | int n; | | 68 | for (int n = 0; n < RSIZE; n++) |
68 | | | | |
69 | for (n = 0; n < 256; n++) | | | |
70 | as->s[n] = n; | | 69 | as->s[n] = n; |
71 | as->i = 0; | | 70 | as->i = 0; |
72 | as->j = 0; | | 71 | as->j = 0; |
73 | | | 72 | |
74 | as->initialized = 1; | | 73 | as->initialized = 1; |
75 | arc4_stir(as); | | 74 | arc4_stir(as); |
76 | } | | 75 | } |
77 | | | 76 | |
78 | static inline void | | 77 | static inline void |
79 | arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen) | | 78 | arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen) |
80 | { | | 79 | { |
81 | int n; | | | |
82 | uint8_t si; | | 80 | uint8_t si; |
83 | | | 81 | |
84 | as->i--; | | 82 | as->i--; |
85 | for (n = 0; n < 256; n++) { | | 83 | for (int n = 0; n < RSIZE; n++) { |
86 | as->i = (as->i + 1); | | 84 | as->i = (as->i + 1); |
87 | si = as->s[as->i]; | | 85 | si = as->s[as->i]; |
88 | as->j = (as->j + si + dat[n % datlen]); | | 86 | as->j = (as->j + si + dat[n % datlen]); |
89 | as->s[as->i] = as->s[as->j]; | | 87 | as->s[as->i] = as->s[as->j]; |
90 | as->s[as->j] = si; | | 88 | as->s[as->j] = si; |
91 | } | | 89 | } |
92 | as->j = as->i; | | 90 | as->j = as->i; |
93 | } | | 91 | } |
94 | | | 92 | |
95 | static void | | 93 | static void |
96 | arc4_stir(struct arc4_stream *as) | | 94 | arc4_stir(struct arc4_stream *as) |
97 | { | | 95 | { |
98 | int rdat[128 / sizeof(int)]; | | 96 | int rdat[32]; |
99 | int n; | | 97 | static const int mib[] = { CTL_KERN, KERN_URND }; |
100 | int mib[2]; | | | |
101 | unsigned int i; | | | |
102 | size_t len; | | 98 | size_t len; |
103 | | | 99 | |
104 | /* | | 100 | /* |
105 | * This code once opened and read /dev/urandom on each | | 101 | * This code once opened and read /dev/urandom on each |
106 | * call. That causes repeated rekeying of the kernel stream | | 102 | * call. That causes repeated rekeying of the kernel stream |
107 | * generator, which is very wasteful. Because of application | | 103 | * generator, which is very wasteful. Because of application |
108 | * behavior, caching the fd doesn't really help. So we just | | 104 | * behavior, caching the fd doesn't really help. So we just |
109 | * fill up the tank from sysctl, which is a tiny bit slower | | 105 | * fill up the tank from sysctl, which is a tiny bit slower |
110 | * for us but much friendlier to other entropy consumers. | | 106 | * for us but much friendlier to other entropy consumers. |
111 | */ | | 107 | */ |
112 | | | 108 | |
113 | mib[0] = CTL_KERN; | | 109 | for (size_t i = 0; i < __arraycount(rdat); i++) { |
114 | mib[1] = KERN_URND; | | | |
115 | | | | |
116 | for (i = 0; i < sizeof(rdat) / sizeof(int); i++) { | | | |
117 | len = sizeof(rdat[i]); | | 110 | len = sizeof(rdat[i]); |
118 | if (sysctl(mib, 2, &rdat[i], &len, NULL, 0) == -1) | | 111 | if (sysctl(mib, 2, &rdat[i], &len, NULL, 0) == -1) |
119 | abort(); | | 112 | abort(); |
120 | } | | 113 | } |
121 | | | 114 | |
122 | arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); | | 115 | arc4_addrandom(as, (void *) &rdat, (int)sizeof(rdat)); |
123 | | | 116 | |
124 | /* | | 117 | /* |
125 | * Throw away the first N words of output, as suggested in the | | 118 | * Throw away the first N words of output, as suggested in the |
126 | * paper "Weaknesses in the Key Scheduling Algorithm of RC4" | | 119 | * paper "Weaknesses in the Key Scheduling Algorithm of RC4" |
127 | * by Fluher, Mantin, and Shamir. (N = 256 in our case.) | | 120 | * by Fluher, Mantin, and Shamir. (N = 256 in our case.) |
128 | */ | | 121 | */ |
129 | for (n = 0; n < 256 * 4; n++) | | 122 | for (size_t j = 0; j < RSIZE * 4; j++) |
130 | arc4_getbyte(as); | | 123 | arc4_getbyte(as); |
131 | } | | 124 | } |
132 | | | 125 | |
133 | static inline uint8_t | | 126 | static inline uint8_t |
134 | arc4_getbyte(struct arc4_stream *as) | | 127 | arc4_getbyte(struct arc4_stream *as) |
135 | { | | 128 | { |
136 | uint8_t si, sj; | | 129 | uint8_t si, sj; |
137 | | | 130 | |
138 | as->i = (as->i + 1); | | 131 | as->i = (as->i + 1); |
139 | si = as->s[as->i]; | | 132 | si = as->s[as->i]; |
140 | as->j = (as->j + si); | | 133 | as->j = (as->j + si); |
141 | sj = as->s[as->j]; | | 134 | sj = as->s[as->j]; |
142 | as->s[as->i] = sj; | | 135 | as->s[as->i] = sj; |
| @@ -274,27 +267,27 @@ arc4random_buf(void *buf, size_t len) | | | @@ -274,27 +267,27 @@ arc4random_buf(void *buf, size_t len) |
274 | * random number will be inside the range | | 267 | * random number will be inside the range |
275 | * [2^32 % upper_bound, 2^32[ which maps back to | | 268 | * [2^32 % upper_bound, 2^32[ which maps back to |
276 | * [0, upper_bound[ after reduction modulo upper_bound. | | 269 | * [0, upper_bound[ after reduction modulo upper_bound. |
277 | */ | | 270 | */ |
278 | static uint32_t | | 271 | static uint32_t |
279 | _arc4random_uniform_unlocked(uint32_t upper_bound) | | 272 | _arc4random_uniform_unlocked(uint32_t upper_bound) |
280 | { | | 273 | { |
281 | uint32_t r, min; | | 274 | uint32_t r, min; |
282 | | | 275 | |
283 | if (upper_bound < 2) | | 276 | if (upper_bound < 2) |
284 | return 0; | | 277 | return 0; |
285 | | | 278 | |
286 | #if defined(ULONG_MAX) && (ULONG_MAX > 0xFFFFFFFFUL) | | 279 | #if defined(ULONG_MAX) && (ULONG_MAX > 0xFFFFFFFFUL) |
287 | min = 0x100000000UL % upper_bound; | | 280 | min = (uint32_t)(0x100000000U % upper_bound); |
288 | #else | | 281 | #else |
289 | /* calculate (2^32 % upper_bound) avoiding 64-bit math */ | | 282 | /* calculate (2^32 % upper_bound) avoiding 64-bit math */ |
290 | if (upper_bound > 0x80000000U) | | 283 | if (upper_bound > 0x80000000U) |
291 | /* 2^32 - upper_bound (only one "value area") */ | | 284 | /* 2^32 - upper_bound (only one "value area") */ |
292 | min = 1 + ~upper_bound; | | 285 | min = 1 + ~upper_bound; |
293 | else | | 286 | else |
294 | /* ((2^32 - x) % x) == (2^32 % x) when x <= 2^31 */ | | 287 | /* ((2^32 - x) % x) == (2^32 % x) when x <= 2^31 */ |
295 | min = (0xFFFFFFFFU - upper_bound + 1) % upper_bound; | | 288 | min = (0xFFFFFFFFU - upper_bound + 1) % upper_bound; |
296 | #endif | | 289 | #endif |
297 | | | 290 | |
298 | /* | | 291 | /* |
299 | * This could theoretically loop forever but each retry has | | 292 | * This could theoretically loop forever but each retry has |
300 | * p > 0.5 (worst case, usually far better) of selecting a | | 293 | * p > 0.5 (worst case, usually far better) of selecting a |