randm.c 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249
  1. /*****************************************************************************
  2. * randm.c - Random number generator program file.
  3. *
  4. * Copyright (c) 2003 by Marc Boucher, Services Informatiques (MBSI) inc.
  5. * Copyright (c) 1998 by Global Election Systems Inc.
  6. *
  7. * The authors hereby grant permission to use, copy, modify, distribute,
  8. * and license this software and its documentation for any purpose, provided
  9. * that existing copyright notices are retained in all copies and that this
  10. * notice and the following disclaimer are included verbatim in any
  11. * distributions. No written agreement, license, or royalty fee is required
  12. * for any of the authorized uses.
  13. *
  14. * THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS *AS IS* AND ANY EXPRESS OR
  15. * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  16. * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  17. * IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  18. * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  19. * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  20. * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  21. * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  23. * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24. *
  25. ******************************************************************************
  26. * REVISION HISTORY
  27. *
  28. * 03-01-01 Marc Boucher <marc@mbsi.ca>
  29. * Ported to lwIP.
  30. * 98-06-03 Guy Lancaster <lancasterg@acm.org>, Global Election Systems Inc.
  31. * Extracted from avos.
  32. *****************************************************************************/
  33. #include "lwip/opt.h"
  34. #if PPP_SUPPORT /* don't build if not configured for use in lwipopts.h */
  35. #include "md5.h"
  36. #include "randm.h"
  37. #include "ppp.h"
  38. #include "pppdebug.h"
  39. #include <string.h>
  40. #if MD5_SUPPORT /* this module depends on MD5 */
  41. #define RANDPOOLSZ 16 /* Bytes stored in the pool of randomness. */
  42. /*****************************/
  43. /*** LOCAL DATA STRUCTURES ***/
  44. /*****************************/
  45. static char randPool[RANDPOOLSZ]; /* Pool of randomness. */
  46. static long randCount = 0; /* Pseudo-random incrementer */
  47. /***********************************/
  48. /*** PUBLIC FUNCTION DEFINITIONS ***/
  49. /***********************************/
  50. /*
  51. * Initialize the random number generator.
  52. *
  53. * Since this is to be called on power up, we don't have much
  54. * system randomess to work with. Here all we use is the
  55. * real-time clock. We'll accumulate more randomness as soon
  56. * as things start happening.
  57. */
  58. void
  59. avRandomInit()
  60. {
  61. avChurnRand(NULL, 0);
  62. }
  63. /*
  64. * Churn the randomness pool on a random event. Call this early and often
  65. * on random and semi-random system events to build randomness in time for
  66. * usage. For randomly timed events, pass a null pointer and a zero length
  67. * and this will use the system timer and other sources to add randomness.
  68. * If new random data is available, pass a pointer to that and it will be
  69. * included.
  70. *
  71. * Ref: Applied Cryptography 2nd Ed. by Bruce Schneier p. 427
  72. */
  73. void
  74. avChurnRand(char *randData, u32_t randLen)
  75. {
  76. MD5_CTX md5;
  77. /* ppp_trace(LOG_INFO, "churnRand: %u@%P\n", randLen, randData); */
  78. MD5Init(&md5);
  79. MD5Update(&md5, (u_char *)randPool, sizeof(randPool));
  80. if (randData) {
  81. MD5Update(&md5, (u_char *)randData, randLen);
  82. } else {
  83. struct {
  84. /* INCLUDE fields for any system sources of randomness */
  85. char foobar;
  86. } sysData;
  87. /* Load sysData fields here. */
  88. MD5Update(&md5, (u_char *)&sysData, sizeof(sysData));
  89. }
  90. MD5Final((u_char *)randPool, &md5);
  91. /* ppp_trace(LOG_INFO, "churnRand: -> 0\n"); */
  92. }
  93. /*
  94. * Use the random pool to generate random data. This degrades to pseudo
  95. * random when used faster than randomness is supplied using churnRand().
  96. * Note: It's important that there be sufficient randomness in randPool
  97. * before this is called for otherwise the range of the result may be
  98. * narrow enough to make a search feasible.
  99. *
  100. * Ref: Applied Cryptography 2nd Ed. by Bruce Schneier p. 427
  101. *
  102. * XXX Why does he not just call churnRand() for each block? Probably
  103. * so that you don't ever publish the seed which could possibly help
  104. * predict future values.
  105. * XXX Why don't we preserve md5 between blocks and just update it with
  106. * randCount each time? Probably there is a weakness but I wish that
  107. * it was documented.
  108. */
  109. void
  110. avGenRand(char *buf, u32_t bufLen)
  111. {
  112. MD5_CTX md5;
  113. u_char tmp[16];
  114. u32_t n;
  115. while (bufLen > 0) {
  116. n = LWIP_MIN(bufLen, RANDPOOLSZ);
  117. MD5Init(&md5);
  118. MD5Update(&md5, (u_char *)randPool, sizeof(randPool));
  119. MD5Update(&md5, (u_char *)&randCount, sizeof(randCount));
  120. MD5Final(tmp, &md5);
  121. randCount++;
  122. MEMCPY(buf, tmp, n);
  123. buf += n;
  124. bufLen -= n;
  125. }
  126. }
  127. /*
  128. * Return a new random number.
  129. */
  130. u32_t
  131. avRandom()
  132. {
  133. u32_t newRand;
  134. avGenRand((char *)&newRand, sizeof(newRand));
  135. return newRand;
  136. }
  137. #else /* MD5_SUPPORT */
  138. /*****************************/
  139. /*** LOCAL DATA STRUCTURES ***/
  140. /*****************************/
  141. static int avRandomized = 0; /* Set when truely randomized. */
  142. static u32_t avRandomSeed = 0; /* Seed used for random number generation. */
  143. /***********************************/
  144. /*** PUBLIC FUNCTION DEFINITIONS ***/
  145. /***********************************/
  146. /*
  147. * Initialize the random number generator.
  148. *
  149. * Here we attempt to compute a random number seed but even if
  150. * it isn't random, we'll randomize it later.
  151. *
  152. * The current method uses the fields from the real time clock,
  153. * the idle process counter, the millisecond counter, and the
  154. * hardware timer tick counter. When this is invoked
  155. * in startup(), then the idle counter and timer values may
  156. * repeat after each boot and the real time clock may not be
  157. * operational. Thus we call it again on the first random
  158. * event.
  159. */
  160. void
  161. avRandomInit()
  162. {
  163. #if 0
  164. /* Get a pointer into the last 4 bytes of clockBuf. */
  165. u32_t *lptr1 = (u32_t *)((char *)&clockBuf[3]);
  166. /*
  167. * Initialize our seed using the real-time clock, the idle
  168. * counter, the millisecond timer, and the hardware timer
  169. * tick counter. The real-time clock and the hardware
  170. * tick counter are the best sources of randomness but
  171. * since the tick counter is only 16 bit (and truncated
  172. * at that), the idle counter and millisecond timer
  173. * (which may be small values) are added to help
  174. * randomize the lower 16 bits of the seed.
  175. */
  176. readClk();
  177. avRandomSeed += *(u32_t *)clockBuf + *lptr1 + OSIdleCtr
  178. + ppp_mtime() + ((u32_t)TM1 << 16) + TM1;
  179. #else
  180. avRandomSeed += sys_jiffies(); /* XXX */
  181. #endif
  182. /* Initialize the Borland random number generator. */
  183. srand((unsigned)avRandomSeed);
  184. }
  185. /*
  186. * Randomize our random seed value. Here we use the fact that
  187. * this function is called at *truely random* times by the polling
  188. * and network functions. Here we only get 16 bits of new random
  189. * value but we use the previous value to randomize the other 16
  190. * bits.
  191. */
  192. void
  193. avRandomize(void)
  194. {
  195. static u32_t last_jiffies;
  196. if (!avRandomized) {
  197. avRandomized = !0;
  198. avRandomInit();
  199. /* The initialization function also updates the seed. */
  200. } else {
  201. /* avRandomSeed += (avRandomSeed << 16) + TM1; */
  202. avRandomSeed += (sys_jiffies() - last_jiffies); /* XXX */
  203. }
  204. last_jiffies = sys_jiffies();
  205. }
  206. /*
  207. * Return a new random number.
  208. * Here we use the Borland rand() function to supply a pseudo random
  209. * number which we make truely random by combining it with our own
  210. * seed which is randomized by truely random events.
  211. * Thus the numbers will be truely random unless there have been no
  212. * operator or network events in which case it will be pseudo random
  213. * seeded by the real time clock.
  214. */
  215. u32_t
  216. avRandom()
  217. {
  218. return ((((u32_t)rand() << 16) + rand()) + avRandomSeed);
  219. }
  220. #endif /* MD5_SUPPORT */
  221. #endif /* PPP_SUPPORT */