arc4random.c 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197
  1. /* $$$: arc4random.c 2005/02/08 robert */
  2. /* $NetBSD: arc4random.c,v 1.5.2.1 2004/03/26 22:52:50 jmc Exp $ */
  3. /* $OpenBSD: arc4random.c,v 1.6 2001/06/05 05:05:38 pvalchev Exp $ */
  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 by leaving this copyright notice intact.
  11. */
  12. /*
  13. * This code is derived from section 17.1 of Applied Cryptography,
  14. * second edition, which describes a stream cipher allegedly
  15. * compatible with RSA Labs "RC4" cipher (the actual description of
  16. * which is a trade secret). The same algorithm is used as a stream
  17. * cipher called "arcfour" in Tatu Ylonen's ssh package.
  18. *
  19. * Here the stream cipher has been modified always to include the time
  20. * when initializing the state. That makes it impossible to
  21. * regenerate the same random sequence twice, so this can't be used
  22. * for encryption, but will generate good random numbers.
  23. *
  24. * RC4 is a registered trademark of RSA Laboratories.
  25. */
  26. #include <features.h>
  27. #include <fcntl.h>
  28. #include <stdlib.h>
  29. #include <unistd.h>
  30. #include <sys/types.h>
  31. #include <sys/param.h>
  32. #include <sys/time.h>
  33. #ifdef __ARC4RANDOM_USE_ERANDOM__
  34. #include <sys/sysctl.h>
  35. #endif
  36. struct arc4_stream {
  37. uint8_t i;
  38. uint8_t j;
  39. uint8_t s[256];
  40. };
  41. static int rs_initialized;
  42. static struct arc4_stream rs;
  43. static __inline__ void arc4_init(struct arc4_stream *);
  44. static __inline__ void arc4_addrandom(struct arc4_stream *, u_char *, int);
  45. static void arc4_stir(struct arc4_stream *);
  46. static __inline__ uint8_t arc4_getbyte(struct arc4_stream *);
  47. static __inline__ uint32_t arc4_getword(struct arc4_stream *);
  48. static __inline__ void
  49. arc4_init(struct arc4_stream *as)
  50. {
  51. int n;
  52. for (n = 0; n < 256; n++)
  53. as->s[n] = n;
  54. as->i = 0;
  55. as->j = 0;
  56. }
  57. static __inline__ void
  58. arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen)
  59. {
  60. int n;
  61. uint8_t si;
  62. as->i--;
  63. for (n = 0; n < 256; n++) {
  64. as->i = (as->i + 1);
  65. si = as->s[as->i];
  66. as->j = (as->j + si + dat[n % datlen]);
  67. as->s[as->i] = as->s[as->j];
  68. as->s[as->j] = si;
  69. }
  70. as->j = as->i;
  71. }
  72. static void
  73. arc4_stir(struct arc4_stream *as)
  74. {
  75. int fd;
  76. struct {
  77. struct timeval tv;
  78. uint rnd[(128 - sizeof(struct timeval)) / sizeof(uint)];
  79. } rdat;
  80. int n;
  81. gettimeofday(&rdat.tv, NULL);
  82. fd = open("/dev/urandom", O_RDONLY);
  83. if (fd != -1) {
  84. read(fd, rdat.rnd, sizeof(rdat.rnd));
  85. close(fd);
  86. }
  87. #ifdef __ARC4RANDOM_USE_ERANDOM__
  88. else {
  89. int mib[3];
  90. uint i;
  91. size_t len;
  92. /* Device could not be opened, we might be chrooted, take
  93. * randomness from sysctl. */
  94. mib[0] = CTL_KERN;
  95. mib[1] = KERN_RANDOM;
  96. mib[2] = RANDOM_ERANDOM;
  97. for (i = 0; i < sizeof(rdat.rnd) / sizeof(uint); i++) {
  98. len = sizeof(uint);
  99. if (sysctl(mib, 3, &rdat.rnd[i], &len, NULL, 0) == -1)
  100. break;
  101. }
  102. }
  103. #endif
  104. arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
  105. /*
  106. * Throw away the first N words of output, as suggested in the
  107. * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
  108. * by Fluher, Mantin, and Shamir.
  109. * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
  110. * N = 256 in our case.
  111. */
  112. for (n = 0; n < 256 * 4; n++)
  113. arc4_getbyte(as);
  114. }
  115. static __inline__ uint8_t
  116. arc4_getbyte(struct arc4_stream *as)
  117. {
  118. uint8_t si, sj;
  119. as->i = (as->i + 1);
  120. si = as->s[as->i];
  121. as->j = (as->j + si);
  122. sj = as->s[as->j];
  123. as->s[as->i] = sj;
  124. as->s[as->j] = si;
  125. return (as->s[(si + sj) & 0xff]);
  126. }
  127. static __inline__ uint32_t
  128. arc4_getword(struct arc4_stream *as)
  129. {
  130. uint32_t val;
  131. val = arc4_getbyte(as) << 24;
  132. val |= arc4_getbyte(as) << 16;
  133. val |= arc4_getbyte(as) << 8;
  134. val |= arc4_getbyte(as);
  135. return val;
  136. }
  137. static void
  138. __arc4random_stir(void)
  139. {
  140. if (!rs_initialized) {
  141. arc4_init(&rs);
  142. rs_initialized = 1;
  143. }
  144. arc4_stir(&rs);
  145. }
  146. strong_alias(__arc4random_stir,arc4random_stir)
  147. void
  148. arc4random_addrandom(u_char *dat, int datlen)
  149. {
  150. if (!rs_initialized)
  151. __arc4random_stir();
  152. arc4_addrandom(&rs, dat, datlen);
  153. }
  154. uint32_t
  155. arc4random(void)
  156. {
  157. if (!rs_initialized)
  158. __arc4random_stir();
  159. return arc4_getword(&rs);
  160. }
  161. #if 0
  162. /*-------- Test code --------*/
  163. #include <stdlib.h>
  164. #include <stdio.h>
  165. int main(void) {
  166. int random_number;
  167. random_number = arc4random() % 65536;
  168. printf("%d\n", random_number);
  169. return 0;
  170. }
  171. #endif