lib/libc/gen/arc4random.c

   1 /* $FreeBSD: src/lib/libc/gen/arc4random.c,v 1.4 2000/01/27 23:06:13 jasone Exp $ */
   2 /* $DragonFly: src/lib/libc/gen/arc4random.c,v 1.7 2005/11/13 01:07:42 swildner Exp $ */
   3
   4 /*
   5  * Arc4 random number generator for OpenBSD.
   6  * Copyright 1996 David Mazieres <dm@lcs.mit.edu>.
   7  *
   8  * Modification and redistribution in source and binary forms is
   9  * permitted provided that due credit is given to the author and the
  10  * OpenBSD project (for instance by leaving this copyright notice
  11  * intact).
  12  */
  13
  14 /*
  15  * This code is derived from section 17.1 of Applied Cryptography,
  16  * second edition, which describes a stream cipher allegedly
  17  * compatible with RSA Labs "RC4" cipher (the actual description of
  18  * which is a trade secret).  The same algorithm is used as a stream
  19  * cipher called "arcfour" in Tatu Ylonen's ssh package.
  20  *
  21  * Here the stream cipher has been modified always to include the time
  22  * when initializing the state.  That makes it impossible to
  23  * regenerate the same random sequence twice, so this can't be used
  24  * for encryption, but will generate good random numbers.
  25  *
  26  * RC4 is a registered trademark of RSA Laboratories.
  27  */
  28
  29 #include "namespace.h"
  30 #include <stdlib.h>
  31 #include <fcntl.h>
  32 #include <unistd.h>
  33 #include <sys/types.h>
  34 #include <sys/time.h>
  35 #include "un-namespace.h"
  36
  37 struct arc4_stream {
  38         u_int8_t i;
  39         u_int8_t j;
  40         u_int8_t s[256];
  41 };
  42
  43 static int rs_initialized;
  44 static struct arc4_stream rs;
  45
  46 static u_int8_t arc4_getbyte(struct arc4_stream *);
  47
  48 static void
  49 arc4_init(struct arc4_stream *as)
  50 {
  51         int     n;
  52
  53         for (n = 0; n < 256; n++)
  54                 as->s[n] = n;
  55         as->i = 0;
  56         as->j = 0;
  57 }
  58
  59 static void
  60 arc4_addrandom(struct arc4_stream *as, u_char *dat, size_t datlen)
  61 {
  62         size_t n;
  63         u_int8_t si;
  64
  65         as->i--;
  66         for (n = 0; n < 256; n++) {
  67                 as->i = (as->i + 1);
  68                 si = as->s[as->i];
  69                 as->j = (as->j + si + dat[n % datlen]);
  70                 as->s[as->i] = as->s[as->j];
  71                 as->s[as->j] = si;
  72         }
  73 }
  74
  75 static void
  76 arc4_stir(struct arc4_stream *as)
  77 {
  78         int     fd, n;
  79         struct {
  80                 struct timeval tv;
  81                 pid_t pid;
  82                 u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)];
  83         }       rdat;
  84
  85         gettimeofday(&rdat.tv, NULL);
  86         rdat.pid = getpid();
  87         fd = _open("/dev/urandom", O_RDONLY, 0);
  88         if (fd >= 0) {
  89                 _read(fd, rdat.rnd, sizeof(rdat.rnd));
  90                 _close(fd);
  91         }
  92         /* fd < 0?  Ah, what the heck. We'll just take whatever was on the
  93          * stack... */
  94
  95         arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
  96
  97         /*
  98          * Throw away the first N bytes of output, as suggested in the
  99          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 100          * by Fluher, Mantin, and Shamir.  N=1024 is based on
 101          * suggestions in the paper "(Not So) Random Shuffles of RC4"
 102          * by Ilya Mironov.
 103          */
 104         for (n = 0; n < 1024; n++)
 105                 arc4_getbyte(as);
 106 }
 107
 108 static u_int8_t
 109 arc4_getbyte(struct arc4_stream *as)
 110 {
 111         u_int8_t si, sj;
 112
 113         as->i = (as->i + 1);
 114         si = as->s[as->i];
 115         as->j = (as->j + si);
 116         sj = as->s[as->j];
 117         as->s[as->i] = sj;
 118         as->s[as->j] = si;
 119         return (as->s[(si + sj) & 0xff]);
 120 }
 121
 122 static u_int32_t
 123 arc4_getword(struct arc4_stream *as)
 124 {
 125         u_int32_t val;
 126         val = arc4_getbyte(as) << 24;
 127         val |= arc4_getbyte(as) << 16;
 128         val |= arc4_getbyte(as) << 8;
 129         val |= arc4_getbyte(as);
 130         return val;
 131 }
 132
 133 void
 134 arc4random_stir(void)
 135 {
 136         if (!rs_initialized) {
 137                 arc4_init(&rs);
 138                 rs_initialized = 1;
 139         }
 140         arc4_stir(&rs);
 141 }
 142
 143 void
 144 arc4random_addrandom(uint8_t *dat, size_t datlen)
 145 {
 146         if (!rs_initialized)
 147                 arc4random_stir();
 148         arc4_addrandom(&rs, dat, datlen);
 149 }
 150
 151 u_int32_t
 152 arc4random(void)
 153 {
 154         if (!rs_initialized)
 155                 arc4random_stir();
 156         return arc4_getword(&rs);
 157 }
 158
 159 #if 0
 160 /*-------- Test code for i386 --------*/
 161 #include <stdio.h>
 162 #include <machine/pctr.h>
 163 int
 164 main(int argc, char **argv)
 165 {
 166         const int iter = 1000000;
 167         int     i;
 168         pctrval v;
 169
 170         v = rdtsc();
 171         for (i = 0; i < iter; i++)
 172                 arc4random();
 173         v = rdtsc() - v;
 174         v /= iter;
 175
 176         printf("%qd cycles\n", v);
 177 }
 178 #endif