1/* 2 * magic.c - PPP Magic Number routines. 3 * 4 * Copyright (c) 1984-2000 Carnegie Mellon University. All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 18 * 3. The name "Carnegie Mellon University" must not be used to 19 * endorse or promote products derived from this software without 20 * prior written permission. For permission or any legal 21 * details, please contact 22 * Office of Technology Transfer 23 * Carnegie Mellon University 24 * 5000 Forbes Avenue 25 * Pittsburgh, PA 15213-3890 26 * (412) 268-4387, fax: (412) 268-7395 27 * tech-transfer@andrew.cmu.edu 28 * 29 * 4. Redistributions of any form whatsoever must retain the following 30 * acknowledgment: 31 * "This product includes software developed by Computing Services 32 * at Carnegie Mellon University (http://www.cmu.edu/computing/)." 33 * 34 * CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO 35 * THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 36 * AND FITNESS, IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE 37 * FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 38 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 39 * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING 40 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 41 */ 42/***************************************************************************** 43* randm.c - Random number generator program file. 44* 45* Copyright (c) 2003 by Marc Boucher, Services Informatiques (MBSI) inc. 46* Copyright (c) 1998 by Global Election Systems Inc. 47* 48* The authors hereby grant permission to use, copy, modify, distribute, 49* and license this software and its documentation for any purpose, provided 50* that existing copyright notices are retained in all copies and that this 51* notice and the following disclaimer are included verbatim in any 52* distributions. No written agreement, license, or royalty fee is required 53* for any of the authorized uses. 54* 55* THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS *AS IS* AND ANY EXPRESS OR 56* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 57* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 58* IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 59* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 60* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 61* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 62* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 63* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 64* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 65* 66****************************************************************************** 67* REVISION HISTORY 68* 69* 03-01-01 Marc Boucher <marc@mbsi.ca> 70* Ported to lwIP. 71* 98-06-03 Guy Lancaster <lancasterg@acm.org>, Global Election Systems Inc. 72* Extracted from avos. 73*****************************************************************************/ 74 75#include "netif/ppp/ppp_opts.h" 76#if PPP_SUPPORT /* don't build if not configured for use in lwipopts.h */ 77 78#include "netif/ppp/ppp_impl.h" 79#include "netif/ppp/magic.h" 80 81#if PPP_MD5_RANDM /* Using MD5 for better randomness if enabled */ 82 83#include "netif/ppp/pppcrypt.h" 84 85#define MD5_HASH_SIZE 16 86static char magic_randpool[MD5_HASH_SIZE]; /* Pool of randomness. */ 87static long magic_randcount; /* Pseudo-random incrementer */ 88static u32_t magic_randomseed; /* Seed used for random number generation. */ 89 90/* 91 * Churn the randomness pool on a random event. Call this early and often 92 * on random and semi-random system events to build randomness in time for 93 * usage. For randomly timed events, pass a null pointer and a zero length 94 * and this will use the system timer and other sources to add randomness. 95 * If new random data is available, pass a pointer to that and it will be 96 * included. 97 * 98 * Ref: Applied Cryptography 2nd Ed. by Bruce Schneier p. 427 99 */ 100static void magic_churnrand(char *rand_data, u32_t rand_len) { 101 lwip_md5_context md5_ctx; 102 103 /* LWIP_DEBUGF(LOG_INFO, ("magic_churnrand: %u@%P\n", rand_len, rand_data)); */ 104 lwip_md5_init(&md5_ctx); 105 lwip_md5_starts(&md5_ctx); 106 lwip_md5_update(&md5_ctx, (u_char *)magic_randpool, sizeof(magic_randpool)); 107 if (rand_data) { 108 lwip_md5_update(&md5_ctx, (u_char *)rand_data, rand_len); 109 } else { 110 struct { 111 /* INCLUDE fields for any system sources of randomness */ 112 u32_t jiffies; 113#ifdef LWIP_RAND 114 u32_t rand; 115#endif /* LWIP_RAND */ 116 } sys_data; 117 magic_randomseed += sys_jiffies(); 118 sys_data.jiffies = magic_randomseed; 119#ifdef LWIP_RAND 120 sys_data.rand = LWIP_RAND(); 121#endif /* LWIP_RAND */ 122 /* Load sys_data fields here. */ 123 lwip_md5_update(&md5_ctx, (u_char *)&sys_data, sizeof(sys_data)); 124 } 125 lwip_md5_finish(&md5_ctx, (u_char *)magic_randpool); 126 lwip_md5_free(&md5_ctx); 127/* LWIP_DEBUGF(LOG_INFO, ("magic_churnrand: -> 0\n")); */ 128} 129 130/* 131 * Initialize the random number generator. 132 */ 133void magic_init(void) { 134 magic_churnrand(NULL, 0); 135} 136 137/* 138 * Randomize our random seed value. 139 */ 140void magic_randomize(void) { 141 magic_churnrand(NULL, 0); 142} 143 144/* 145 * magic_random_bytes - Fill a buffer with random bytes. 146 * 147 * Use the random pool to generate random data. This degrades to pseudo 148 * random when used faster than randomness is supplied using magic_churnrand(). 149 * Note: It's important that there be sufficient randomness in magic_randpool 150 * before this is called for otherwise the range of the result may be 151 * narrow enough to make a search feasible. 152 * 153 * Ref: Applied Cryptography 2nd Ed. by Bruce Schneier p. 427 154 * 155 * XXX Why does he not just call magic_churnrand() for each block? Probably 156 * so that you don't ever publish the seed which could possibly help 157 * predict future values. 158 * XXX Why don't we preserve md5 between blocks and just update it with 159 * magic_randcount each time? Probably there is a weakness but I wish that 160 * it was documented. 161 */ 162void magic_random_bytes(unsigned char *buf, u32_t buf_len) { 163 lwip_md5_context md5_ctx; 164 u_char tmp[MD5_HASH_SIZE]; 165 u32_t n; 166 167 while (buf_len > 0) { 168 lwip_md5_init(&md5_ctx); 169 lwip_md5_starts(&md5_ctx); 170 lwip_md5_update(&md5_ctx, (u_char *)magic_randpool, sizeof(magic_randpool)); 171 lwip_md5_update(&md5_ctx, (u_char *)&magic_randcount, sizeof(magic_randcount)); 172 lwip_md5_finish(&md5_ctx, tmp); 173 lwip_md5_free(&md5_ctx); 174 magic_randcount++; 175 n = LWIP_MIN(buf_len, MD5_HASH_SIZE); 176 MEMCPY(buf, tmp, n); 177 buf += n; 178 buf_len -= n; 179 } 180} 181 182/* 183 * Return a new random number. 184 */ 185u32_t magic(void) { 186 u32_t new_rand; 187 188 magic_random_bytes((unsigned char *)&new_rand, sizeof(new_rand)); 189 190 return new_rand; 191} 192 193#else /* PPP_MD5_RANDM */ 194 195/*****************************/ 196/*** LOCAL DATA STRUCTURES ***/ 197/*****************************/ 198#ifndef LWIP_RAND 199static int magic_randomized; /* Set when truely randomized. */ 200#endif /* LWIP_RAND */ 201static u32_t magic_randomseed; /* Seed used for random number generation. */ 202 203 204/***********************************/ 205/*** PUBLIC FUNCTION DEFINITIONS ***/ 206/***********************************/ 207 208/* 209 * Initialize the random number generator. 210 * 211 * Here we attempt to compute a random number seed but even if 212 * it isn't random, we'll randomize it later. 213 * 214 * The current method uses the fields from the real time clock, 215 * the idle process counter, the millisecond counter, and the 216 * hardware timer tick counter. When this is invoked 217 * in startup(), then the idle counter and timer values may 218 * repeat after each boot and the real time clock may not be 219 * operational. Thus we call it again on the first random 220 * event. 221 */ 222void magic_init(void) { 223 magic_randomseed += sys_jiffies(); 224#ifndef LWIP_RAND 225 /* Initialize the Borland random number generator. */ 226 srand((unsigned)magic_randomseed); 227#endif /* LWIP_RAND */ 228} 229 230/* 231 * magic_init - Initialize the magic number generator. 232 * 233 * Randomize our random seed value. Here we use the fact that 234 * this function is called at *truely random* times by the polling 235 * and network functions. Here we only get 16 bits of new random 236 * value but we use the previous value to randomize the other 16 237 * bits. 238 */ 239void magic_randomize(void) { 240#ifndef LWIP_RAND 241 if (!magic_randomized) { 242 magic_randomized = !0; 243 magic_init(); 244 /* The initialization function also updates the seed. */ 245 } else { 246#endif /* LWIP_RAND */ 247 magic_randomseed += sys_jiffies(); 248#ifndef LWIP_RAND 249 } 250#endif /* LWIP_RAND */ 251} 252 253/* 254 * Return a new random number. 255 * 256 * Here we use the Borland rand() function to supply a pseudo random 257 * number which we make truely random by combining it with our own 258 * seed which is randomized by truely random events. 259 * Thus the numbers will be truely random unless there have been no 260 * operator or network events in which case it will be pseudo random 261 * seeded by the real time clock. 262 */ 263u32_t magic(void) { 264#ifdef LWIP_RAND 265 return LWIP_RAND() + magic_randomseed; 266#else /* LWIP_RAND */ 267 return ((u32_t)rand() << 16) + (u32_t)rand() + magic_randomseed; 268#endif /* LWIP_RAND */ 269} 270 271/* 272 * magic_random_bytes - Fill a buffer with random bytes. 273 */ 274void magic_random_bytes(unsigned char *buf, u32_t buf_len) { 275 u32_t new_rand, n; 276 277 while (buf_len > 0) { 278 new_rand = magic(); 279 n = LWIP_MIN(buf_len, sizeof(new_rand)); 280 MEMCPY(buf, &new_rand, n); 281 buf += n; 282 buf_len -= n; 283 } 284} 285#endif /* PPP_MD5_RANDM */ 286 287/* 288 * Return a new random number between 0 and (2^pow)-1 included. 289 */ 290u32_t magic_pow(u8_t pow) { 291 return magic() & ~(~0UL<<pow); 292} 293 294#endif /* PPP_SUPPORT */ 295