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