gen/arc4random.c

   1 /*
   2  * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /* $FreeBSD: src/lib/libc/gen/arc4random.c,v 1.4 2000/01/27 23:06:13 jasone Exp $ */
  24
  25 /*
  26  * Arc4 random number generator for OpenBSD.
  27  * Copyright 1996 David Mazieres <dm@lcs.mit.edu>.
  28  *
  29  * Modification and redistribution in source and binary forms is
  30  * permitted provided that due credit is given to the author and the
  31  * OpenBSD project (for instance by leaving this copyright notice
  32  * intact).
  33  */
  34
  35 /*
  36  * This code is derived from section 17.1 of Applied Cryptography,
  37  * second edition, which describes a stream cipher allegedly
  38  * compatible with RSA Labs "RC4" cipher (the actual description of
  39  * which is a trade secret).  The same algorithm is used as a stream
  40  * cipher called "arcfour" in Tatu Ylonen's ssh package.
  41  *
  42  * Here the stream cipher has been modified always to include the time
  43  * when initializing the state.  That makes it impossible to
  44  * regenerate the same random sequence twice, so this can't be used
  45  * for encryption, but will generate good random numbers.
  46  *
  47  * RC4 is a registered trademark of RSA Laboratories.
  48  */
  49
  50 #include <stdlib.h>
  51 #include <fcntl.h>
  52 #include <unistd.h>
  53 #include <sys/types.h>
  54 #include <sys/time.h>
  55
  56 struct arc4_stream {
  57         u_int8_t i;
  58         u_int8_t j;
  59         u_int8_t s[256];
  60 };
  61
  62 static int rs_initialized;
  63 static struct arc4_stream *rs = NULL;
  64
  65 static inline void
  66 arc4_init(as)
  67         struct arc4_stream *as;
  68 {
  69         int     n;
  70
  71         for (n = 0; n < 256; n++)
  72                 as->s[n] = n;
  73         as->i = 0;
  74         as->j = 0;
  75 }
  76
  77 static inline void
  78 arc4_addrandom(as, dat, datlen)
  79         struct arc4_stream *as;
  80         u_char *dat;
  81         int     datlen;
  82 {
  83         int     n;
  84         u_int8_t si;
  85
  86         as->i--;
  87         for (n = 0; n < 256; n++) {
  88                 as->i = (as->i + 1);
  89                 si = as->s[as->i];
  90                 as->j = (as->j + si + dat[n % datlen]);
  91                 as->s[as->i] = as->s[as->j];
  92                 as->s[as->j] = si;
  93         }
  94 }
  95
  96 static void
  97 arc4_stir(as)
  98         struct arc4_stream *as;
  99 {
 100         int     fd;
 101         struct {
 102                 struct timeval tv;
 103                 pid_t pid;
 104                 u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)];
 105         }       rdat;
 106
 107         gettimeofday(&rdat.tv, NULL);
 108         rdat.pid = getpid();
 109         fd = open("/dev/urandom", O_RDONLY, 0);
 110         if (fd >= 0) {
 111                 (void) read(fd, rdat.rnd, sizeof(rdat.rnd));
 112                 close(fd);
 113         }
 114         /* fd < 0?  Ah, what the heck. We'll just take whatever was on the
 115          * stack... */
 116
 117         arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
 118 }
 119
 120 static inline u_int8_t
 121 arc4_getbyte(as)
 122         struct arc4_stream *as;
 123 {
 124         u_int8_t si, sj;
 125
 126         as->i = (as->i + 1);
 127         si = as->s[as->i];
 128         as->j = (as->j + si);
 129         sj = as->s[as->j];
 130         as->s[as->i] = sj;
 131         as->s[as->j] = si;
 132         return (as->s[(si + sj) & 0xff]);
 133 }
 134
 135 static inline u_int32_t
 136 arc4_getword(as)
 137         struct arc4_stream *as;
 138 {
 139         u_int32_t val;
 140         val = arc4_getbyte(as) << 24;
 141         val |= arc4_getbyte(as) << 16;
 142         val |= arc4_getbyte(as) << 8;
 143         val |= arc4_getbyte(as);
 144         return val;
 145 }
 146
 147 void
 148 arc4random_stir()
 149 {
 150         if ( rs == NULL ) {
 151                 rs = malloc( sizeof(struct arc4_stream) );
 152                 if( rs == NULL )
 153                         return ; /* Hmmm. */
 154         }
 155         if (!rs_initialized) {
 156                 arc4_init(rs);
 157                 rs_initialized = 1;
 158         }
 159         arc4_stir(rs);
 160 }
 161
 162 void
 163 arc4random_addrandom(dat, datlen)
 164         u_char *dat;
 165         int     datlen;
 166 {
 167         if (!rs_initialized)
 168                 arc4random_stir();
 169         arc4_addrandom(rs, dat, datlen);
 170 }
 171
 172 u_int32_t
 173 arc4random()
 174 {
 175         if (!rs_initialized)
 176                 arc4random_stir();
 177         return arc4_getword(rs);
 178 }
 179
 180 #if 0
 181 /*-------- Test code for i386 --------*/
 182 #include <stdio.h>
 183 #include <machine/pctr.h>
 184 int
 185 main(int argc, char **argv)
 186 {
 187         const int iter = 1000000;
 188         int     i;
 189         pctrval v;
 190
 191         v = rdtsc();
 192         for (i = 0; i < iter; i++)
 193                 arc4random();
 194         v = rdtsc() - v;
 195         v /= iter;
 196
 197         printf("%qd cycles\n", v);
 198 }
 199 #endif