sys/kern/subr_csprng.c

   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 }