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