The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/dev/random/yarrow.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  * Copyright (c) 2000-2004 Mark R V Murray
    3  * All rights reserved.
    4  *
    5  * Redistribution and use in source and binary forms, with or without
    6  * modification, are permitted provided that the following conditions
    7  * are met:
    8  * 1. Redistributions of source code must retain the above copyright
    9  *    notice, this list of conditions and the following disclaimer
   10  *    in this position and unchanged.
   11  * 2. Redistributions in binary form must reproduce the above copyright
   12  *    notice, this list of conditions and the following disclaimer in the
   13  *    documentation and/or other materials provided with the distribution.
   14  *
   15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
   16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
   18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
   19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
   20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
   22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
   24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   25  *
   26  */
   27 
   28 #include <sys/cdefs.h>
   29 __FBSDID("$FreeBSD: releng/8.1/sys/dev/random/yarrow.c 174073 2007-11-29 16:06:12Z simon $");
   30 
   31 #include <sys/param.h>
   32 #include <sys/kernel.h>
   33 #include <sys/lock.h>
   34 #include <sys/malloc.h>
   35 #include <sys/mutex.h>
   36 #include <sys/random.h>
   37 #include <sys/sysctl.h>
   38 #include <sys/systm.h>
   39 
   40 #include <crypto/rijndael/rijndael-api-fst.h>
   41 #include <crypto/sha2/sha2.h>
   42 
   43 #include <dev/random/hash.h>
   44 #include <dev/random/randomdev_soft.h>
   45 #include <dev/random/yarrow.h>
   46 
   47 RANDOM_CHECK_UINT(gengateinterval, 4, 64);
   48 RANDOM_CHECK_UINT(bins, 2, 16);
   49 RANDOM_CHECK_UINT(fastthresh, BLOCKSIZE/4, BLOCKSIZE);
   50 RANDOM_CHECK_UINT(slowthresh, BLOCKSIZE/4, BLOCKSIZE);
   51 RANDOM_CHECK_UINT(slowoverthresh, 1, 5);
   52 
   53 /* Structure holding the entropy state */
   54 static struct random_state random_state;
   55 
   56 static void generator_gate(void);
   57 static void reseed(u_int);
   58 
   59 /* The reseed thread mutex */
   60 struct mtx random_reseed_mtx;
   61 
   62 /* Process a single stochastic event off the harvest queue */
   63 void
   64 random_process_event(struct harvest *event)
   65 {
   66         u_int pl, overthreshhold[2];
   67         struct source *source;
   68         enum esource src;
   69 
   70         /* Unpack the event into the appropriate source accumulator */
   71         pl = random_state.which;
   72         source = &random_state.pool[pl].source[event->source];
   73         yarrow_hash_iterate(&random_state.pool[pl].hash, event->entropy,
   74                 sizeof(event->entropy));
   75         yarrow_hash_iterate(&random_state.pool[pl].hash, &event->somecounter,
   76                 sizeof(event->somecounter));
   77         source->frac += event->frac;
   78         source->bits += event->bits + source->frac/1024;
   79         source->frac %= 1024;
   80 
   81         /* Count the over-threshold sources in each pool */
   82         for (pl = 0; pl < 2; pl++) {
   83                 overthreshhold[pl] = 0;
   84                 for (src = RANDOM_START; src < ENTROPYSOURCE; src++) {
   85                         if (random_state.pool[pl].source[src].bits
   86                                 > random_state.pool[pl].thresh)
   87                                 overthreshhold[pl]++;
   88                 }
   89         }
   90 
   91         /* if any fast source over threshhold, reseed */
   92         if (overthreshhold[FAST])
   93                 reseed(FAST);
   94 
   95         /* if enough slow sources are over threshhold, reseed */
   96         if (overthreshhold[SLOW] >= random_state.slowoverthresh)
   97                 reseed(SLOW);
   98 
   99         /* Invert the fast/slow pool selector bit */
  100         random_state.which = !random_state.which;
  101 }
  102 
  103 void
  104 random_yarrow_init_alg(struct sysctl_ctx_list *clist, struct sysctl_oid *in_o)
  105 {
  106         int i;
  107         struct sysctl_oid *random_yarrow_o;
  108 
  109         /* Yarrow parameters. Do not adjust these unless you have
  110          * have a very good clue about what they do!
  111          */
  112         random_yarrow_o = SYSCTL_ADD_NODE(clist,
  113                 SYSCTL_CHILDREN(in_o),
  114                 OID_AUTO, "yarrow", CTLFLAG_RW, 0,
  115                 "Yarrow Parameters");
  116 
  117         SYSCTL_ADD_PROC(clist,
  118                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
  119                 "gengateinterval", CTLTYPE_INT|CTLFLAG_RW,
  120                 &random_state.gengateinterval, 10,
  121                 random_check_uint_gengateinterval, "I",
  122                 "Generation gate interval");
  123 
  124         SYSCTL_ADD_PROC(clist,
  125                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
  126                 "bins", CTLTYPE_INT|CTLFLAG_RW,
  127                 &random_state.bins, 10,
  128                 random_check_uint_bins, "I",
  129                 "Execution time tuner");
  130 
  131         SYSCTL_ADD_PROC(clist,
  132                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
  133                 "fastthresh", CTLTYPE_INT|CTLFLAG_RW,
  134                 &random_state.pool[0].thresh, (3*BLOCKSIZE)/4,
  135                 random_check_uint_fastthresh, "I",
  136                 "Fast reseed threshold");
  137 
  138         SYSCTL_ADD_PROC(clist,
  139                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
  140                 "slowthresh", CTLTYPE_INT|CTLFLAG_RW,
  141                 &random_state.pool[1].thresh, BLOCKSIZE,
  142                 random_check_uint_slowthresh, "I",
  143                 "Slow reseed threshold");
  144 
  145         SYSCTL_ADD_PROC(clist,
  146                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
  147                 "slowoverthresh", CTLTYPE_INT|CTLFLAG_RW,
  148                 &random_state.slowoverthresh, 2,
  149                 random_check_uint_slowoverthresh, "I",
  150                 "Slow over-threshold reseed");
  151 
  152         random_state.gengateinterval = 10;
  153         random_state.bins = 10;
  154         random_state.pool[0].thresh = (3*BLOCKSIZE)/4;
  155         random_state.pool[1].thresh = BLOCKSIZE;
  156         random_state.slowoverthresh = 2;
  157         random_state.which = FAST;
  158 
  159         /* Initialise the fast and slow entropy pools */
  160         for (i = 0; i < 2; i++)
  161                 yarrow_hash_init(&random_state.pool[i].hash);
  162 
  163         /* Clear the counter */
  164         for (i = 0; i < 4; i++)
  165                 random_state.counter[i] = 0;
  166 
  167         /* Set up a lock for the reseed process */
  168         mtx_init(&random_reseed_mtx, "random reseed", NULL, MTX_DEF);
  169 }
  170 
  171 void
  172 random_yarrow_deinit_alg(void)
  173 {
  174         mtx_destroy(&random_reseed_mtx);
  175 }
  176 
  177 static void
  178 reseed(u_int fastslow)
  179 {
  180         /* Interrupt-context stack is a limited resource; make large
  181          * structures static.
  182          */
  183         static u_char v[TIMEBIN][KEYSIZE];      /* v[i] */
  184         static struct yarrowhash context;
  185         u_char hash[KEYSIZE];                   /* h' */
  186         u_char temp[KEYSIZE];
  187         u_int i;
  188         enum esource j;
  189 
  190         /* The reseed task must not be jumped on */
  191         mtx_lock(&random_reseed_mtx);
  192 
  193         /* 1. Hash the accumulated entropy into v[0] */
  194 
  195         yarrow_hash_init(&context);
  196         /* Feed the slow pool hash in if slow */
  197         if (fastslow == SLOW)
  198                 yarrow_hash_iterate(&context,
  199                         &random_state.pool[SLOW].hash,
  200                         sizeof(struct yarrowhash));
  201         yarrow_hash_iterate(&context,
  202                 &random_state.pool[FAST].hash, sizeof(struct yarrowhash));
  203         yarrow_hash_finish(&context, v[0]);
  204 
  205         /* 2. Compute hash values for all v. _Supposed_ to be computationally
  206          *    intensive.
  207          */
  208 
  209         if (random_state.bins > TIMEBIN)
  210                 random_state.bins = TIMEBIN;
  211         for (i = 1; i < random_state.bins; i++) {
  212                 yarrow_hash_init(&context);
  213                 /* v[i] #= h(v[i - 1]) */
  214                 yarrow_hash_iterate(&context, v[i - 1], KEYSIZE);
  215                 /* v[i] #= h(v[0]) */
  216                 yarrow_hash_iterate(&context, v[0], KEYSIZE);
  217                 /* v[i] #= h(i) */
  218                 yarrow_hash_iterate(&context, &i, sizeof(u_int));
  219                 /* Return the hashval */
  220                 yarrow_hash_finish(&context, v[i]);
  221         }
  222 
  223         /* 3. Compute a new key; h' is the identity function here;
  224          *    it is not being ignored!
  225          */
  226 
  227         yarrow_hash_init(&context);
  228         yarrow_hash_iterate(&context, &random_state.key, KEYSIZE);
  229         for (i = 1; i < random_state.bins; i++)
  230                 yarrow_hash_iterate(&context, &v[i], KEYSIZE);
  231         yarrow_hash_finish(&context, temp);
  232         yarrow_encrypt_init(&random_state.key, temp);
  233 
  234         /* 4. Recompute the counter */
  235 
  236         for (i = 0; i < 4; i++)
  237                 random_state.counter[i] = 0;
  238         yarrow_encrypt(&random_state.key, random_state.counter, temp);
  239         memcpy(random_state.counter, temp, sizeof(random_state.counter));
  240 
  241         /* 5. Reset entropy estimate accumulators to zero */
  242 
  243         for (i = 0; i <= fastslow; i++) {
  244                 for (j = RANDOM_START; j < ENTROPYSOURCE; j++) {
  245                         random_state.pool[i].source[j].bits = 0;
  246                         random_state.pool[i].source[j].frac = 0;
  247                 }
  248         }
  249 
  250         /* 6. Wipe memory of intermediate values */
  251 
  252         memset((void *)v, 0, sizeof(v));
  253         memset((void *)temp, 0, sizeof(temp));
  254         memset((void *)hash, 0, sizeof(hash));
  255 
  256         /* 7. Dump to seed file */
  257         /* XXX Not done here yet */
  258 
  259         /* Unblock the device if it was blocked due to being unseeded */
  260         random_yarrow_unblock();
  261 
  262         /* Release the reseed mutex */
  263         mtx_unlock(&random_reseed_mtx);
  264 }
  265 
  266 /* Internal function to return processed entropy from the PRNG */
  267 int
  268 random_yarrow_read(void *buf, int count)
  269 {
  270         static int cur = 0;
  271         static int gate = 1;
  272         static u_char genval[KEYSIZE];
  273         size_t tomove;
  274         int i;
  275         int retval;
  276 
  277         /* The reseed task must not be jumped on */
  278         mtx_lock(&random_reseed_mtx);
  279 
  280         if (gate) {
  281                 generator_gate();
  282                 random_state.outputblocks = 0;
  283                 gate = 0;
  284         }
  285         if (count > 0 && (size_t)count >= sizeof(random_state.counter)) {
  286                 retval = 0;
  287                 for (i = 0; i < count; i += (int)sizeof(random_state.counter)) {
  288                         random_state.counter[0]++;
  289                         yarrow_encrypt(&random_state.key, random_state.counter,
  290                                 genval);
  291                         tomove = min(count - i, sizeof(random_state.counter));
  292                         memcpy((char *)buf + i, genval, tomove);
  293                         if (++random_state.outputblocks >=
  294                                 random_state.gengateinterval) {
  295                                 generator_gate();
  296                                 random_state.outputblocks = 0;
  297                         }
  298                         retval += (int)tomove;
  299                         cur = 0;
  300                 }
  301         }
  302         else {
  303                 if (!cur) {
  304                         random_state.counter[0]++;
  305                         yarrow_encrypt(&random_state.key, random_state.counter,
  306                                 genval);
  307                         memcpy(buf, genval, (size_t)count);
  308                         cur = (int)sizeof(random_state.counter) - count;
  309                         if (++random_state.outputblocks >=
  310                                 random_state.gengateinterval) {
  311                                 generator_gate();
  312                                 random_state.outputblocks = 0;
  313                         }
  314                         retval = count;
  315                 }
  316                 else {
  317                         retval = MIN(cur, count);
  318                         memcpy(buf,
  319                             &genval[(int)sizeof(random_state.counter) - cur],
  320                             (size_t)retval);
  321                         cur -= retval;
  322                 }
  323         }
  324         mtx_unlock(&random_reseed_mtx);
  325         return retval;
  326 }
  327 
  328 static void
  329 generator_gate(void)
  330 {
  331         u_int i;
  332         u_char temp[KEYSIZE];
  333 
  334         for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) {
  335                 random_state.counter[0]++;
  336                 yarrow_encrypt(&random_state.key, random_state.counter,
  337                         &(temp[i]));
  338         }
  339 
  340         yarrow_encrypt_init(&random_state.key, temp);
  341         memset((void *)temp, 0, KEYSIZE);
  342 
  343 }
  344 
  345 /* Helper routine to perform explicit reseeds */
  346 void
  347 random_yarrow_reseed(void)
  348 {
  349         reseed(SLOW);
  350 }

Cache object: 6ea5b59a7990298a0fa0f7d92bc9dba5


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.