dist/ipf/arc4random.c

   1 /*      $NetBSD$        */
   2
   3 #ifdef NEED_LOCAL_RAND
   4 /*-
   5  * THE BEER-WARE LICENSE
   6  *
   7  * <dan@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
   8  * can do whatever you want with this stuff.  If we meet some day, and you
   9  * think this stuff is worth it, you can buy me a beer in return.
  10  *
  11  * Dan Moschuk
  12  */
  13 #if !defined(SOLARIS2) && !defined(__osf__)
  14 # include <sys/cdefs.h>
  15 #endif
  16
  17 #include <sys/types.h>
  18 #include <sys/param.h>
  19 #ifdef __FreeBSD__
  20 # include <sys/kernel.h>
  21 #endif
  22 #ifndef __osf__
  23 # include <sys/random.h>
  24 #endif
  25 #ifdef __FreeBSD__
  26 # include <sys/libkern.h>
  27 #endif
  28 #include <sys/lock.h>
  29 #ifndef __osf__
  30 # include <sys/mutex.h>
  31 #endif
  32 #include <sys/time.h>
  33
  34 #if defined(SOLARIS2) && (SOLARIS2 < 9)
  35 # include <netinet/in_systm.h>
  36 #endif
  37 #include <sys/socket.h>
  38 #include <net/if.h>
  39 #ifdef __osf__
  40 # include <net/route.h>
  41 #endif
  42 #include <netinet/in.h>
  43 #include <netinet/ip.h>
  44 #include "netinet/ip_compat.h"
  45 #include "md5.h"
  46
  47 #if !defined(__GNUC__)
  48 # define __inline
  49 #endif
  50
  51 #define ARC4_RESEED_BYTES 65536
  52 #define ARC4_RESEED_SECONDS 300
  53 #define ARC4_KEYBYTES (256 / 8)
  54
  55 static u_int8_t arc4_i, arc4_j;
  56 static int arc4_numruns = 0;
  57 static u_int8_t arc4_sbox[256];
  58 static time_t arc4_t_reseed;
  59 static ipfmutex_t arc4_mtx;
  60 static MD5_CTX md5ctx;
  61
  62 static u_int8_t arc4_randbyte(void);
  63 static int ipf_read_random(void *dest, int length);
  64
  65 static __inline void
  66 arc4_swap(u_int8_t *a, u_int8_t *b)
  67 {
  68         u_int8_t c;
  69
  70         c = *a;
  71         *a = *b;
  72         *b = c;
  73 }
  74
  75 /*
  76  * Stir our S-box.
  77  */
  78 static void
  79 arc4_randomstir (void)
  80 {
  81         u_int8_t key[256];
  82         int r, n;
  83         struct timeval tv_now;
  84
  85         /*
  86          * XXX read_random() returns unsafe numbers if the entropy
  87          * device is not loaded -- MarkM.
  88          */
  89         r = ipf_read_random(key, ARC4_KEYBYTES);
  90         GETKTIME(&tv_now);
  91         MUTEX_ENTER(&arc4_mtx);
  92         /* If r == 0 || -1, just use what was on the stack. */
  93         if (r > 0) {
  94                 for (n = r; n < sizeof(key); n++)
  95                         key[n] = key[n % r];
  96         }
  97
  98         for (n = 0; n < 256; n++) {
  99                 arc4_j = (arc4_j + arc4_sbox[n] + key[n]) % 256;
 100                 arc4_swap(&arc4_sbox[n], &arc4_sbox[arc4_j]);
 101         }
 102
 103         /* Reset for next reseed cycle. */
 104         arc4_t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS;
 105         arc4_numruns = 0;
 106
 107         /*
 108          * Throw away the first N words of output, as suggested in the
 109          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 110          * by Fluher, Mantin, and Shamir.  (N = 256 in our case.)
 111          */
 112         for (n = 0; n < 256*4; n++)
 113                 arc4_randbyte();
 114         MUTEX_EXIT(&arc4_mtx);
 115 }
 116
 117 /*
 118  * Initialize our S-box to its beginning defaults.
 119  */
 120 static void
 121 arc4_init(void)
 122 {
 123         int n;
 124
 125         MD5Init(&md5ctx);
 126
 127         MUTEX_INIT(&arc4_mtx, "arc4_mtx");
 128         arc4_i = arc4_j = 0;
 129         for (n = 0; n < 256; n++)
 130                 arc4_sbox[n] = (u_int8_t) n;
 131
 132         arc4_t_reseed = 0;
 133 }
 134
 135
 136 /*
 137  * Generate a random byte.
 138  */
 139 static u_int8_t
 140 arc4_randbyte(void)
 141 {
 142         u_int8_t arc4_t;
 143
 144         arc4_i = (arc4_i + 1) % 256;
 145         arc4_j = (arc4_j + arc4_sbox[arc4_i]) % 256;
 146
 147         arc4_swap(&arc4_sbox[arc4_i], &arc4_sbox[arc4_j]);
 148
 149         arc4_t = (arc4_sbox[arc4_i] + arc4_sbox[arc4_j]) % 256;
 150         return arc4_sbox[arc4_t];
 151 }
 152
 153 /*
 154  * MPSAFE
 155  */
 156 void
 157 arc4rand(void *ptr, u_int len, int reseed)
 158 {
 159         u_int8_t *p;
 160         struct timeval tv;
 161
 162         GETKTIME(&tv);
 163         if (reseed ||
 164            (arc4_numruns > ARC4_RESEED_BYTES) ||
 165            (tv.tv_sec > arc4_t_reseed))
 166                 arc4_randomstir();
 167
 168         MUTEX_ENTER(&arc4_mtx);
 169         arc4_numruns += len;
 170         p = ptr;
 171         while (len--)
 172                 *p++ = arc4_randbyte();
 173         MUTEX_EXIT(&arc4_mtx);
 174 }
 175
 176 uint32_t
 177 ipf_random(void)
 178 {
 179         uint32_t ret;
 180
 181         arc4rand(&ret, sizeof ret, 0);
 182         return ret;
 183 }
 184
 185
 186 static u_char pot[ARC4_RESEED_BYTES];
 187 static u_char *pothead = pot, *pottail = pot;
 188 static int inpot = 0;
 189
 190 /*
 191  * This is not very strong, and this is understood, but the aim isn't to
 192  * be cryptographically strong - it is just to make up something that is
 193  * pseudo random.
 194  */
 195 void
 196 ipf_rand_push(void *src, int length)
 197 {
 198         static int arc4_inited = 0;
 199         u_char *nsrc;
 200         int mylen;
 201
 202         if (arc4_inited == 0) {
 203                 arc4_init();
 204                 arc4_inited = 1;
 205         }
 206
 207         if (length < 64) {
 208                 MD5Update(&md5ctx, src, length);
 209                 return;
 210         }
 211
 212         nsrc = src;
 213         mylen = length;
 214
 215 #if defined(_SYS_MD5_H) && defined(SOLARIS2)
 216 # define        buf     buf_un.buf8
 217 #endif
 218         MUTEX_ENTER(&arc4_mtx);
 219         while ((mylen > 64)  && (sizeof(pot) - inpot > sizeof(md5ctx.buf))) {
 220                 MD5Update(&md5ctx, nsrc, 64);
 221                 mylen -= 64;
 222                 nsrc += 64;
 223                 if (pottail + sizeof(md5ctx.buf) > pot + sizeof(pot)) {
 224                         int left, numbytes;
 225
 226                         numbytes = pot + sizeof(pot) - pottail;
 227                         bcopy(md5ctx.buf, pottail, numbytes);
 228                         left = sizeof(md5ctx.buf) - numbytes;
 229                         pottail = pot;
 230                         bcopy(md5ctx.buf + sizeof(md5ctx.buf) - left,
 231                               pottail, left);
 232                         pottail += left;
 233                 } else {
 234                         bcopy(md5ctx.buf, pottail, sizeof(md5ctx.buf));
 235                         pottail += sizeof(md5ctx.buf);
 236                 }
 237                 inpot += 64;
 238         }
 239         MUTEX_EXIT(&arc4_mtx);
 240 #if defined(_SYS_MD5_H) && defined(SOLARIS2)
 241 # undef buf
 242 #endif
 243 }
 244
 245
 246 static int
 247 ipf_read_random(void *dest, int length)
 248 {
 249         if (length > inpot)
 250                 return 0;
 251
 252         MUTEX_ENTER(&arc4_mtx);
 253         if (pothead + length > pot + sizeof(pot)) {
 254                 int left, numbytes;
 255
 256                 left = length;
 257                 numbytes = pot + sizeof(pot) - pothead;
 258                 bcopy(pothead, dest, numbytes);
 259                 left -= numbytes;
 260                 pothead = pot;
 261                 bcopy(pothead, dest + length - left, left);
 262                 pothead += left;
 263         } else {
 264                 bcopy(pothead, dest, length);
 265                 pothead += length;
 266         }
 267         inpot -= length;
 268         if (inpot == 0)
 269                 pothead = pottail = pot;
 270         MUTEX_EXIT(&arc4_mtx);
 271
 272         return length;
 273 }
 274
 275 #endif /* NEED_LOCAL_RAND */