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/rndpool.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 /*      $NetBSD: rndpool.c,v 1.17 2002/11/10 03:29:00 thorpej Exp $        */
    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  * 3. All advertising materials mentioning features or use of this software
   20  *    must display the following acknowledgement:
   21  *        This product includes software developed by the NetBSD
   22  *        Foundation, Inc. and its contributors.
   23  * 4. Neither the name of The NetBSD Foundation nor the names of its
   24  *    contributors may be used to endorse or promote products derived
   25  *    from this software without specific prior written permission.
   26  *
   27  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
   28  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
   29  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
   30  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
   31  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   32  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   33  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   34  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   35  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   36  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   37  * POSSIBILITY OF SUCH DAMAGE.
   38  */
   39 
   40 #include <sys/cdefs.h>
   41 __KERNEL_RCSID(0, "$NetBSD: rndpool.c,v 1.17 2002/11/10 03:29:00 thorpej Exp $");
   42 
   43 #include <sys/param.h>
   44 #include <sys/systm.h>
   45 #include <sys/sha1.h>
   46 
   47 #include <sys/rnd.h>
   48 
   49 /*
   50  * The random pool "taps"
   51  */
   52 #define TAP1    99
   53 #define TAP2    59
   54 #define TAP3    31
   55 #define TAP4     9
   56 #define TAP5     7
   57 
   58 static inline void rndpool_add_one_word(rndpool_t *, u_int32_t);
   59 
   60 void
   61 rndpool_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 <= 20); /* XXX sha knowledge */
   75 }
   76 
   77 u_int32_t
   78 rndpool_get_entropy_count(rndpool_t *rp)
   79 {
   80 
   81         return (rp->stats.curentropy);
   82 }
   83 
   84 void rndpool_get_stats(rndpool_t *rp, void *rsp, int size)
   85 {
   86 
   87         memcpy(rsp, &rp->stats, size);
   88 }
   89 
   90 void
   91 rndpool_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 
  102 u_int32_t *
  103 rndpool_get_pool(rndpool_t *rp)
  104 {
  105 
  106         return (rp->pool);
  107 }
  108 
  109 u_int32_t
  110 rndpool_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  */
  154 static inline void
  155 rndpool_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 #if 0
  183 /*
  184  * Stir a 32-bit value (with possibly less entropy than that) into the pool.
  185  * Update entropy estimate.
  186  */
  187 void
  188 rndpool_add_uint32(rndpool_t *rp, u_int32_t  val, u_int32_t  entropy)
  189 {
  190         rndpool_add_one_word(rp, val);
  191 
  192         rp->entropy += entropy;
  193         rp->stats.added += entropy;
  194         if (rp->entropy > RND_POOLBITS) {
  195                 rp->stats.discarded += (rp->entropy - RND_POOLBITS);
  196                 rp->entropy = RND_POOLBITS;
  197         }
  198 }
  199 #endif
  200 
  201 /*
  202  * Add a buffer's worth of data to the pool.
  203  */
  204 void
  205 rndpool_add_data(rndpool_t *rp, void *p, u_int32_t len, u_int32_t entropy)
  206 {
  207         u_int32_t val;
  208         u_int8_t *buf;
  209 
  210         buf = p;
  211 
  212         for (; len > 3; len -= 4) {
  213                 val = *((u_int32_t *)buf);
  214 
  215                 rndpool_add_one_word(rp, val);
  216                 buf += 4;
  217         }
  218 
  219         if (len != 0) {
  220                 val = 0;
  221                 switch (len) {
  222                 case 3:
  223                         val = *buf++;
  224                 case 2:
  225                         val = val << 8 | *buf++;
  226                 case 1:
  227                         val = val << 8 | *buf++;
  228                 }
  229 
  230                 rndpool_add_one_word(rp, val);
  231         }
  232 
  233         rp->stats.curentropy += entropy;
  234         rp->stats.added += entropy;
  235 
  236         if (rp->stats.curentropy > RND_POOLBITS) {
  237                 rp->stats.discarded += (rp->stats.curentropy - RND_POOLBITS);
  238                 rp->stats.curentropy = RND_POOLBITS;
  239         }
  240 }
  241 
  242 /*
  243  * Extract some number of bytes from the random pool, decreasing the
  244  * estimate of randomness as each byte is extracted.
  245  *
  246  * Do this by hashing the pool and returning a part of the hash as
  247  * randomness.  Stir the hash back into the pool.  Note that no
  248  * secrets going back into the pool are given away here since parts of
  249  * the hash are xored together before being returned.
  250  *
  251  * Honor the request from the caller to only return good data, any data,
  252  * etc.  Note that we must have at least 64 bits of entropy in the pool
  253  * before we return anything in the high-quality modes.
  254  */
  255 u_int32_t
  256 rndpool_extract_data(rndpool_t *rp, void *p, u_int32_t len, u_int32_t mode)
  257 {
  258         u_int i;
  259         SHA1_CTX hash;
  260         u_char digest[20];      /* XXX SHA knowledge */
  261         u_int32_t remain, deltae, count;
  262         u_int8_t *buf;
  263         int good;
  264 
  265         buf = p;
  266         remain = len;
  267 
  268         if (mode == RND_EXTRACT_ANY)
  269                 good = 1;
  270         else
  271                 good = (rp->stats.curentropy >= (8 * RND_ENTROPY_THRESHOLD));
  272 
  273         KASSERT(RND_ENTROPY_THRESHOLD*2 <= 20); /* XXX SHA knowledge */
  274 
  275         while (good && (remain != 0)) {
  276                 /*
  277                  * While bytes are requested, compute the hash of the pool,
  278                  * and then "fold" the hash in half with XOR, keeping the
  279                  * exact hash value secret, as it will be stirred back into
  280                  * the pool.
  281                  *
  282                  * XXX this approach needs examination by competant
  283                  * cryptographers!  It's rather expensive per bit but
  284                  * also involves every bit of the pool in the
  285                  * computation of every output bit..
  286                  */
  287                 SHA1Init(&hash);
  288                 SHA1Update(&hash, (u_int8_t *)rp->pool, RND_POOLWORDS * 4);
  289                 SHA1Final(digest, &hash);
  290 
  291                 /*
  292                  * Stir the hash back into the pool.  This guarantees
  293                  * that the next hash will generate a different value
  294                  * if no new values were added to the pool.
  295                  */
  296                 for (i = 0; i < 5; i++) {
  297                         u_int32_t word;
  298                         memcpy(&word, &digest[i * 4], 4);
  299                         rndpool_add_one_word(rp, word);
  300                 }
  301 
  302                 count = min(remain, RND_ENTROPY_THRESHOLD);
  303 
  304                 for (i = 0; i < count; i++)
  305                         buf[i] = digest[i] ^ digest[i + RND_ENTROPY_THRESHOLD];
  306 
  307                 buf += count;
  308                 deltae = count * 8;
  309                 remain -= count;
  310 
  311                 deltae = min(deltae, rp->stats.curentropy);
  312 
  313                 rp->stats.removed += deltae;
  314                 rp->stats.curentropy -= deltae;
  315 
  316                 if (rp->stats.curentropy == 0)
  317                         rp->stats.generated += (count * 8) - deltae;
  318 
  319                 if (mode == RND_EXTRACT_GOOD)
  320                         good = (rp->stats.curentropy >=
  321                             (8 * RND_ENTROPY_THRESHOLD));
  322         }
  323 
  324         memset(&hash, 0, sizeof(hash));
  325         memset(digest, 0, sizeof(digest));
  326 
  327         return (len - remain);
  328 }

Cache object: 339eeec61cc7e27e1cf95053f8428dd1


[ 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.