contrib/ipfilter/arc4random.c

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