lwip_magic.c

00001 /*
00002  * magic.c - PPP Magic Number routines.
00003  *
00004  * Copyright (c) 1984-2000 Carnegie Mellon University. All rights reserved.
00005  *
00006  * Redistribution and use in source and binary forms, with or without
00007  * modification, are permitted provided that the following conditions
00008  * are met:
00009  *
00010  * 1. Redistributions of source code must retain the above copyright
00011  *    notice, this list of conditions and the following disclaimer.
00012  *
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in
00015  *    the documentation and/or other materials provided with the
00016  *    distribution.
00017  *
00018  * 3. The name "Carnegie Mellon University" must not be used to
00019  *    endorse or promote products derived from this software without
00020  *    prior written permission. For permission or any legal
00021  *    details, please contact
00022  *      Office of Technology Transfer
00023  *      Carnegie Mellon University
00024  *      5000 Forbes Avenue
00025  *      Pittsburgh, PA  15213-3890
00026  *      (412) 268-4387, fax: (412) 268-7395
00027  *      tech-transfer@andrew.cmu.edu
00028  *
00029  * 4. Redistributions of any form whatsoever must retain the following
00030  *    acknowledgment:
00031  *    "This product includes software developed by Computing Services
00032  *     at Carnegie Mellon University (http://www.cmu.edu/computing/)."
00033  *
00034  * CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO
00035  * THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
00036  * AND FITNESS, IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
00037  * FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
00038  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
00039  * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
00040  * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
00041  */
00042 /*****************************************************************************
00043 * randm.c - Random number generator program file.
00044 *
00045 * Copyright (c) 2003 by Marc Boucher, Services Informatiques (MBSI) inc.
00046 * Copyright (c) 1998 by Global Election Systems Inc.
00047 *
00048 * The authors hereby grant permission to use, copy, modify, distribute,
00049 * and license this software and its documentation for any purpose, provided
00050 * that existing copyright notices are retained in all copies and that this
00051 * notice and the following disclaimer are included verbatim in any
00052 * distributions. No written agreement, license, or royalty fee is required
00053 * for any of the authorized uses.
00054 *
00055 * THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS *AS IS* AND ANY EXPRESS OR
00056 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00057 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00058 * IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
00059 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00060 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00061 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00062 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00063 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00064 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00065 *
00066 ******************************************************************************
00067 * REVISION HISTORY
00068 *
00069 * 03-01-01 Marc Boucher <marc@mbsi.ca>
00070 *   Ported to lwIP.
00071 * 98-06-03 Guy Lancaster <lancasterg@acm.org>, Global Election Systems Inc.
00072 *   Extracted from avos.
00073 *****************************************************************************/
00074 
00075 #include "netif/ppp/ppp_opts.h"
00076 #if PPP_SUPPORT /* don't build if not configured for use in lwipopts.h */
00077 
00078 #include "netif/ppp/ppp_impl.h"
00079 #include "netif/ppp/magic.h"
00080 
00081 #if PPP_MD5_RANDM /* Using MD5 for better randomness if enabled */
00082 
00083 #include "netif/ppp/pppcrypt.h"
00084 
00085 #define MD5_HASH_SIZE 16
00086 static char magic_randpool[MD5_HASH_SIZE];   /* Pool of randomness. */
00087 static long magic_randcount;      /* Pseudo-random incrementer */
00088 static u32_t magic_randomseed;    /* Seed used for random number generation. */
00089 
00090 /*
00091  * Churn the randomness pool on a random event.  Call this early and often
00092  *  on random and semi-random system events to build randomness in time for
00093  *  usage.  For randomly timed events, pass a null pointer and a zero length
00094  *  and this will use the system timer and other sources to add randomness.
00095  *  If new random data is available, pass a pointer to that and it will be
00096  *  included.
00097  *
00098  * Ref: Applied Cryptography 2nd Ed. by Bruce Schneier p. 427
00099  */
00100 static void magic_churnrand(char *rand_data, u32_t rand_len) {
00101   lwip_md5_context md5_ctx;
00102 
00103   /* LWIP_DEBUGF(LOG_INFO, ("magic_churnrand: %u@%P\n", rand_len, rand_data)); */
00104   lwip_md5_init(&md5_ctx);
00105   lwip_md5_starts(&md5_ctx);
00106   lwip_md5_update(&md5_ctx, (u_char *)magic_randpool, sizeof(magic_randpool));
00107   if (rand_data) {
00108     lwip_md5_update(&md5_ctx, (u_char *)rand_data, rand_len);
00109   } else {
00110     struct {
00111       /* INCLUDE fields for any system sources of randomness */
00112       u32_t jiffies;
00113 #ifdef LWIP_RAND
00114       u32_t rand;
00115 #endif /* LWIP_RAND */
00116     } sys_data;
00117     magic_randomseed += sys_jiffies();
00118     sys_data.jiffies = magic_randomseed;
00119 #ifdef LWIP_RAND
00120     sys_data.rand = LWIP_RAND();
00121 #endif /* LWIP_RAND */
00122     /* Load sys_data fields here. */
00123     lwip_md5_update(&md5_ctx, (u_char *)&sys_data, sizeof(sys_data));
00124   }
00125   lwip_md5_finish(&md5_ctx, (u_char *)magic_randpool);
00126   lwip_md5_free(&md5_ctx);
00127 /*  LWIP_DEBUGF(LOG_INFO, ("magic_churnrand: -> 0\n")); */
00128 }
00129 
00130 /*
00131  * Initialize the random number generator.
00132  */
00133 void magic_init(void) {
00134   magic_churnrand(NULL, 0);
00135 }
00136 
00137 /*
00138  * Randomize our random seed value.
00139  */
00140 void magic_randomize(void) {
00141   magic_churnrand(NULL, 0);
00142 }
00143 
00144 /*
00145  * magic_random_bytes - Fill a buffer with random bytes.
00146  *
00147  * Use the random pool to generate random data.  This degrades to pseudo
00148  *  random when used faster than randomness is supplied using magic_churnrand().
00149  * Note: It's important that there be sufficient randomness in magic_randpool
00150  *  before this is called for otherwise the range of the result may be
00151  *  narrow enough to make a search feasible.
00152  *
00153  * Ref: Applied Cryptography 2nd Ed. by Bruce Schneier p. 427
00154  *
00155  * XXX Why does he not just call magic_churnrand() for each block?  Probably
00156  *  so that you don't ever publish the seed which could possibly help
00157  *  predict future values.
00158  * XXX Why don't we preserve md5 between blocks and just update it with
00159  *  magic_randcount each time?  Probably there is a weakness but I wish that
00160  *  it was documented.
00161  */
00162 void magic_random_bytes(unsigned char *buf, u32_t buf_len) {
00163   lwip_md5_context md5_ctx;
00164   u_char tmp[MD5_HASH_SIZE];
00165   u32_t n;
00166 
00167   while (buf_len > 0) {
00168     lwip_md5_init(&md5_ctx);
00169     lwip_md5_starts(&md5_ctx);
00170     lwip_md5_update(&md5_ctx, (u_char *)magic_randpool, sizeof(magic_randpool));
00171     lwip_md5_update(&md5_ctx, (u_char *)&magic_randcount, sizeof(magic_randcount));
00172     lwip_md5_finish(&md5_ctx, tmp);
00173     lwip_md5_free(&md5_ctx);
00174     magic_randcount++;
00175     n = LWIP_MIN(buf_len, MD5_HASH_SIZE);
00176     MEMCPY(buf, tmp, n);
00177     buf += n;
00178     buf_len -= n;
00179   }
00180 }
00181 
00182 /*
00183  * Return a new random number.
00184  */
00185 u32_t magic(void) {
00186   u32_t new_rand;
00187 
00188   magic_random_bytes((unsigned char *)&new_rand, sizeof(new_rand));
00189 
00190   return new_rand;
00191 }
00192 
00193 #else /* PPP_MD5_RANDM */
00194 
00195 /*****************************/
00196 /*** LOCAL DATA STRUCTURES ***/
00197 /*****************************/
00198 #ifndef LWIP_RAND
00199 static int  magic_randomized;       /* Set when truely randomized. */
00200 #endif /* LWIP_RAND */
00201 static u32_t magic_randomseed;      /* Seed used for random number generation. */
00202 
00203 
00204 /***********************************/
00205 /*** PUBLIC FUNCTION DEFINITIONS ***/
00206 /***********************************/
00207 
00208 /*
00209  * Initialize the random number generator.
00210  *
00211  * Here we attempt to compute a random number seed but even if
00212  * it isn't random, we'll randomize it later.
00213  *
00214  * The current method uses the fields from the real time clock,
00215  * the idle process counter, the millisecond counter, and the
00216  * hardware timer tick counter.  When this is invoked
00217  * in startup(), then the idle counter and timer values may
00218  * repeat after each boot and the real time clock may not be
00219  * operational.  Thus we call it again on the first random
00220  * event.
00221  */
00222 void magic_init(void) {
00223   magic_randomseed += sys_jiffies();
00224 #ifndef LWIP_RAND
00225   /* Initialize the Borland random number generator. */
00226   srand((unsigned)magic_randomseed);
00227 #endif /* LWIP_RAND */
00228 }
00229 
00230 /*
00231  * magic_init - Initialize the magic number generator.
00232  *
00233  * Randomize our random seed value.  Here we use the fact that
00234  * this function is called at *truely random* times by the polling
00235  * and network functions.  Here we only get 16 bits of new random
00236  * value but we use the previous value to randomize the other 16
00237  * bits.
00238  */
00239 void magic_randomize(void) {
00240 #ifndef LWIP_RAND
00241   if (!magic_randomized) {
00242     magic_randomized = !0;
00243     magic_init();
00244     /* The initialization function also updates the seed. */
00245   } else {
00246 #endif /* LWIP_RAND */
00247     magic_randomseed += sys_jiffies();
00248 #ifndef LWIP_RAND
00249   }
00250 #endif /* LWIP_RAND */
00251 }
00252 
00253 /*
00254  * Return a new random number.
00255  *
00256  * Here we use the Borland rand() function to supply a pseudo random
00257  * number which we make truely random by combining it with our own
00258  * seed which is randomized by truely random events.
00259  * Thus the numbers will be truely random unless there have been no
00260  * operator or network events in which case it will be pseudo random
00261  * seeded by the real time clock.
00262  */
00263 u32_t magic(void) {
00264 #ifdef LWIP_RAND
00265   return LWIP_RAND() + magic_randomseed;
00266 #else /* LWIP_RAND */
00267   return ((u32_t)rand() << 16) + (u32_t)rand() + magic_randomseed;
00268 #endif /* LWIP_RAND */
00269 }
00270 
00271 /*
00272  * magic_random_bytes - Fill a buffer with random bytes.
00273  */
00274 void magic_random_bytes(unsigned char *buf, u32_t buf_len) {
00275   u32_t new_rand, n;
00276 
00277   while (buf_len > 0) {
00278     new_rand = magic();
00279     n = LWIP_MIN(buf_len, sizeof(new_rand));
00280     MEMCPY(buf, &new_rand, n);
00281     buf += n;
00282     buf_len -= n;
00283   }
00284 }
00285 #endif /* PPP_MD5_RANDM */
00286 
00287 /*
00288  * Return a new random number between 0 and (2^pow)-1 included.
00289  */
00290 u32_t magic_pow(u8_t pow) {
00291   return magic() & ~(~0UL<<pow);
00292 }
00293 
00294 #endif /* PPP_SUPPORT */