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/libkern/arc4random.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  * THE BEER-WARE LICENSE
    3  *
    4  * <dan@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
    5  * can do whatever you want with this stuff.  If we meet some day, and you
    6  * think this stuff is worth it, you can buy me a beer in return.
    7  *
    8  * Dan Moschuk
    9  */
   10 
   11 #include <sys/cdefs.h>
   12 __FBSDID("$FreeBSD$");
   13 
   14 #include <sys/types.h>
   15 #include <sys/param.h>
   16 #include <sys/kernel.h>
   17 #include <sys/random.h>
   18 #include <sys/libkern.h>
   19 #include <sys/lock.h>
   20 #include <sys/mutex.h>
   21 #include <sys/time.h>
   22 #include <sys/smp.h>
   23 #include <sys/malloc.h>
   24 
   25 #define ARC4_RESEED_BYTES 65536
   26 #define ARC4_RESEED_SECONDS 300
   27 #define ARC4_KEYBYTES 256
   28 
   29 int arc4rand_iniseed_state = ARC4_ENTR_NONE;
   30 
   31 MALLOC_DEFINE(M_ARC4RANDOM, "arc4random", "arc4random structures");
   32 
   33 struct arc4_s {
   34         struct mtx mtx;
   35         u_int8_t i, j;
   36         int numruns;
   37         u_int8_t sbox[256];
   38         time_t t_reseed;
   39 
   40 } __aligned(CACHE_LINE_SIZE);
   41 
   42 static struct arc4_s *arc4inst = NULL;
   43 
   44 #define ARC4_FOREACH(_arc4) \
   45         for (_arc4 = &arc4inst[0]; _arc4 <= &arc4inst[mp_maxid]; _arc4++)
   46 
   47 static u_int8_t arc4_randbyte(struct arc4_s *arc4);
   48 
   49 static __inline void
   50 arc4_swap(u_int8_t *a, u_int8_t *b)
   51 {
   52         u_int8_t c;
   53 
   54         c = *a;
   55         *a = *b;
   56         *b = c;
   57 }       
   58 
   59 /*
   60  * Stir our S-box.
   61  */
   62 static void
   63 arc4_randomstir(struct arc4_s* arc4)
   64 {
   65         u_int8_t key[ARC4_KEYBYTES];
   66         int n;
   67         struct timeval tv_now;
   68 
   69         /*
   70          * XXX: FIX!! This isn't brilliant. Need more confidence.
   71          * This returns zero entropy before random(4) is seeded.
   72          */
   73         (void)read_random(key, ARC4_KEYBYTES);
   74         getmicrouptime(&tv_now);
   75         mtx_lock(&arc4->mtx);
   76         for (n = 0; n < 256; n++) {
   77                 arc4->j = (arc4->j + arc4->sbox[n] + key[n]) % 256;
   78                 arc4_swap(&arc4->sbox[n], &arc4->sbox[arc4->j]);
   79         }
   80         arc4->i = arc4->j = 0;
   81         /* Reset for next reseed cycle. */
   82         arc4->t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS;
   83         arc4->numruns = 0;
   84         /*
   85          * Throw away the first N words of output, as suggested in the
   86          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
   87          * by Fluher, Mantin, and Shamir.  (N = 768 in our case.)
   88          *
   89          * http://dl.acm.org/citation.cfm?id=646557.694759
   90          */
   91         for (n = 0; n < 768*4; n++)
   92                 arc4_randbyte(arc4);
   93 
   94         mtx_unlock(&arc4->mtx);
   95 }
   96 
   97 /*
   98  * Initialize our S-box to its beginning defaults.
   99  */
  100 static void
  101 arc4_init(void)
  102 {
  103         struct arc4_s *arc4;
  104         int n;
  105 
  106         arc4inst = malloc((mp_maxid + 1) * sizeof(struct arc4_s),
  107                         M_ARC4RANDOM, M_NOWAIT | M_ZERO);
  108         KASSERT(arc4inst != NULL, ("arc4_init: memory allocation error"));
  109 
  110         ARC4_FOREACH(arc4) {
  111                 mtx_init(&arc4->mtx, "arc4_mtx", NULL, MTX_DEF);
  112 
  113                 arc4->i = arc4->j = 0;
  114                 for (n = 0; n < 256; n++)
  115                         arc4->sbox[n] = (u_int8_t) n;
  116 
  117                 arc4->t_reseed = -1;
  118                 arc4->numruns = 0;
  119         }
  120 }
  121 SYSINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_init, NULL);
  122 
  123 
  124 static void
  125 arc4_uninit(void)
  126 {
  127         struct arc4_s *arc4;
  128 
  129         ARC4_FOREACH(arc4) {
  130                 mtx_destroy(&arc4->mtx);
  131         }
  132 
  133         free(arc4inst, M_ARC4RANDOM);
  134 }
  135 
  136 SYSUNINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_uninit, NULL);
  137 
  138 
  139 /*
  140  * Generate a random byte.
  141  */
  142 static u_int8_t
  143 arc4_randbyte(struct arc4_s *arc4)
  144 {
  145         u_int8_t arc4_t;
  146 
  147         arc4->i = (arc4->i + 1) % 256;
  148         arc4->j = (arc4->j + arc4->sbox[arc4->i]) % 256;
  149 
  150         arc4_swap(&arc4->sbox[arc4->i], &arc4->sbox[arc4->j]);
  151 
  152         arc4_t = (arc4->sbox[arc4->i] + arc4->sbox[arc4->j]) % 256;
  153         return arc4->sbox[arc4_t];
  154 }
  155 
  156 /*
  157  * MPSAFE
  158  */
  159 void
  160 arc4rand(void *ptr, u_int len, int reseed)
  161 {
  162         u_char *p;
  163         struct timeval tv;
  164         struct arc4_s *arc4;
  165 
  166         if (reseed || atomic_cmpset_int(&arc4rand_iniseed_state,
  167                         ARC4_ENTR_HAVE, ARC4_ENTR_SEED)) {
  168                 ARC4_FOREACH(arc4)
  169                         arc4_randomstir(arc4);
  170         }
  171 
  172         arc4 = &arc4inst[curcpu];
  173         getmicrouptime(&tv);
  174         if ((arc4->numruns > ARC4_RESEED_BYTES) ||
  175                 (tv.tv_sec > arc4->t_reseed))
  176                 arc4_randomstir(arc4);
  177 
  178         mtx_lock(&arc4->mtx);
  179         arc4->numruns += len;
  180         p = ptr;
  181         while (len--)
  182                 *p++ = arc4_randbyte(arc4);
  183         mtx_unlock(&arc4->mtx);
  184 }
  185 
  186 uint32_t
  187 arc4random(void)
  188 {
  189         uint32_t ret;
  190 
  191         arc4rand(&ret, sizeof ret, 0);
  192         return ret;
  193 }

Cache object: b2720943ede01be14bb09cf97d4978e2


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