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