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