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 
34 #include "lwip/opt.h"
35 
36 #if PPP_SUPPORT /* don't build if not configured for use in lwipopts.h */
37 
38 #include "md5.h"
39 #include "randm.h"
40 
41 #include "ppp_impl.h"
42 #include "pppdebug.h"
43 
44 #include <string.h>
45 
46 #if MD5_SUPPORT /* this module depends on MD5 */
47 #define RANDPOOLSZ 16   /* Bytes stored in the pool of randomness. */
48 
49 /*****************************/
50 /*** LOCAL DATA STRUCTURES ***/
51 /*****************************/
52 static char randPool[RANDPOOLSZ];   /* Pool of randomness. */
53 static long randCount = 0;      /* Pseudo-random incrementer */
54 
55 
56 /***********************************/
57 /*** PUBLIC FUNCTION DEFINITIONS ***/
58 /***********************************/
59 /*
60  * Initialize the random number generator.
61  *
62  * Since this is to be called on power up, we don't have much
63  *  system randomess to work with.  Here all we use is the
64  *  real-time clock.  We'll accumulate more randomness as soon
65  *  as things start happening.
66  */
67 void
avRandomInit()68 avRandomInit()
69 {
70   avChurnRand(NULL, 0);
71 }
72 
73 /*
74  * Churn the randomness pool on a random event.  Call this early and often
75  *  on random and semi-random system events to build randomness in time for
76  *  usage.  For randomly timed events, pass a null pointer and a zero length
77  *  and this will use the system timer and other sources to add randomness.
78  *  If new random data is available, pass a pointer to that and it will be
79  *  included.
80  *
81  * Ref: Applied Cryptography 2nd Ed. by Bruce Schneier p. 427
82  */
83 void
avChurnRand(char * randData,u32_t randLen)84 avChurnRand(char *randData, u32_t randLen)
85 {
86   MD5_CTX md5;
87 
88   /* LWIP_DEBUGF(LOG_INFO, ("churnRand: %u@%P\n", randLen, randData)); */
89   MD5Init(&md5);
90   MD5Update(&md5, (u_char *)randPool, sizeof(randPool));
91   if (randData) {
92     MD5Update(&md5, (u_char *)randData, randLen);
93   } else {
94     struct {
95       /* INCLUDE fields for any system sources of randomness */
96       char foobar;
97     } sysData;
98 
99     /* Load sysData fields here. */
100     MD5Update(&md5, (u_char *)&sysData, sizeof(sysData));
101   }
102   MD5Final((u_char *)randPool, &md5);
103 /*  LWIP_DEBUGF(LOG_INFO, ("churnRand: -> 0\n")); */
104 }
105 
106 /*
107  * Use the random pool to generate random data.  This degrades to pseudo
108  *  random when used faster than randomness is supplied using churnRand().
109  * Note: It's important that there be sufficient randomness in randPool
110  *  before this is called for otherwise the range of the result may be
111  *  narrow enough to make a search feasible.
112  *
113  * Ref: Applied Cryptography 2nd Ed. by Bruce Schneier p. 427
114  *
115  * XXX Why does he not just call churnRand() for each block?  Probably
116  *  so that you don't ever publish the seed which could possibly help
117  *  predict future values.
118  * XXX Why don't we preserve md5 between blocks and just update it with
119  *  randCount each time?  Probably there is a weakness but I wish that
120  *  it was documented.
121  */
122 void
avGenRand(char * buf,u32_t bufLen)123 avGenRand(char *buf, u32_t bufLen)
124 {
125   MD5_CTX md5;
126   u_char tmp[16];
127   u32_t n;
128 
129   while (bufLen > 0) {
130     n = LWIP_MIN(bufLen, RANDPOOLSZ);
131     MD5Init(&md5);
132     MD5Update(&md5, (u_char *)randPool, sizeof(randPool));
133     MD5Update(&md5, (u_char *)&randCount, sizeof(randCount));
134     MD5Final(tmp, &md5);
135     randCount++;
136     MEMCPY(buf, tmp, n);
137     buf += n;
138     bufLen -= n;
139   }
140 }
141 
142 /*
143  * Return a new random number.
144  */
145 u32_t
avRandom()146 avRandom()
147 {
148   u32_t newRand;
149 
150   avGenRand((char *)&newRand, sizeof(newRand));
151 
152   return newRand;
153 }
154 
155 #else /* MD5_SUPPORT */
156 
157 /*****************************/
158 /*** LOCAL DATA STRUCTURES ***/
159 /*****************************/
160 static int  avRandomized = 0;       /* Set when truely randomized. */
161 static u32_t avRandomSeed = 0;      /* Seed used for random number generation. */
162 
163 
164 /***********************************/
165 /*** PUBLIC FUNCTION DEFINITIONS ***/
166 /***********************************/
167 /*
168  * Initialize the random number generator.
169  *
170  * Here we attempt to compute a random number seed but even if
171  * it isn't random, we'll randomize it later.
172  *
173  * The current method uses the fields from the real time clock,
174  * the idle process counter, the millisecond counter, and the
175  * hardware timer tick counter.  When this is invoked
176  * in startup(), then the idle counter and timer values may
177  * repeat after each boot and the real time clock may not be
178  * operational.  Thus we call it again on the first random
179  * event.
180  */
181 void
avRandomInit()182 avRandomInit()
183 {
184 #if 0
185   /* Get a pointer into the last 4 bytes of clockBuf. */
186   u32_t *lptr1 = (u32_t *)((char *)&clockBuf[3]);
187 
188   /*
189    * Initialize our seed using the real-time clock, the idle
190    * counter, the millisecond timer, and the hardware timer
191    * tick counter.  The real-time clock and the hardware
192    * tick counter are the best sources of randomness but
193    * since the tick counter is only 16 bit (and truncated
194    * at that), the idle counter and millisecond timer
195    * (which may be small values) are added to help
196    * randomize the lower 16 bits of the seed.
197    */
198   readClk();
199   avRandomSeed += *(u32_t *)clockBuf + *lptr1 + OSIdleCtr
200            + ppp_mtime() + ((u32_t)TM1 << 16) + TM1;
201 #else
202   avRandomSeed += sys_jiffies(); /* XXX */
203 #endif
204 
205   /* Initialize the Borland random number generator. */
206   srand((unsigned)avRandomSeed);
207 }
208 
209 /*
210  * Randomize our random seed value.  Here we use the fact that
211  * this function is called at *truely random* times by the polling
212  * and network functions.  Here we only get 16 bits of new random
213  * value but we use the previous value to randomize the other 16
214  * bits.
215  */
216 void
avRandomize(void)217 avRandomize(void)
218 {
219   static u32_t last_jiffies;
220 
221   if (!avRandomized) {
222     avRandomized = !0;
223     avRandomInit();
224     /* The initialization function also updates the seed. */
225   } else {
226     /* avRandomSeed += (avRandomSeed << 16) + TM1; */
227     avRandomSeed += (sys_jiffies() - last_jiffies); /* XXX */
228   }
229   last_jiffies = sys_jiffies();
230 }
231 
232 /*
233  * Return a new random number.
234  * Here we use the Borland rand() function to supply a pseudo random
235  * number which we make truely random by combining it with our own
236  * seed which is randomized by truely random events.
237  * Thus the numbers will be truely random unless there have been no
238  * operator or network events in which case it will be pseudo random
239  * seeded by the real time clock.
240  */
241 u32_t
avRandom()242 avRandom()
243 {
244   return ((((u32_t)rand() << 16) + rand()) + avRandomSeed);
245 }
246 
247 #endif /* MD5_SUPPORT */
248 
249 #endif /* PPP_SUPPORT */
250