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, size_t bytes) 150 { 151 /* Update nonce whenever the counter is about to overflow */ 152 if (chacha_check_counter(&state->cipher_ctx)) { 153 ++state->nonce; 154 chacha_ivsetup(&state->cipher_ctx, (const uint8_t *)&state->nonce); 155 } 156 157 chacha_encrypt_bytes(&state->cipher_ctx, in, out, (uint32_t)bytes); 158 159 return 0; 160 } 161 162 /* 163 * XXX: flags is currently unused, but could be used to know whether 164 * it's a /dev/random or /dev/urandom read, and make sure that 165 * enough entropy has been collected recently, etc. 166 */ 167 int 168 csprng_get_random(struct csprng_state *state, uint8_t *out, int bytes, 169 int flags __unused) 170 { 171 int cnt; 172 int total_bytes = 0; 173 174 /* 175 * XXX: can optimize a bit by digging into chacha_encrypt_bytes 176 * and removing the xor of the stream with the input - that 177 * way we don't have to xor the output (which we provide 178 * as input). 179 */ 180 bzero(out, bytes); 181 182 STATE_LOCK(state); 183 184 again: 185 if (!state->callout_based_reseed && 186 ratecheck(&state->last_reseed, &csprng_reseed_interval)) { 187 csprng_reseed(state); 188 } 189 190 /* 191 * If no reseed has occurred yet, we can't possibly give out 192 * any random data. 193 * Sleep until entropy is added to the pools (or a callout-based 194 * reseed, if enabled, occurs). 195 */ 196 if (state->reseed_cnt == 0) { 197 STATE_SLEEP(state, "csprngrsd", 0); 198 goto again; 199 } 200 201 while (bytes > 0) { 202 /* Limit amount of output without rekeying to 2^20 */ 203 cnt = (bytes > (1 << 20)) ? (1 << 20) : bytes; 204 205 encrypt_bytes(state, out, out, cnt); 206 207 /* Update key and rekey cipher */ 208 encrypt_bytes(state, state->key, state->key, sizeof(state->key)); 209 chacha_keysetup(&state->cipher_ctx, state->key, 210 8*sizeof(state->key)); 211 212 out += cnt; 213 bytes -= cnt; 214 total_bytes += cnt; 215 } 216 217 STATE_UNLOCK(state); 218 219 return total_bytes; 220 } 221 222 static 223 int 224 csprng_reseed(struct csprng_state *state) 225 { 226 int i; 227 struct csprng_pool *pool; 228 SHA256_CTX hash_ctx; 229 uint8_t digest[SHA256_DIGEST_LENGTH]; 230 231 /* 232 * If there's not enough entropy in the first 233 * pool, don't reseed. 234 */ 235 if (state->pool[0].bytes < MIN_POOL_SIZE) { 236 ++state->failed_reseeds; 237 return 1; 238 } 239 240 SHA256_Init(&hash_ctx); 241 242 /* 243 * Update hash that will result in new key with the 244 * old key. 245 */ 246 SHA256_Update(&hash_ctx, state->key, sizeof(state->key)); 247 248 state->reseed_cnt++; 249 250 for (i = 0; i < 32; i++) { 251 if ((state->reseed_cnt % (1 << i)) != 0) 252 break; 253 254 pool = &state->pool[i]; 255 POOL_LOCK(pool); 256 257 /* 258 * Finalize hash of the entropy in this pool. 259 */ 260 SHA256_Final(digest, &pool->hash_ctx); 261 262 /* 263 * Reinitialize pool with a hash of the old pool digest. 264 * This is a slight deviation from Fortuna as per reference, 265 * but is in line with other Fortuna implementations. 266 */ 267 csprng_pool_init(pool, digest, sizeof(digest)); 268 269 POOL_UNLOCK(pool); 270 271 /* 272 * Update hash that will result in new key with this 273 * pool's hashed entropy. 274 */ 275 SHA256_Update(&hash_ctx, digest, sizeof(digest)); 276 } 277 278 SHA256_Final(state->key, &hash_ctx); 279 280 /* Update key and rekey cipher */ 281 chacha_keysetup(&state->cipher_ctx, state->key, 282 8*sizeof(state->key)); 283 284 /* Increment the nonce if the counter overflows */ 285 if (chacha_incr_counter(&state->cipher_ctx)) { 286 ++state->nonce; 287 chacha_ivsetup(&state->cipher_ctx, (const uint8_t *)&state->nonce); 288 } 289 290 return 0; 291 } 292 293 static 294 void 295 csprng_reseed_callout(void *arg) 296 { 297 struct csprng_state *state = (struct csprng_state *)arg; 298 int reseed_interval = MIN_RESEED_INTERVAL; 299 300 STATE_LOCK(state); 301 302 csprng_reseed(arg); 303 304 STATE_WAKEUP(state); 305 STATE_UNLOCK(state); 306 307 callout_reset(&state->reseed_callout, reseed_interval, 308 csprng_reseed_callout, state); 309 } 310 311 int 312 csprng_add_entropy(struct csprng_state *state, int src_id, 313 const uint8_t *entropy, size_t bytes, int flags) 314 { 315 struct csprng_pool *pool; 316 int pool_id; 317 318 /* 319 * Pick the next pool for this source on a round-robin 320 * basis. 321 */ 322 src_id &= 0xff; 323 pool_id = state->src_pool_idx[src_id]++ & 0x1f; 324 pool = &state->pool[pool_id]; 325 326 if (flags & CSPRNG_TRYLOCK) { 327 /* 328 * If we are asked to just try the lock instead 329 * of spinning until we get it, return if we 330 * can't get a hold of the lock right now. 331 */ 332 if (!POOL_TRYLOCK(pool)) 333 return -1; 334 } else { 335 POOL_LOCK(pool); 336 } 337 338 SHA256_Update(&pool->hash_ctx, (const uint8_t *)&src_id, sizeof(src_id)); 339 SHA256_Update(&pool->hash_ctx, (const uint8_t *)&bytes, sizeof(bytes)); 340 SHA256_Update(&pool->hash_ctx, entropy, bytes); 341 342 pool->bytes += bytes; 343 344 POOL_UNLOCK(pool); 345 346 /* 347 * If a wakeup is missed, it doesn't matter too much - it'll get woken 348 * up by the next add_entropy() call. 349 */ 350 STATE_WAKEUP(state); 351 352 return 0; 353 } 354