| 1 | /* -*-c-*- |
| 2 | * |
| 3 | * $Id: rand.c,v 1.3 1998/01/12 16:46:23 mdw Exp $ |
| 4 | * |
| 5 | * Random number generation |
| 6 | * |
| 7 | * (c) 1998 EBI |
| 8 | */ |
| 9 | |
| 10 | /*----- Licencing notice --------------------------------------------------* |
| 11 | * |
| 12 | * This file is part of Become. |
| 13 | * |
| 14 | * Become is free software; you can redistribute it and/or modify |
| 15 | * it under the terms of the GNU General Public License as published by |
| 16 | * the Free Software Foundation; either version 2 of the License, or |
| 17 | * (at your option) any later version. |
| 18 | * |
| 19 | * Become is distributed in the hope that it will be useful, |
| 20 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 21 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 22 | * GNU General Public License for more details. |
| 23 | * |
| 24 | * You should have received a copy of the GNU General Public License |
| 25 | * along with `become'; if not, write to the Free Software Foundation, |
| 26 | * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
| 27 | */ |
| 28 | |
| 29 | /*----- Revision history --------------------------------------------------* |
| 30 | * |
| 31 | * $Log: rand.c,v $ |
| 32 | * Revision 1.3 1998/01/12 16:46:23 mdw |
| 33 | * Fix copyright date. |
| 34 | * |
| 35 | * Revision 1.2 1997/08/07 09:47:07 mdw |
| 36 | * Fix address of the FSF. |
| 37 | * |
| 38 | * Revision 1.1 1997/08/07 09:46:05 mdw |
| 39 | * New source file added to maintain a randomness pool. |
| 40 | * |
| 41 | */ |
| 42 | |
| 43 | /*----- Header files ------------------------------------------------------*/ |
| 44 | |
| 45 | /* --- ANSI headers --- */ |
| 46 | |
| 47 | #include <ctype.h> |
| 48 | #include <errno.h> |
| 49 | #include <stdio.h> |
| 50 | #include <stdlib.h> |
| 51 | #include <string.h> |
| 52 | #include <time.h> |
| 53 | |
| 54 | /* --- Local headers --- */ |
| 55 | |
| 56 | #include "become.h" |
| 57 | #include "config.h" |
| 58 | #include "icrypt.h" |
| 59 | #include "md5.h" |
| 60 | #include "rand.h" |
| 61 | #include "tx.h" |
| 62 | #include "utils.h" |
| 63 | |
| 64 | /*----- Magic numbers -----------------------------------------------------*/ |
| 65 | |
| 66 | #define rand__seedBits 512 /* Number of random seed bits */ |
| 67 | |
| 68 | /*----- Persistant state --------------------------------------------------*/ |
| 69 | |
| 70 | static unsigned char rand__pool[rand__seedBits / 8]; /* Entropy pool */ |
| 71 | static size_t rand__i = 0; /* Index into entropy pool */ |
| 72 | static size_t rand__r = 0; /* Rotation to apply to next byte */ |
| 73 | |
| 74 | /*----- Main code ---------------------------------------------------------*/ |
| 75 | |
| 76 | /* --- @rand_read@ --- * |
| 77 | * |
| 78 | * Arguments: @FILE *fp@ = pointer to file to read from |
| 79 | * |
| 80 | * Returns: --- |
| 81 | * |
| 82 | * Use: Reads a random number seed from the stream. |
| 83 | */ |
| 84 | |
| 85 | void rand_read(FILE *fp) |
| 86 | { |
| 87 | tx_getBits(rand__pool, rand__seedBits, fp); |
| 88 | rand__i = 0; |
| 89 | rand__r = 0; |
| 90 | T( traceblk(TRACE_RAND, "rand: loaded randomness pool", |
| 91 | rand__pool, sizeof(rand__pool)); ) |
| 92 | } |
| 93 | |
| 94 | /* --- @rand_write@ --- * |
| 95 | * |
| 96 | * Arguments: @FILE *fp@ = pointer to file to write on |
| 97 | * |
| 98 | * Returns: --- |
| 99 | * |
| 100 | * Use: Writes a random number seed back to the stream. |
| 101 | */ |
| 102 | |
| 103 | void rand_write(FILE *fp) |
| 104 | { |
| 105 | rand_churn(); |
| 106 | tx_putBits(rand__pool, rand__seedBits, fp); |
| 107 | } |
| 108 | |
| 109 | /* --- @rand_clear@ --- * |
| 110 | * |
| 111 | * Arguments: --- |
| 112 | * |
| 113 | * Returns: --- |
| 114 | * |
| 115 | * Use: Clears the random number pool. |
| 116 | */ |
| 117 | |
| 118 | void rand_clear(void) |
| 119 | { |
| 120 | memset(rand__pool, 0, sizeof(rand__pool)); |
| 121 | T( trace(TRACE_RAND, "rand: cleared randomness pool"); ) |
| 122 | rand__i = 0; |
| 123 | rand__r = 0; |
| 124 | } |
| 125 | |
| 126 | /* --- @rand_encrypt@ --- * |
| 127 | * |
| 128 | * Arguments: @icrypt_job *j@ = pointer to an encryption job to apply |
| 129 | * |
| 130 | * Returns: --- |
| 131 | * |
| 132 | * Use: Encrypts the randomness pool with a given key. This should |
| 133 | * be done before use, in case the pool gets compromised. |
| 134 | */ |
| 135 | |
| 136 | void rand_encrypt(icrypt_job *j) |
| 137 | { |
| 138 | icrypt_encrypt(j, rand__pool, rand__pool, sizeof(rand__pool)); |
| 139 | rand__i = 0; |
| 140 | rand__r = 0; |
| 141 | T( traceblk(TRACE_RAND, "encrypted randomness pool", |
| 142 | rand__pool, sizeof(rand__pool)); ) |
| 143 | } |
| 144 | |
| 145 | /* --- @rand_add@ --- * |
| 146 | * |
| 147 | * Arguments: @const void *p@ = pointer to some data |
| 148 | * @size_t sz@ = size of the data in bytes |
| 149 | * |
| 150 | * Returns: --- |
| 151 | * |
| 152 | * Use: Adds entropy to the pool. |
| 153 | */ |
| 154 | |
| 155 | void rand_add(const void *p, size_t sz) |
| 156 | { |
| 157 | /* --- Method --- * |
| 158 | * |
| 159 | * Entropy is inserted byte-by-byte. The method used is derived from |
| 160 | * Linux's `drivers/char/random.c', which is in turn appears to be inspired |
| 161 | * by SHA-1. |
| 162 | * |
| 163 | * Imagine the randomness pool as 8 parallel shift registers. To insert |
| 164 | * a byte into the pool, XOR it with bytes picked according to a primitive |
| 165 | * polynomial mod 2, and rotate one place to the left. (The rotation is |
| 166 | * from SHA-1; it introduces some interaction between the registers.) |
| 167 | */ |
| 168 | |
| 169 | size_t i = rand__i; |
| 170 | const unsigned char *cp = p; |
| 171 | size_t mask = (rand__seedBits / 8) - 1; |
| 172 | size_t r = rand__r; |
| 173 | unsigned int x; |
| 174 | |
| 175 | /* --- Ensure the polynomial is valid --- * |
| 176 | * |
| 177 | * The current polynomal is %$x^{64} + x^4 + x^3 + x + 1$% (picked from |
| 178 | * Schneier's excellent book). If the pool size changes, though, I'll |
| 179 | * need another polynomial. |
| 180 | */ |
| 181 | |
| 182 | #if rand__seedBits / 8 != 64 |
| 183 | # error Change the polynomal in rand_add |
| 184 | #endif |
| 185 | |
| 186 | T( traceblk(TRACE_RAND, "rand: incoming entropy", p, sz); ) |
| 187 | |
| 188 | /* --- Add values to the entropy pool --- */ |
| 189 | |
| 190 | while (sz) { |
| 191 | x = *cp++ & 0xffu; |
| 192 | if (r) |
| 193 | x = ((x << r) | (x >> (8 - r))); |
| 194 | x ^= (rand__pool[i] ^ |
| 195 | rand__pool[(i + 1) & mask] ^ |
| 196 | rand__pool[(i + 3) & mask] ^ |
| 197 | rand__pool[(i + 4) & mask]); |
| 198 | rand__pool[i] = ((x << 1) | (x >> 7)) & 0xffu; |
| 199 | sz--; |
| 200 | i = (i + 1) & mask; |
| 201 | r = (r + 3) & 7; |
| 202 | } |
| 203 | |
| 204 | /* --- Update the global counters --- */ |
| 205 | |
| 206 | rand__r = r; |
| 207 | rand__i = i; |
| 208 | |
| 209 | T( traceblk(TRACE_RAND, "rand: added some entropy", |
| 210 | rand__pool, sizeof(rand__pool)); ) |
| 211 | } |
| 212 | |
| 213 | /* --- @rand_extract@ --- * |
| 214 | * |
| 215 | * Arguments: @unsigned char *b@ = pointer to output buffer |
| 216 | * @size_t sz@ = number of bytes wanted |
| 217 | * |
| 218 | * Returns: --- |
| 219 | * |
| 220 | * Use: Produces a number of random bytes. |
| 221 | */ |
| 222 | |
| 223 | void rand_extract(unsigned char *b, size_t sz) |
| 224 | { |
| 225 | /* --- Method --- * |
| 226 | * |
| 227 | * Hash the buffer with a secure hash (or, in this case, with MD5 and hope |
| 228 | * for the best...). If this gives us enough bytes, fill the output |
| 229 | * buffer; otherwise copy the whole hash out. The contribute the hash back |
| 230 | * into the randomness pool with @rand_add@ to provide some feedback. |
| 231 | * |
| 232 | * The secure hash gives us good mixing over the whole of the randomness |
| 233 | * pool, and attempts to ensure that an attacker receiving our random |
| 234 | * numbers can't predict any numbers we don't actually give him. |
| 235 | */ |
| 236 | |
| 237 | size_t c; |
| 238 | unsigned char mdbuf[MD5_HASHSIZE]; |
| 239 | md5 md; |
| 240 | |
| 241 | T( trace(TRACE_RAND, "rand: extracting entropy"); ) |
| 242 | |
| 243 | while (sz) { |
| 244 | c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz; |
| 245 | md5_init(&md); |
| 246 | md5_buffer(&md, rand__pool, sizeof(rand__pool)); |
| 247 | md5_final(&md, mdbuf); |
| 248 | memcpy(b, mdbuf, c); |
| 249 | rand_add(mdbuf, c); |
| 250 | b += c; sz -= c; |
| 251 | } |
| 252 | burn(mdbuf); burn(md); |
| 253 | |
| 254 | T( trace(TRACE_RAND, "rand: finished extracting entropy"); ) |
| 255 | } |
| 256 | |
| 257 | /* --- @rand_churn@ --- * |
| 258 | * |
| 259 | * Arguments: --- |
| 260 | * |
| 261 | * Returns: --- |
| 262 | * |
| 263 | * Use: Churns the randomness pool completely. The pool is replaced |
| 264 | * by repeated MD5-ings of itself. |
| 265 | */ |
| 266 | |
| 267 | void rand_churn(void) |
| 268 | { |
| 269 | md5 md; |
| 270 | unsigned char mdbuf[MD5_HASHSIZE]; |
| 271 | size_t sz = sizeof(rand__pool); |
| 272 | size_t c; |
| 273 | |
| 274 | T( trace(TRACE_RAND, "rand: churning pool"); ) |
| 275 | |
| 276 | rand__i = 0; |
| 277 | rand__r = 0; |
| 278 | |
| 279 | while (sz) { |
| 280 | c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz; |
| 281 | md5_init(&md); |
| 282 | md5_buffer(&md, rand__pool, sizeof(rand__pool)); |
| 283 | md5_final(&md, mdbuf); |
| 284 | rand_add(mdbuf, c); |
| 285 | sz -= c; |
| 286 | } |
| 287 | |
| 288 | rand__i = 0; |
| 289 | rand__r = 0; |
| 290 | |
| 291 | burn(mdbuf); burn(md); |
| 292 | |
| 293 | T( trace(TRACE_RAND, "rand: finished churning pool"); ) |
| 294 | } |
| 295 | |
| 296 | /*----- That's all, folks -------------------------------------------------*/ |