1/* 2 * Arc4 random number generator for OpenBSD. 3 * Copyright 1996 David Mazieres <dm@lcs.mit.edu>. 4 * 5 * Modification and redistribution in source and binary forms is 6 * permitted provided that due credit is given to the author and the 7 * OpenBSD project by leaving this copyright notice intact. 8 */ 9 10/* 11 * This code is derived from section 17.1 of Applied Cryptography, 12 * second edition, which describes a stream cipher allegedly 13 * compatible with RSA Labs "RC4" cipher (the actual description of 14 * which is a trade secret). The same algorithm is used as a stream 15 * cipher called "arcfour" in Tatu Ylonen's ssh package. 16 * 17 * Here the stream cipher has been modified always to include the time 18 * when initializing the state. That makes it impossible to 19 * regenerate the same random sequence twice, so this can't be used 20 * for encryption, but will generate good random numbers. 21 * 22 * RC4 is a registered trademark of RSA Laboratories. 23 */ 24 25#include <sys/time.h> 26 27#include <fcntl.h> 28#include <stdint.h> 29#include <stdlib.h> 30#include <unistd.h> 31 32#include "arc4random.h" 33 34struct arc4_stream { 35 uint8_t i; 36 uint8_t j; 37 uint8_t s[256]; 38 size_t count; 39 pid_t stir_pid; 40}; 41 42#define S(n) (n) 43#define S4(n) S(n), S(n + 1), S(n + 2), S(n + 3) 44#define S16(n) S4(n), S4(n + 4), S4(n + 8), S4(n + 12) 45#define S64(n) S16(n), S16(n + 16), S16(n + 32), S16(n + 48) 46#define S256 S64(0), S64(64), S64(128), S64(192) 47 48static struct arc4_stream rs = { .i = 0xff, .j = 0, .s = { S256 }, 49 .count = 0, .stir_pid = 0 }; 50 51#undef S 52#undef S4 53#undef S16 54#undef S64 55#undef S256 56 57static void 58arc4_addrandom(struct arc4_stream *as, unsigned char *dat, int datlen) 59{ 60 int n; 61 uint8_t si; 62 63 as->i--; 64 for (n = 0; n < 256; n++) { 65 as->i = (uint8_t)(as->i + 1); 66 si = as->s[as->i]; 67 as->j = (uint8_t)(as->j + si + dat[n % datlen]); 68 as->s[as->i] = as->s[as->j]; 69 as->s[as->j] = si; 70 } 71 as->j = as->i; 72} 73 74static uint8_t 75arc4_getbyte(struct arc4_stream *as) 76{ 77 uint8_t si, sj; 78 79 as->i = (uint8_t)(as->i + 1); 80 si = as->s[as->i]; 81 as->j = (uint8_t)(as->j + si); 82 sj = as->s[as->j]; 83 as->s[as->i] = sj; 84 as->s[as->j] = si; 85 return (as->s[(si + sj) & 0xff]); 86} 87 88static uint32_t 89arc4_getword(struct arc4_stream *as) 90{ 91 int val; 92 93 val = arc4_getbyte(as) << 24; 94 val |= arc4_getbyte(as) << 16; 95 val |= arc4_getbyte(as) << 8; 96 val |= arc4_getbyte(as); 97 return (uint32_t)val; 98} 99 100static void 101arc4_stir(struct arc4_stream *as) 102{ 103 int fd; 104 struct { 105 struct timeval tv; 106 unsigned int rnd[(128 - sizeof(struct timeval)) / 107 sizeof(unsigned int)]; 108 } rdat; 109 size_t n; 110 111 gettimeofday(&rdat.tv, NULL); 112 fd = open("/dev/urandom", O_RDONLY); 113 if (fd != -1) { 114 (void)read(fd, rdat.rnd, sizeof(rdat.rnd)); 115 close(fd); 116 } 117 118 /* fd < 0? Ah, what the heck. We'll just take 119 * whatever was on the stack... */ 120 arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); 121 122 /* 123 * Throw away the first N words of output, as suggested in the 124 * paper "Weaknesses in the Key Scheduling Algorithm of RC4" 125 * by Fluher, Mantin, and Shamir. (N = 256 in our case.) 126 */ 127 for (n = 0; n < 256 * sizeof(uint32_t); n++) 128 arc4_getbyte(as); 129 as->count = 1600000; 130} 131 132static void 133arc4_stir_if_needed(struct arc4_stream *as) 134{ 135 pid_t pid; 136 137 pid = getpid(); 138 if (as->count <= sizeof(uint32_t) || !as->stir_pid != pid) { 139 as->stir_pid = pid; 140 arc4_stir(as); 141 } else 142 as->count -= sizeof(uint32_t); 143} 144 145uint32_t 146arc4random() 147{ 148 149 arc4_stir_if_needed(&rs); 150 return arc4_getword(&rs); 151} 152