FreeBSD/Linux Kernel Cross Reference
sys/dev/rndpool.c
1 /* $NetBSD: rndpool.c,v 1.20 2008/04/28 20:23:47 martin Exp $ */
2
3 /*-
4 * Copyright (c) 1997 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Michael Graff <explorer@flame.org>. This code uses ideas and
9 * algorithms from the Linux driver written by Ted Ts'o.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
21 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
24 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30 * POSSIBILITY OF SUCH DAMAGE.
31 */
32
33 #include <sys/cdefs.h>
34 __KERNEL_RCSID(0, "$NetBSD: rndpool.c,v 1.20 2008/04/28 20:23:47 martin Exp $");
35
36 #include <sys/param.h>
37 #include <sys/systm.h>
38 #include <sys/sha1.h>
39
40 #include <sys/rnd.h>
41
42 /*
43 * The random pool "taps"
44 */
45 #define TAP1 99
46 #define TAP2 59
47 #define TAP3 31
48 #define TAP4 9
49 #define TAP5 7
50
51 static inline void rndpool_add_one_word(rndpool_t *, u_int32_t);
52
53 void
54 rndpool_init(rndpool_t *rp)
55 {
56
57 rp->cursor = 0;
58 rp->rotate = 1;
59
60 memset(&rp->stats, 0, sizeof(rp->stats));
61
62 rp->stats.curentropy = 0;
63 rp->stats.poolsize = RND_POOLWORDS;
64 rp->stats.threshold = RND_ENTROPY_THRESHOLD;
65 rp->stats.maxentropy = RND_POOLBITS;
66
67 KASSERT(RND_ENTROPY_THRESHOLD*2 <= 20); /* XXX sha knowledge */
68 }
69
70 u_int32_t
71 rndpool_get_entropy_count(rndpool_t *rp)
72 {
73
74 return (rp->stats.curentropy);
75 }
76
77 void rndpool_get_stats(rndpool_t *rp, void *rsp, int size)
78 {
79
80 memcpy(rsp, &rp->stats, size);
81 }
82
83 void
84 rndpool_increment_entropy_count(rndpool_t *rp, u_int32_t entropy)
85 {
86
87 rp->stats.curentropy += entropy;
88 rp->stats.added += entropy;
89 if (rp->stats.curentropy > RND_POOLBITS) {
90 rp->stats.discarded += (rp->stats.curentropy - RND_POOLBITS);
91 rp->stats.curentropy = RND_POOLBITS;
92 }
93 }
94
95 u_int32_t *
96 rndpool_get_pool(rndpool_t *rp)
97 {
98
99 return (rp->pool);
100 }
101
102 u_int32_t
103 rndpool_get_poolsize(void)
104 {
105
106 return (RND_POOLWORDS);
107 }
108
109 /*
110 * The input function treats the contents of the pool as an array of
111 * 32 LFSR's of length RND_POOLWORDS, one per bit-plane. The LFSR's
112 * are clocked once in parallel, using 32-bit xor operations, for each
113 * word to be added.
114 *
115 * Each word to be added is xor'd with the output word of the LFSR
116 * array (one tap at a time).
117 *
118 * In order to facilitate distribution of entropy between the
119 * bit-planes, a 32-bit rotate of this result is performed prior to
120 * feedback. The rotation distance is incremented every RND_POOLWORDS
121 * clocks, by a value that is relativly prime to the word size to try
122 * to spread the bits throughout the pool quickly when the pool is
123 * empty.
124 *
125 * Each LFSR thus takes its feedback from another LFSR, and is
126 * effectively re-keyed by both that LFSR and the new data. Feedback
127 * occurs with another XOR into the new LFSR, rather than assignment,
128 * to avoid destroying any entropy in the destination.
129 *
130 * Even with zeros as input, the LFSR output data are never visible;
131 * the contents of the pool are never divulged except via a hash of
132 * the entire pool, so there is no information for correlation
133 * attacks. With rotation-based rekeying, each LFSR runs at most a few
134 * cycles before being permuted. However, beware of initial
135 * conditions when no entropy has been added.
136 *
137 * The output function also stirs the generated hash back into the
138 * pool, further permuting the LFSRs and spreading entropy through the
139 * pool. Any unknown bits anywhere in the pool are thus reflected
140 * across all the LFSRs after output.
141 *
142 * (The final XOR assignment into the pool for feedback is equivalent
143 * to an additional LFSR tap of the MSB before shifting, in the case
144 * where no rotation is done, once every 32 cycles. This LFSR runs for
145 * at most one length.)
146 */
147 static inline void
148 rndpool_add_one_word(rndpool_t *rp, u_int32_t val)
149 {
150 /*
151 * Shifting is implemented using a cursor and taps as offsets,
152 * added mod the size of the pool. For this reason,
153 * RND_POOLWORDS must be a power of two.
154 */
155 val ^= rp->pool[(rp->cursor + TAP1) & (RND_POOLWORDS - 1)];
156 val ^= rp->pool[(rp->cursor + TAP2) & (RND_POOLWORDS - 1)];
157 val ^= rp->pool[(rp->cursor + TAP3) & (RND_POOLWORDS - 1)];
158 val ^= rp->pool[(rp->cursor + TAP4) & (RND_POOLWORDS - 1)];
159 val ^= rp->pool[(rp->cursor + TAP5) & (RND_POOLWORDS - 1)];
160 if (rp->rotate != 0)
161 val = ((val << rp->rotate) | (val >> (32 - rp->rotate)));
162 rp->pool[rp->cursor++] ^= val;
163
164 /*
165 * If we have looped around the pool, increment the rotate
166 * variable so the next value will get xored in rotated to
167 * a different position.
168 */
169 if (rp->cursor == RND_POOLWORDS) {
170 rp->cursor = 0;
171 rp->rotate = (rp->rotate + 7) & 31;
172 }
173 }
174
175 #if 0
176 /*
177 * Stir a 32-bit value (with possibly less entropy than that) into the pool.
178 * Update entropy estimate.
179 */
180 void
181 rndpool_add_uint32(rndpool_t *rp, u_int32_t val, u_int32_t entropy)
182 {
183 rndpool_add_one_word(rp, val);
184
185 rp->entropy += entropy;
186 rp->stats.added += entropy;
187 if (rp->entropy > RND_POOLBITS) {
188 rp->stats.discarded += (rp->entropy - RND_POOLBITS);
189 rp->entropy = RND_POOLBITS;
190 }
191 }
192 #endif
193
194 /*
195 * Add a buffer's worth of data to the pool.
196 */
197 void
198 rndpool_add_data(rndpool_t *rp, void *p, u_int32_t len, u_int32_t entropy)
199 {
200 u_int32_t val;
201 u_int8_t *buf;
202
203 buf = p;
204
205 for (; len > 3; len -= 4) {
206 val = *((u_int32_t *)buf);
207
208 rndpool_add_one_word(rp, val);
209 buf += 4;
210 }
211
212 if (len != 0) {
213 val = 0;
214 switch (len) {
215 case 3:
216 val = *buf++;
217 case 2:
218 val = val << 8 | *buf++;
219 case 1:
220 val = val << 8 | *buf++;
221 }
222
223 rndpool_add_one_word(rp, val);
224 }
225
226 rp->stats.curentropy += entropy;
227 rp->stats.added += entropy;
228
229 if (rp->stats.curentropy > RND_POOLBITS) {
230 rp->stats.discarded += (rp->stats.curentropy - RND_POOLBITS);
231 rp->stats.curentropy = RND_POOLBITS;
232 }
233 }
234
235 /*
236 * Extract some number of bytes from the random pool, decreasing the
237 * estimate of randomness as each byte is extracted.
238 *
239 * Do this by hashing the pool and returning a part of the hash as
240 * randomness. Stir the hash back into the pool. Note that no
241 * secrets going back into the pool are given away here since parts of
242 * the hash are xored together before being returned.
243 *
244 * Honor the request from the caller to only return good data, any data,
245 * etc. Note that we must have at least 64 bits of entropy in the pool
246 * before we return anything in the high-quality modes.
247 */
248 u_int32_t
249 rndpool_extract_data(rndpool_t *rp, void *p, u_int32_t len, u_int32_t mode)
250 {
251 u_int i;
252 SHA1_CTX hash;
253 u_char digest[20]; /* XXX SHA knowledge */
254 u_int32_t remain, deltae, count;
255 u_int8_t *buf;
256 int good;
257
258 buf = p;
259 remain = len;
260
261 if (mode == RND_EXTRACT_ANY)
262 good = 1;
263 else
264 good = (rp->stats.curentropy >= (8 * RND_ENTROPY_THRESHOLD));
265
266 KASSERT(RND_ENTROPY_THRESHOLD*2 <= 20); /* XXX SHA knowledge */
267
268 while (good && (remain != 0)) {
269 /*
270 * While bytes are requested, compute the hash of the pool,
271 * and then "fold" the hash in half with XOR, keeping the
272 * exact hash value secret, as it will be stirred back into
273 * the pool.
274 *
275 * XXX this approach needs examination by competant
276 * cryptographers! It's rather expensive per bit but
277 * also involves every bit of the pool in the
278 * computation of every output bit..
279 */
280 SHA1Init(&hash);
281 SHA1Update(&hash, (u_int8_t *)rp->pool, RND_POOLWORDS * 4);
282 SHA1Final(digest, &hash);
283
284 /*
285 * Stir the hash back into the pool. This guarantees
286 * that the next hash will generate a different value
287 * if no new values were added to the pool.
288 */
289 for (i = 0; i < 5; i++) {
290 u_int32_t word;
291 memcpy(&word, &digest[i * 4], 4);
292 rndpool_add_one_word(rp, word);
293 }
294
295 count = min(remain, RND_ENTROPY_THRESHOLD);
296
297 for (i = 0; i < count; i++)
298 buf[i] = digest[i] ^ digest[i + RND_ENTROPY_THRESHOLD];
299
300 buf += count;
301 deltae = count * 8;
302 remain -= count;
303
304 deltae = min(deltae, rp->stats.curentropy);
305
306 rp->stats.removed += deltae;
307 rp->stats.curentropy -= deltae;
308
309 if (rp->stats.curentropy == 0)
310 rp->stats.generated += (count * 8) - deltae;
311
312 if (mode == RND_EXTRACT_GOOD)
313 good = (rp->stats.curentropy >=
314 (8 * RND_ENTROPY_THRESHOLD));
315 }
316
317 memset(&hash, 0, sizeof(hash));
318 memset(digest, 0, sizeof(digest));
319
320 return (len - remain);
321 }
Cache object: c3f209945fb3b6c88dd40ed7c1fd8922
|