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 arc4_init(struct arc4_stream *) __attribute__((always_inline));
  66 static inline void
  67 arc4_init(as)
  68         struct arc4_stream *as;
  69 {
  70         int     n;
  71
  72         for (n = 0; n < 256; n++)
  73                 as->s[n] = n;
  74         as->i = 0;
  75         as->j = 0;
  76 }
  77
  78 static inline void arc4_addrandom(struct arc4_stream *, u_char *, int) __attribute__((always_inline));
  79 static inline void
  80 arc4_addrandom(as, dat, datlen)
  81         struct arc4_stream *as;
  82         u_char *dat;
  83         int     datlen;
  84 {
  85         int     n;
  86         u_int8_t si;
  87
  88         as->i--;
  89         for (n = 0; n < 256; n++) {
  90                 as->i = (as->i + 1);
  91                 si = as->s[as->i];
  92                 as->j = (as->j + si + dat[n % datlen]);
  93                 as->s[as->i] = as->s[as->j];
  94                 as->s[as->j] = si;
  95         }
  96 }
  97
  98 static void
  99 arc4_stir(as)
 100         struct arc4_stream *as;
 101 {
 102         int     fd;
 103         struct {
 104                 struct timeval tv;
 105                 pid_t pid;
 106                 u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)];
 107         }       rdat;
 108
 109         gettimeofday(&rdat.tv, NULL);
 110         rdat.pid = getpid();
 111         fd = open("/dev/urandom", O_RDONLY, 0);
 112         if (fd >= 0) {
 113                 (void) read(fd, rdat.rnd, sizeof(rdat.rnd));
 114                 close(fd);
 115         }
 116         /* fd < 0?  Ah, what the heck. We'll just take whatever was on the
 117          * stack... */
 118
 119         arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
 120 }
 121
 122 static inline u_int8_t arc4_getbyte(struct arc4_stream *) __attribute__((always_inline));
 123 static inline u_int8_t
 124 arc4_getbyte(as)
 125         struct arc4_stream *as;
 126 {
 127         u_int8_t si, sj;
 128
 129         as->i = (as->i + 1);
 130         si = as->s[as->i];
 131         as->j = (as->j + si);
 132         sj = as->s[as->j];
 133         as->s[as->i] = sj;
 134         as->s[as->j] = si;
 135         return (as->s[(si + sj) & 0xff]);
 136 }
 137
 138 static inline u_int32_t arc4_getword(struct arc4_stream *) __attribute__((always_inline));
 139 static inline u_int32_t
 140 arc4_getword(as)
 141         struct arc4_stream *as;
 142 {
 143         u_int32_t val;
 144         val = arc4_getbyte(as) << 24;
 145         val |= arc4_getbyte(as) << 16;
 146         val |= arc4_getbyte(as) << 8;
 147         val |= arc4_getbyte(as);
 148         return val;
 149 }
 150
 151 void
 152 arc4random_stir()
 153 {
 154         if ( rs == NULL ) {
 155                 rs = malloc( sizeof(struct arc4_stream) );
 156                 if( rs == NULL )
 157                         return ; /* Hmmm. */
 158         }
 159         if (!rs_initialized) {
 160                 arc4_init(rs);
 161                 rs_initialized = 1;
 162         }
 163         arc4_stir(rs);
 164 }
 165
 166 void
 167 arc4random_addrandom(dat, datlen)
 168         u_char *dat;
 169         int     datlen;
 170 {
 171         if (!rs_initialized)
 172                 arc4random_stir();
 173         arc4_addrandom(rs, dat, datlen);
 174 }
 175
 176 u_int32_t
 177 arc4random()
 178 {
 179         if (!rs_initialized)
 180                 arc4random_stir();
 181         return arc4_getword(rs);
 182 }
 183
 184 #if 0
 185 /*-------- Test code for i386 --------*/
 186 #include <stdio.h>
 187 #include <machine/pctr.h>
 188 int
 189 main(int argc, char **argv)
 190 {
 191         const int iter = 1000000;
 192         int     i;
 193         pctrval v;
 194
 195         v = rdtsc();
 196         for (i = 0; i < iter; i++)
 197                 arc4random();
 198         v = rdtsc() - v;
 199         v /= iter;
 200
 201         printf("%qd cycles\n", v);
 202 }
 203 #endif