1/* $NetBSD: kern_rndpool.c,v 1.16 2015/04/21 04:41:36 riastradh 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: kern_rndpool.c,v 1.16 2015/04/21 04:41:36 riastradh Exp $");
35
36#include <sys/param.h>
37#include <sys/rndpool.h>
38#include <sys/sha1.h>
39#include <sys/systm.h>
40
41#include <dev/rnd_private.h>
42
43/*
44 * The random pool "taps"
45 */
46#define TAP1 99
47#define TAP2 59
48#define TAP3 31
49#define TAP4 9
50#define TAP5 7
51
52void
53rndpool_init(rndpool_t *rp)
54{
55
56 rp->cursor = 0;
57 rp->rotate = 1;
58
59 memset(&rp->stats, 0, sizeof(rp->stats));
60
61 rp->stats.curentropy = 0;
62 rp->stats.poolsize = RND_POOLWORDS;
63 rp->stats.threshold = RND_ENTROPY_THRESHOLD;
64 rp->stats.maxentropy = RND_POOLBITS;
65}
66
67u_int32_t
68rndpool_get_entropy_count(rndpool_t *rp)
69{
70
71 return (rp->stats.curentropy);
72}
73
74void
75rndpool_set_entropy_count(rndpool_t *rp, u_int32_t count)
76{
77 int32_t difference = count - rp->stats.curentropy;
78
79 if (__predict_true(difference > 0)) {
80 rp->stats.added += difference;
81 }
82
83 rp->stats.curentropy = count;
84 if (rp->stats.curentropy > RND_POOLBITS) {
85 rp->stats.discarded += (rp->stats.curentropy - RND_POOLBITS);
86 rp->stats.curentropy = RND_POOLBITS;
87 }
88}
89
90void rndpool_get_stats(rndpool_t *rp, void *rsp, int size)
91{
92
93 memcpy(rsp, &rp->stats, size);
94}
95
96/*
97 * The input function treats the contents of the pool as an array of
98 * 32 LFSR's of length RND_POOLWORDS, one per bit-plane. The LFSR's
99 * are clocked once in parallel, using 32-bit xor operations, for each
100 * word to be added.
101 *
102 * Each word to be added is xor'd with the output word of the LFSR
103 * array (one tap at a time).
104 *
105 * In order to facilitate distribution of entropy between the
106 * bit-planes, a 32-bit rotate of this result is performed prior to
107 * feedback. The rotation distance is incremented every RND_POOLWORDS
108 * clocks, by a value that is relativly prime to the word size to try
109 * to spread the bits throughout the pool quickly when the pool is
110 * empty.
111 *
112 * Each LFSR thus takes its feedback from another LFSR, and is
113 * effectively re-keyed by both that LFSR and the new data. Feedback
114 * occurs with another XOR into the new LFSR, rather than assignment,
115 * to avoid destroying any entropy in the destination.
116 *
117 * Even with zeros as input, the LFSR output data are never visible;
118 * the contents of the pool are never divulged except via a hash of
119 * the entire pool, so there is no information for correlation
120 * attacks. With rotation-based rekeying, each LFSR runs at most a few
121 * cycles before being permuted. However, beware of initial
122 * conditions when no entropy has been added.
123 *
124 * The output function also stirs the generated hash back into the
125 * pool, further permuting the LFSRs and spreading entropy through the
126 * pool. Any unknown bits anywhere in the pool are thus reflected
127 * across all the LFSRs after output.
128 *
129 * (The final XOR assignment into the pool for feedback is equivalent
130 * to an additional LFSR tap of the MSB before shifting, in the case
131 * where no rotation is done, once every 32 cycles. This LFSR runs for
132 * at most one length.)
133 */
134static inline void
135rndpool_add_one_word(rndpool_t *rp, u_int32_t val)
136{
137 /*
138 * Shifting is implemented using a cursor and taps as offsets,
139 * added mod the size of the pool. For this reason,
140 * RND_POOLWORDS must be a power of two.
141 */
142 val ^= rp->pool[(rp->cursor + TAP1) & (RND_POOLWORDS - 1)];
143 val ^= rp->pool[(rp->cursor + TAP2) & (RND_POOLWORDS - 1)];
144 val ^= rp->pool[(rp->cursor + TAP3) & (RND_POOLWORDS - 1)];
145 val ^= rp->pool[(rp->cursor + TAP4) & (RND_POOLWORDS - 1)];
146 val ^= rp->pool[(rp->cursor + TAP5) & (RND_POOLWORDS - 1)];
147 if (rp->rotate != 0)
148 val = ((val << rp->rotate) | (val >> (32 - rp->rotate)));
149 rp->pool[rp->cursor++] ^= val;
150
151 /*
152 * If we have looped around the pool, increment the rotate
153 * variable so the next value will get xored in rotated to
154 * a different position.
155 */
156 if (rp->cursor == RND_POOLWORDS) {
157 rp->cursor = 0;
158 rp->rotate = (rp->rotate + 7) & 31;
159 }
160}
161
162/*
163 * Add a buffer's worth of data to the pool.
164 */
165void
166rndpool_add_data(rndpool_t *rp,
167 const void * const p, u_int32_t len, u_int32_t entropy)
168{
169 u_int32_t val;
170 const u_int8_t * buf;
171
172 buf = p;
173
174 for (; len > 3; len -= 4) {
175 (void)memcpy(&val, buf, 4);
176 rndpool_add_one_word(rp, val);
177 buf += 4;
178 }
179
180 if (len != 0) {
181 val = 0;
182 switch (len) {
183 case 3:
184 val = *buf++;
185 case 2:
186 val = val << 8 | *buf++;
187 case 1:
188 val = val << 8 | *buf++;
189 }
190
191 rndpool_add_one_word(rp, val);
192 }
193
194 rp->stats.curentropy += entropy;
195 rp->stats.added += entropy;
196
197 if (rp->stats.curentropy > RND_POOLBITS) {
198 rp->stats.discarded += (rp->stats.curentropy - RND_POOLBITS);
199 rp->stats.curentropy = RND_POOLBITS;
200 }
201}
202
203/*
204 * Extract some number of bytes from the random pool, decreasing the
205 * estimate of randomness as each byte is extracted.
206 *
207 * Do this by hashing the pool and returning a part of the hash as
208 * randomness. Stir the hash back into the pool. Note that no
209 * secrets going back into the pool are given away here since parts of
210 * the hash are xored together before being returned.
211 *
212 * Honor the request from the caller to only return good data, any data,
213 * etc.
214 *
215 * For the "high-quality" mode, we must have as much data as the caller
216 * requests, and at some point we must have had at least the "threshold"
217 * amount of entropy in the pool.
218 */
219u_int32_t
220rndpool_extract_data(rndpool_t *rp, void *p, u_int32_t len, u_int32_t mode)
221{
222 u_int i;
223 SHA1_CTX hash;
224 u_char digest[SHA1_DIGEST_LENGTH];
225 u_int32_t remain, deltae, count;
226 u_int8_t *buf;
227
228 buf = p;
229 remain = len;
230
231 KASSERT(RND_ENTROPY_THRESHOLD * 2 <= sizeof(digest));
232
233 while (remain != 0 && ! (mode == RND_EXTRACT_GOOD &&
234 remain > rp->stats.curentropy * 8)) {
235 /*
236 * While bytes are requested, compute the hash of the pool,
237 * and then "fold" the hash in half with XOR, keeping the
238 * exact hash value secret, as it will be stirred back into
239 * the pool.
240 *
241 * XXX this approach needs examination by competant
242 * cryptographers! It's rather expensive per bit but
243 * also involves every bit of the pool in the
244 * computation of every output bit..
245 */
246 SHA1Init(&hash);
247 SHA1Update(&hash, (u_int8_t *)rp->pool, RND_POOLWORDS * 4);
248 SHA1Final(digest, &hash);
249
250 /*
251 * Stir the hash back into the pool. This guarantees
252 * that the next hash will generate a different value
253 * if no new values were added to the pool.
254 */
255 CTASSERT(RND_ENTROPY_THRESHOLD * 2 == SHA1_DIGEST_LENGTH);
256 for (i = 0; i < SHA1_DIGEST_LENGTH/4; i++) {
257 u_int32_t word;
258 memcpy(&word, &digest[i * 4], 4);
259 rndpool_add_one_word(rp, word);
260 }
261
262 /* XXX careful, here the THRESHOLD just controls folding */
263 count = min(remain, RND_ENTROPY_THRESHOLD);
264
265 for (i = 0; i < count; i++)
266 buf[i] = digest[i] ^ digest[i + RND_ENTROPY_THRESHOLD];
267
268 buf += count;
269 deltae = count * 8;
270 remain -= count;
271
272 deltae = min(deltae, rp->stats.curentropy);
273
274 rp->stats.removed += deltae;
275 rp->stats.curentropy -= deltae;
276
277 if (rp->stats.curentropy == 0)
278 rp->stats.generated += (count * 8) - deltae;
279
280 }
281
282 explicit_memset(&hash, 0, sizeof(hash));
283 explicit_memset(digest, 0, sizeof(digest));
284
285 return (len - remain);
286}
287