1/*      $NetBSD$        */
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$");
35
36#include <sys/param.h>
37#include <sys/systm.h>
38#include <sys/sha1.h>
39
40#include <sys/rnd.h>
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
52/*
53 * Let others know: the pool is full.
54 */
55int rnd_full = 0;			/* Flag: is the pool full? */
56int rnd_filled = 0;			/* Count: how many times filled? */
57
58static inline void rndpool_add_one_word(rndpool_t *, u_int32_t);
59
60void
61rndpool_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 <= SHA1_DIGEST_LENGTH);
75}
76
77u_int32_t
78rndpool_get_entropy_count(rndpool_t *rp)
79{
80
81	return (rp->stats.curentropy);
82}
83
84void rndpool_get_stats(rndpool_t *rp, void *rsp, int size)
85{
86
87	memcpy(rsp, &rp->stats, size);
88}
89
90void
91rndpool_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
102u_int32_t *
103rndpool_get_pool(rndpool_t *rp)
104{
105
106	return (rp->pool);
107}
108
109u_int32_t
110rndpool_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 */
154static inline void
155rndpool_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/*
183 * Add a buffer's worth of data to the pool.
184 */
185void
186rndpool_add_data(rndpool_t *rp, void *p, u_int32_t len, u_int32_t entropy)
187{
188	u_int32_t val;
189	u_int8_t *buf;
190
191	buf = p;
192
193	for (; len > 3; len -= 4) {
194		val = *((u_int32_t *)buf);
195
196		rndpool_add_one_word(rp, val);
197		buf += 4;
198	}
199
200	if (len != 0) {
201		val = 0;
202		switch (len) {
203		case 3:
204			val = *buf++;
205		case 2:
206			val = val << 8 | *buf++;
207		case 1:
208			val = val << 8 | *buf++;
209		}
210
211		rndpool_add_one_word(rp, val);
212	}
213
214	rp->stats.curentropy += entropy;
215	rp->stats.added += entropy;
216
217	if (rp->stats.curentropy > RND_POOLBITS) {
218		rp->stats.discarded += (rp->stats.curentropy - RND_POOLBITS);
219		rp->stats.curentropy = RND_POOLBITS;
220		rnd_filled++;
221		rnd_full = 1;
222	}
223}
224
225/*
226 * Extract some number of bytes from the random pool, decreasing the
227 * estimate of randomness as each byte is extracted.
228 *
229 * Do this by hashing the pool and returning a part of the hash as
230 * randomness.  Stir the hash back into the pool.  Note that no
231 * secrets going back into the pool are given away here since parts of
232 * the hash are xored together before being returned.
233 *
234 * Honor the request from the caller to only return good data, any data,
235 * etc.  Note that we must have at least 64 bits of entropy in the pool
236 * before we return anything in the high-quality modes.
237 */
238u_int32_t
239rndpool_extract_data(rndpool_t *rp, void *p, u_int32_t len, u_int32_t mode)
240{
241	u_int i;
242	SHA1_CTX hash;
243	u_char digest[SHA1_DIGEST_LENGTH];
244	u_int32_t remain, deltae, count;
245	u_int8_t *buf;
246	int good;
247
248	buf = p;
249	remain = len;
250
251	if (rp->stats.curentropy < RND_POOLBITS / 2) {
252		rnd_full = 0;
253	}
254
255	if (mode == RND_EXTRACT_ANY)
256		good = 1;
257	else
258		good = (rp->stats.curentropy >= (8 * RND_ENTROPY_THRESHOLD));
259
260	KASSERT(RND_ENTROPY_THRESHOLD * 2 <= sizeof(digest));
261
262	while (good && (remain != 0)) {
263		/*
264		 * While bytes are requested, compute the hash of the pool,
265		 * and then "fold" the hash in half with XOR, keeping the
266		 * exact hash value secret, as it will be stirred back into
267		 * the pool.
268		 *
269		 * XXX this approach needs examination by competant
270		 * cryptographers!  It's rather expensive per bit but
271		 * also involves every bit of the pool in the
272		 * computation of every output bit..
273		 */
274		SHA1Init(&hash);
275		SHA1Update(&hash, (u_int8_t *)rp->pool, RND_POOLWORDS * 4);
276		SHA1Final(digest, &hash);
277
278		/*
279		 * Stir the hash back into the pool.  This guarantees
280		 * that the next hash will generate a different value
281		 * if no new values were added to the pool.
282		 */
283		for (i = 0; i < 5; i++) {
284			u_int32_t word;
285			memcpy(&word, &digest[i * 4], 4);
286			rndpool_add_one_word(rp, word);
287		}
288
289		count = min(remain, RND_ENTROPY_THRESHOLD);
290
291		for (i = 0; i < count; i++)
292			buf[i] = digest[i] ^ digest[i + RND_ENTROPY_THRESHOLD];
293
294		buf += count;
295		deltae = count * 8;
296		remain -= count;
297
298		deltae = min(deltae, rp->stats.curentropy);
299
300		rp->stats.removed += deltae;
301		rp->stats.curentropy -= deltae;
302
303		if (rp->stats.curentropy == 0)
304			rp->stats.generated += (count * 8) - deltae;
305
306		if (mode == RND_EXTRACT_GOOD)
307			good = (rp->stats.curentropy >=
308			    (8 * RND_ENTROPY_THRESHOLD));
309	}
310
311	memset(&hash, 0, sizeof(hash));
312	memset(digest, 0, sizeof(digest));
313
314	return (len - remain);
315}
316