arc4random.c 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215
  1. /*
  2. * Copyright (c) 1996, David Mazieres <dm@uun.org>
  3. *
  4. * Permission to use, copy, modify, and distribute this software for any
  5. * purpose with or without fee is hereby granted, provided that the above
  6. * copyright notice and this permission notice appear in all copies.
  7. *
  8. * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  9. * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10. * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11. * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12. * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13. * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14. * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15. */
  16. /*
  17. * Arc4 random number generator for OpenBSD.
  18. *
  19. * This code is derived from section 17.1 of Applied Cryptography,
  20. * second edition, which describes a stream cipher allegedly
  21. * compatible with RSA Labs "RC4" cipher (the actual description of
  22. * which is a trade secret). The same algorithm is used as a stream
  23. * cipher called "arcfour" in Tatu Ylonen's ssh package.
  24. *
  25. * Here the stream cipher has been modified always to include entropy
  26. * when initializing the state. That makes it impossible to
  27. * regenerate the same random sequence twice, so this can't be used
  28. * for encryption, but will generate good random numbers.
  29. *
  30. * RC4 is a registered trademark of RSA Laboratories.
  31. */
  32. /* $OpenBSD: arc4random.c,v 1.16 2007/02/12 19:58:47 otto Exp $ */
  33. #include <features.h>
  34. #include <fcntl.h>
  35. #include <stdlib.h>
  36. #include <unistd.h>
  37. #include <sys/types.h>
  38. #include <sys/time.h>
  39. struct arc4_stream {
  40. u_int8_t i;
  41. u_int8_t j;
  42. u_int8_t s[256];
  43. };
  44. static smallint rs_initialized;
  45. static struct arc4_stream rs;
  46. static pid_t arc4_stir_pid;
  47. static int arc4_count;
  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__ u_int8_t
  58. arc4_getbyte(struct arc4_stream *as)
  59. {
  60. u_int8_t si, sj;
  61. as->i = (as->i + 1);
  62. si = as->s[as->i];
  63. as->j = (as->j + si);
  64. sj = as->s[as->j];
  65. as->s[as->i] = sj;
  66. as->s[as->j] = si;
  67. return (as->s[(si + sj) & 0xff]);
  68. }
  69. static __inline__ void
  70. arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen)
  71. {
  72. int n;
  73. u_int8_t si;
  74. as->i--;
  75. for (n = 0; n < 256; n++) {
  76. as->i = (as->i + 1);
  77. si = as->s[as->i];
  78. as->j = (as->j + si + dat[n % datlen]);
  79. as->s[as->i] = as->s[as->j];
  80. as->s[as->j] = si;
  81. }
  82. as->j = as->i;
  83. }
  84. static void
  85. arc4_stir(struct arc4_stream *as)
  86. {
  87. int n;
  88. u_char rnd[128];
  89. struct timeval tv;
  90. #ifndef __ARC4RANDOM_USES_NODEV__
  91. int fd;
  92. fd = open("/dev/urandom", O_RDONLY);
  93. if (fd != -1) {
  94. read(fd, rnd, sizeof(rnd));
  95. close(fd);
  96. }
  97. /* Did the pseudo-random device fail? Use gettimeofday(). */
  98. else
  99. #endif
  100. if (gettimeofday(&tv, NULL) != (-1)) {
  101. /* Initialize the first element so it's hopefully not '0',
  102. * to help out the next loop. Tossing in some prime numbers
  103. * probably can't hurt. */
  104. rnd[0] = (tv.tv_sec % 10000) * 3 + tv.tv_usec * 7 + \
  105. (getpid() % 1000) * 13;
  106. for (n = 1; n < 127 ; n++) {
  107. /* Take advantage of the stack space. Only initialize
  108. * elements equal to '0'. This will make the rnd[]
  109. * array much less vulnerable to timing attacks. Here
  110. * we'll stir getpid() into the value of the previous
  111. * element. Approximately 1 in 128 elements will still
  112. * become '0'. */
  113. if (rnd[n] == 0) {
  114. rnd[n] = ((rnd[n - 1] + n) ^ \
  115. ((getpid() % 1000) * 17));
  116. }
  117. }
  118. }
  119. else {
  120. /* gettimeofday() failed? Do the same thing as above, but only
  121. * with getpid(). */
  122. rnd[0] = (getpid() % 1000) * 19;
  123. for (n = 1; n < 127 ; n++) {
  124. if (rnd[n] == 0) {
  125. rnd[n] = ((rnd[n - 1] + n) ^ \
  126. ((getpid() % 1000) * 23));
  127. }
  128. }
  129. }
  130. arc4_stir_pid = getpid();
  131. arc4_addrandom(as, rnd, sizeof(rnd));
  132. /*
  133. * Discard early keystream, as per recommendations in:
  134. * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
  135. */
  136. for (n = 0; n < 256; n++)
  137. (void)arc4_getbyte(as);
  138. arc4_count = 1600000;
  139. }
  140. #if 0
  141. static void __arc4random_stir(void);
  142. /*
  143. * __arc4_getbyte() is a libc private function intended for use
  144. * with malloc.
  145. */
  146. u_int8_t
  147. __arc4_getbyte(void)
  148. {
  149. if (--arc4_count == 0 || !rs_initialized)
  150. __arc4random_stir();
  151. return arc4_getbyte(&rs);
  152. }
  153. #endif
  154. static __inline__ u_int32_t
  155. arc4_getword(struct arc4_stream *as)
  156. {
  157. u_int32_t val;
  158. val = arc4_getbyte(as) << 24;
  159. val |= arc4_getbyte(as) << 16;
  160. val |= arc4_getbyte(as) << 8;
  161. val |= arc4_getbyte(as);
  162. return val;
  163. }
  164. static void
  165. __arc4random_stir(void)
  166. {
  167. if (!rs_initialized) {
  168. arc4_init(&rs);
  169. rs_initialized = 1;
  170. }
  171. arc4_stir(&rs);
  172. }
  173. strong_alias(__arc4random_stir,arc4random_stir)
  174. void
  175. arc4random_addrandom(u_char *dat, int datlen)
  176. {
  177. if (!rs_initialized)
  178. __arc4random_stir();
  179. arc4_addrandom(&rs, dat, datlen);
  180. }
  181. u_int32_t
  182. arc4random(void)
  183. {
  184. arc4_count -= 4;
  185. if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != getpid())
  186. __arc4random_stir();
  187. return arc4_getword(&rs);
  188. }