sys/lib/libkern/arc4random.c

   1 /*      $NetBSD: arc4random.c,v 1.19 2007/07/19 22:00:04 dsl Exp $      */
   2
   3 /*-
   4  * Copyright (c) 2002 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Thor Lancelot Simon.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 /*-
  33  * THE BEER-WARE LICENSE
  34  *
  35  * <dan@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
  36  * can do whatever you want with this stuff.  If we meet some day, and you
  37  * think this stuff is worth it, you can buy me a beer in return.
  38  *
  39  * Dan Moschuk
  40  *
  41  * $FreeBSD: src/sys/libkern/arc4random.c,v 1.9 2001/08/30 12:30:58 bde Exp $
  42  */
  43
  44 #include <sys/cdefs.h>
  45
  46 #ifdef _KERNEL
  47 #include "rnd.h"
  48 #else
  49 #define NRND 0
  50 #endif
  51
  52 #include <sys/types.h>
  53 #include <sys/time.h>
  54 #include <sys/param.h>
  55 #ifdef _KERNEL
  56 #include <sys/kernel.h>
  57 #endif
  58 #include <sys/systm.h>
  59
  60 #include <lib/libkern/libkern.h>
  61
  62 #if NRND > 0
  63 #include <sys/rnd.h>
  64 #endif
  65
  66 #define ARC4_MAXRUNS 16384
  67 #define ARC4_RESEED_SECONDS 300
  68 #define ARC4_KEYBYTES 32 /* 256 bit key */
  69
  70 #ifdef _STANDALONE
  71 #define time_uptime     1       /* XXX ugly! */
  72 #endif /* _STANDALONE */
  73
  74 static u_int8_t arc4_i, arc4_j;
  75 static int arc4_initialized = 0;
  76 static int arc4_numruns = 0;
  77 static u_int8_t arc4_sbox[256];
  78 static time_t arc4_nextreseed;
  79
  80 static inline u_int8_t arc4_randbyte(void);
  81
  82 static inline void
  83 arc4_swap(u_int8_t *a, u_int8_t *b)
  84 {
  85         u_int8_t c;
  86
  87         c = *a;
  88         *a = *b;
  89         *b = c;
  90 }
  91
  92 /*
  93  * Stir our S-box.
  94  */
  95 static void
  96 arc4_randrekey(void)
  97 {
  98         u_int8_t key[256];
  99         static int cur_keybytes;
 100         int n, byteswanted;
 101 #if NRND > 0
 102         int r;
 103 #endif
 104
 105         if(!arc4_initialized)
 106                 /* The first time through, we must take what we can get */
 107                 byteswanted = 0;
 108         else
 109                 /* Don't rekey with less entropy than we already have */
 110                 byteswanted = cur_keybytes;
 111
 112 #if NRND > 0    /* XXX without rnd, we will key from the stack, ouch! */
 113         r = rnd_extract_data(key, ARC4_KEYBYTES, RND_EXTRACT_GOOD);
 114
 115         if (r < ARC4_KEYBYTES) {
 116                 if (r >= byteswanted) {
 117                         (void)rnd_extract_data(key + r,
 118                                                ARC4_KEYBYTES - r,
 119                                                RND_EXTRACT_ANY);
 120                 } else {
 121                         /* don't replace a good key with a bad one! */
 122                         arc4_nextreseed = time_uptime + ARC4_RESEED_SECONDS;
 123                         arc4_numruns = 0;
 124                         /* we should just ask rnd(4) to rekey us when
 125                            it can, but for now, we'll just try later. */
 126                         return;
 127                 }
 128         }
 129
 130         cur_keybytes = r;
 131
 132         for (n = ARC4_KEYBYTES; n < sizeof(key); n++)
 133                         key[n] = key[n % ARC4_KEYBYTES];
 134 #endif
 135         for (n = 0; n < 256; n++) {
 136                 arc4_j = (arc4_j + arc4_sbox[n] + key[n]) % 256;
 137                 arc4_swap(&arc4_sbox[n], &arc4_sbox[arc4_j]);
 138         }
 139
 140         /* Reset for next reseed cycle. */
 141         arc4_nextreseed = time_uptime + ARC4_RESEED_SECONDS;
 142         arc4_numruns = 0;
 143
 144         /*
 145          * Throw away the first N words of output, as suggested in the
 146          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 147          * by Fluher, Mantin, and Shamir.  (N = 256 in our case.)
 148          */
 149         for (n = 0; n < 256 * 4; n++)
 150                 arc4_randbyte();
 151 }
 152
 153 /*
 154  * Initialize our S-box to its beginning defaults.
 155  */
 156 static void
 157 arc4_init(void)
 158 {
 159         int n;
 160
 161         arc4_i = arc4_j = 0;
 162         for (n = 0; n < 256; n++)
 163                 arc4_sbox[n] = (u_int8_t) n;
 164
 165         arc4_randrekey();
 166         arc4_initialized = 1;
 167 }
 168
 169 /*
 170  * Generate a random byte.
 171  */
 172 static inline u_int8_t
 173 arc4_randbyte(void)
 174 {
 175         u_int8_t arc4_t;
 176
 177         arc4_i = (arc4_i + 1) % 256;
 178         arc4_j = (arc4_j + arc4_sbox[arc4_i]) % 256;
 179
 180         arc4_swap(&arc4_sbox[arc4_i], &arc4_sbox[arc4_j]);
 181
 182         arc4_t = (arc4_sbox[arc4_i] + arc4_sbox[arc4_j]) % 256;
 183         return arc4_sbox[arc4_t];
 184 }
 185
 186 u_int32_t
 187 arc4random(void)
 188 {
 189         u_int32_t ret;
 190         int i;
 191
 192         /* Initialize array if needed. */
 193         if (!arc4_initialized)
 194                 arc4_init();
 195
 196         if ((++arc4_numruns > ARC4_MAXRUNS) ||
 197             (time_uptime > arc4_nextreseed)) {
 198                 arc4_randrekey();
 199         }
 200
 201         for (i = 0, ret = 0; i <= 24; ret |= arc4_randbyte() << i, i += 8)
 202                 continue;
 203         return ret;
 204 }
 205
 206 void
 207 arc4randbytes(void *p, size_t len)
 208 {
 209         u_int8_t *buf;
 210         size_t i;
 211
 212         /* Initialize array if needed. */
 213         if (!arc4_initialized)
 214                 arc4_init();
 215
 216         buf = (u_int8_t *)p;
 217
 218         for (i = 0; i < len; buf[i] = arc4_randbyte(), i++)
 219                 continue;
 220         arc4_numruns += len / sizeof(u_int32_t);
 221         if ((arc4_numruns > ARC4_MAXRUNS) ||
 222             (time_uptime > arc4_nextreseed)) {
 223                 arc4_randrekey();
 224         }
 225 }