1 /* 2 * Copyright (c) 2014 The DragonFly Project. All rights reserved. 3 * 4 * This code is derived from software contributed to The DragonFly Project 5 * by Alex Hornung <alex@alexhornung.com> 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 3. Neither the name of The DragonFly Project nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific, prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 #include <sys/param.h> 35 #include <sys/systm.h> 36 #include <sys/kernel.h> 37 #include <sys/spinlock.h> 38 #include <sys/spinlock2.h> 39 #include <sys/csprng.h> 40 41 /* 42 * Minimum amount of bytes in pool before we consider it 43 * good enough. 44 * It's 64 + the hash digest size because we always 45 * reinitialize the pools with a hash of the previous chunk 46 * of entropy. 47 */ 48 #define MIN_POOL_SIZE (64 + SHA256_DIGEST_LENGTH) 49 50 /* Minimum reseed interval */ 51 #define MIN_RESEED_INTERVAL hz/10 52 53 /* Lock macros */ 54 #define POOL_LOCK_INIT(pool) \ 55 spin_init(&(pool)->lock, "csprng_poollock") 56 57 #define POOL_LOCK(pool) \ 58 spin_lock(&pool->lock) 59 60 #define POOL_TRYLOCK(pool) \ 61 spin_trylock(&pool->lock) 62 63 #define POOL_UNLOCK(pool) \ 64 spin_unlock(&pool->lock) 65 66 67 #define STATE_LOCK_INIT(state) \ 68 spin_init(&state->lock, "csprng_statelock") 69 70 #define STATE_LOCK(state) \ 71 spin_lock(&state->lock) 72 73 #define STATE_UNLOCK(state) \ 74 spin_unlock(&state->lock) 75 76 #define STATE_SLEEP(state, wmesg, timo) \ 77 ssleep(state, &state->lock, 0, wmesg, timo) 78 79 #define STATE_WAKEUP(state) \ 80 wakeup(state) 81 82 static void csprng_reseed_callout(void *arg); 83 static int csprng_reseed(struct csprng_state *state); 84 85 static struct timeval csprng_reseed_interval = { 0, 100000 }; 86 87 static 88 int 89 csprng_pool_init(struct csprng_pool *pool, uint8_t *buf, size_t len) 90 { 91 pool->bytes = 0; 92 SHA256_Init(&pool->hash_ctx); 93 94 if (len > 0) 95 SHA256_Update(&pool->hash_ctx, buf, len); 96 97 return 0; 98 } 99 100 int 101 csprng_init(struct csprng_state *state) 102 { 103 int i, r; 104 105 bzero(state->key, sizeof(state->key)); 106 bzero(&state->cipher_ctx, sizeof(state->cipher_ctx)); 107 bzero(state->src_pool_idx, sizeof(state->src_pool_idx)); 108 bzero(&state->last_reseed, sizeof(state->last_reseed)); 109 110 state->nonce = 0; 111 state->ctr = 0; 112 state->reseed_cnt = 0; 113 state->failed_reseeds = 0; 114 state->callout_based_reseed = 0; 115 116 STATE_LOCK_INIT(state); 117 118 for (i = 0; i < 32; i++) { 119 r = csprng_pool_init(&state->pool[i], NULL, 0); 120 if (r != 0) 121 break; 122 POOL_LOCK_INIT(&state->pool[i]); 123 } 124 125 return r; 126 } 127 128 int 129 csprng_init_reseed(struct csprng_state *state) 130 { 131 state->callout_based_reseed = 1; 132 133 callout_init_mp(&state->reseed_callout); 134 callout_reset(&state->reseed_callout, MIN_RESEED_INTERVAL, 135 csprng_reseed_callout, state); 136 137 return 0; 138 } 139 140 /* 141 * XXX: 142 * Sources don't really a uniquely-allocated src id... 143 * another way we could do that is by simply using 144 * (uint8_t)__LINE__ as the source id... cheap & cheerful. 145 */ 146 147 static 148 int 149 encrypt_bytes(struct csprng_state *state, uint8_t *out, uint8_t *in, 150 size_t bytes) 151 { 152 /* Update nonce whenever the counter is about to overflow */ 153 if (chacha_check_counter(&state->cipher_ctx)) { 154 ++state->nonce; 155 chacha_ivsetup(&state->cipher_ctx, 156 (const uint8_t *)&state->nonce); 157 } 158 159 chacha_encrypt_bytes(&state->cipher_ctx, in, out, (uint32_t)bytes); 160 161 return 0; 162 } 163 164 /* 165 * XXX: flags is currently unused, but could be used to know whether 166 * it's a /dev/random or /dev/urandom read, and make sure that 167 * enough entropy has been collected recently, etc. 168 */ 169 int 170 csprng_get_random(struct csprng_state *state, uint8_t *out, int bytes, 171 int flags __unused) 172 { 173 int cnt; 174 int total_bytes = 0; 175 176 /* 177 * XXX: can optimize a bit by digging into chacha_encrypt_bytes 178 * and removing the xor of the stream with the input - that 179 * way we don't have to xor the output (which we provide 180 * as input). 181 */ 182 bzero(out, bytes); 183 184 STATE_LOCK(state); 185 186 again: 187 if (!state->callout_based_reseed && 188 ratecheck(&state->last_reseed, &csprng_reseed_interval)) { 189 csprng_reseed(state); 190 } 191 192 /* 193 * If no reseed has occurred yet, we can't possibly give out 194 * any random data. 195 * Sleep until entropy is added to the pools (or a callout-based 196 * reseed, if enabled, occurs). 197 */ 198 if (state->reseed_cnt == 0) { 199 STATE_SLEEP(state, "csprngrsd", 0); 200 goto again; 201 } 202 203 while (bytes > 0) { 204 /* Limit amount of output without rekeying to 2^20 */ 205 cnt = (bytes > (1 << 20)) ? (1 << 20) : bytes; 206 207 encrypt_bytes(state, out, out, cnt); 208 209 /* Update key and rekey cipher */ 210 encrypt_bytes(state, state->key, state->key, 211 sizeof(state->key)); 212 chacha_keysetup(&state->cipher_ctx, state->key, 213 8*sizeof(state->key)); 214 215 out += cnt; 216 bytes -= cnt; 217 total_bytes += cnt; 218 } 219 220 STATE_UNLOCK(state); 221 222 return total_bytes; 223 } 224 225 static 226 int 227 csprng_reseed(struct csprng_state *state) 228 { 229 int i; 230 struct csprng_pool *pool; 231 SHA256_CTX hash_ctx; 232 uint8_t digest[SHA256_DIGEST_LENGTH]; 233 234 /* 235 * If there's not enough entropy in the first 236 * pool, don't reseed. 237 */ 238 if (state->pool[0].bytes < MIN_POOL_SIZE) { 239 ++state->failed_reseeds; 240 return 1; 241 } 242 243 SHA256_Init(&hash_ctx); 244 245 /* 246 * Update hash that will result in new key with the 247 * old key. 248 */ 249 SHA256_Update(&hash_ctx, state->key, sizeof(state->key)); 250 251 state->reseed_cnt++; 252 253 for (i = 0; i < 32; i++) { 254 if ((state->reseed_cnt % (1 << i)) != 0) 255 break; 256 257 pool = &state->pool[i]; 258 POOL_LOCK(pool); 259 260 /* 261 * Finalize hash of the entropy in this pool. 262 */ 263 SHA256_Final(digest, &pool->hash_ctx); 264 265 /* 266 * Reinitialize pool with a hash of the old pool digest. 267 * This is a slight deviation from Fortuna as per reference, 268 * but is in line with other Fortuna implementations. 269 */ 270 csprng_pool_init(pool, digest, sizeof(digest)); 271 272 POOL_UNLOCK(pool); 273 274 /* 275 * Update hash that will result in new key with this 276 * pool's hashed entropy. 277 */ 278 SHA256_Update(&hash_ctx, digest, sizeof(digest)); 279 } 280 281 SHA256_Final(state->key, &hash_ctx); 282 283 /* Update key and rekey cipher */ 284 chacha_keysetup(&state->cipher_ctx, state->key, 285 8*sizeof(state->key)); 286 287 /* Increment the nonce if the counter overflows */ 288 if (chacha_incr_counter(&state->cipher_ctx)) { 289 ++state->nonce; 290 chacha_ivsetup(&state->cipher_ctx, 291 (const uint8_t *)&state->nonce); 292 } 293 294 return 0; 295 } 296 297 static 298 void 299 csprng_reseed_callout(void *arg) 300 { 301 struct csprng_state *state = (struct csprng_state *)arg; 302 int reseed_interval = MIN_RESEED_INTERVAL; 303 304 STATE_LOCK(state); 305 306 csprng_reseed(arg); 307 308 STATE_WAKEUP(state); 309 STATE_UNLOCK(state); 310 311 callout_reset(&state->reseed_callout, reseed_interval, 312 csprng_reseed_callout, state); 313 } 314 315 int 316 csprng_add_entropy(struct csprng_state *state, int src_id, 317 const uint8_t *entropy, size_t bytes, int flags) 318 { 319 struct csprng_pool *pool; 320 int pool_id; 321 322 /* 323 * Pick the next pool for this source on a round-robin 324 * basis. 325 */ 326 src_id &= 0xff; 327 pool_id = state->src_pool_idx[src_id]++ & 0x1f; 328 pool = &state->pool[pool_id]; 329 330 if (flags & CSPRNG_TRYLOCK) { 331 /* 332 * If we are asked to just try the lock instead 333 * of spinning until we get it, return if we 334 * can't get a hold of the lock right now. 335 */ 336 if (!POOL_TRYLOCK(pool)) 337 return -1; 338 } else { 339 POOL_LOCK(pool); 340 } 341 342 SHA256_Update(&pool->hash_ctx, (const uint8_t *)&src_id, 343 sizeof(src_id)); 344 SHA256_Update(&pool->hash_ctx, (const uint8_t *)&bytes, 345 sizeof(bytes)); 346 SHA256_Update(&pool->hash_ctx, entropy, bytes); 347 348 pool->bytes += bytes; 349 350 POOL_UNLOCK(pool); 351 352 /* 353 * If a wakeup is missed, it doesn't matter too much - it'll get 354 * woken up by the next add_entropy() call. 355 */ 356 STATE_WAKEUP(state); 357 358 return 0; 359 } 360