From: mdw Date: Thu, 7 Aug 1997 09:46:05 +0000 (+0000) Subject: New source file added to maintain a randomness pool. X-Git-Tag: 1.3.3~132 X-Git-Url: https://git.distorted.org.uk/~mdw/become/commitdiff_plain/a62d3877288d677814f34c5c8af5a05c15eb4ec6 New source file added to maintain a randomness pool. --- diff --git a/src/rand.c b/src/rand.c new file mode 100644 index 0000000..3cbe135 --- /dev/null +++ b/src/rand.c @@ -0,0 +1,290 @@ +/* -*-c-*- + * + * $Id: rand.c,v 1.1 1997/08/07 09:46:05 mdw Exp $ + * + * Random number generation + * + * (c) 1997 EBI + */ + +/*----- Licencing notice --------------------------------------------------* + * + * This file is part of Become. + * + * Become is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * Become is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Become; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: rand.c,v $ + * Revision 1.1 1997/08/07 09:46:05 mdw + * New source file added to maintain a randomness pool. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +/* --- ANSI headers --- */ + +#include +#include +#include +#include +#include +#include + +/* --- Local headers --- */ + +#include "become.h" +#include "config.h" +#include "icrypt.h" +#include "md5.h" +#include "rand.h" +#include "tx.h" +#include "utils.h" + +/*----- Magic numbers -----------------------------------------------------*/ + +#define rand__seedBits 512 /* Number of random seed bits */ + +/*----- Persistant state --------------------------------------------------*/ + +static unsigned char rand__pool[rand__seedBits / 8]; /* Entropy pool */ +static size_t rand__i = 0; /* Index into entropy pool */ +static size_t rand__r = 0; /* Rotation to apply to next byte */ + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @rand_read@ --- * + * + * Arguments: @FILE *fp@ = pointer to file to read from + * + * Returns: --- + * + * Use: Reads a random number seed from the stream. + */ + +void rand_read(FILE *fp) +{ + tx_getBits(rand__pool, rand__seedBits, fp); + rand__i = 0; + rand__r = 0; + T( traceblk(TRACE_RAND, "rand: loaded randomness pool", + rand__pool, sizeof(rand__pool)); ) +} + +/* --- @rand_write@ --- * + * + * Arguments: @FILE *fp@ = pointer to file to write on + * + * Returns: --- + * + * Use: Writes a random number seed back to the stream. + */ + +void rand_write(FILE *fp) +{ + rand_churn(); + tx_putBits(rand__pool, rand__seedBits, fp); +} + +/* --- @rand_clear@ --- * + * + * Arguments: --- + * + * Returns: --- + * + * Use: Clears the random number pool. + */ + +void rand_clear(void) +{ + memset(rand__pool, 0, sizeof(rand__pool)); + T( trace(TRACE_RAND, "rand: cleared randomness pool"); ) + rand__i = 0; + rand__r = 0; +} + +/* --- @rand_encrypt@ --- * + * + * Arguments: @icrypt_job *j@ = pointer to an encryption job to apply + * + * Returns: --- + * + * Use: Encrypts the randomness pool with a given key. This should + * be done before use, in case the pool gets compromised. + */ + +void rand_encrypt(icrypt_job *j) +{ + icrypt_encrypt(j, rand__pool, rand__pool, sizeof(rand__pool)); + rand__i = 0; + rand__r = 0; + T( traceblk(TRACE_RAND, "encrypted randomness pool", + rand__pool, sizeof(rand__pool)); ) +} + +/* --- @rand_add@ --- * + * + * Arguments: @const void *p@ = pointer to some data + * @size_t sz@ = size of the data in bytes + * + * Returns: --- + * + * Use: Adds entropy to the pool. + */ + +void rand_add(const void *p, size_t sz) +{ + /* --- Method --- * + * + * Entropy is inserted byte-by-byte. The method used is derived from + * Linux's `drivers/char/random.c', which is in turn appears to be inspired + * by SHA-1. + * + * Imagine the randomness pool as 8 parallel shift registers. To insert + * a byte into the pool, XOR it with bytes picked according to a primitive + * polynomial mod 2, and rotate one place to the left. (The rotation is + * from SHA-1; it introduces some interaction between the registers.) + */ + + size_t i = rand__i; + const unsigned char *cp = p; + size_t mask = (rand__seedBits / 8) - 1; + size_t r = rand__r; + unsigned int x; + + /* --- Ensure the polynomial is valid --- * + * + * The current polynomal is %$x^{64} + x^4 + x^3 + x + 1$% (picked from + * Schneier's excellent book). If the pool size changes, though, I'll + * need another polynomial. + */ + +#if rand__seedBits / 8 != 64 +# error Change the polynomal in rand_add +#endif + + T( traceblk(TRACE_RAND, "rand: incoming entropy", p, sz); ) + + /* --- Add values to the entropy pool --- */ + + while (sz) { + x = *cp++ & 0xffu; + if (r) + x = ((x << r) | (x >> (8 - r))); + x ^= (rand__pool[i] ^ + rand__pool[(i + 1) & mask] ^ + rand__pool[(i + 3) & mask] ^ + rand__pool[(i + 4) & mask]); + rand__pool[i] = ((x << 1) | (x >> 7)) & 0xffu; + sz--; + i = (i + 1) & mask; + r = (r + 3) & 7; + } + + /* --- Update the global counters --- */ + + rand__r = r; + rand__i = i; + + T( traceblk(TRACE_RAND, "rand: added some entropy", + rand__pool, sizeof(rand__pool)); ) +} + +/* --- @rand_extract@ --- * + * + * Arguments: @unsigned char *b@ = pointer to output buffer + * @size_t sz@ = number of bytes wanted + * + * Returns: --- + * + * Use: Produces a number of random bytes. + */ + +void rand_extract(unsigned char *b, size_t sz) +{ + /* --- Method --- * + * + * Hash the buffer with a secure hash (or, in this case, with MD5 and hope + * for the best...). If this gives us enough bytes, fill the output + * buffer; otherwise copy the whole hash out. The contribute the hash back + * into the randomness pool with @rand_add@ to provide some feedback. + * + * The secure hash gives us good mixing over the whole of the randomness + * pool, and attempts to ensure that an attacker receiving our random + * numbers can't predict any numbers we don't actually give him. + */ + + size_t c; + unsigned char mdbuf[MD5_HASHSIZE]; + md5 md; + + T( trace(TRACE_RAND, "rand: extracting entropy"); ) + + while (sz) { + c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz; + md5_init(&md); + md5_buffer(&md, rand__pool, sizeof(rand__pool)); + md5_final(&md, mdbuf); + memcpy(b, mdbuf, c); + rand_add(mdbuf, c); + b += c; sz -= c; + } + burn(mdbuf); burn(md); + + T( trace(TRACE_RAND, "rand: finished extracting entropy"); ) +} + +/* --- @rand_churn@ --- * + * + * Arguments: --- + * + * Returns: --- + * + * Use: Churns the randomness pool completely. The pool is replaced + * by repeated MD5-ings of itself. + */ + +void rand_churn(void) +{ + md5 md; + unsigned char mdbuf[MD5_HASHSIZE]; + size_t sz = sizeof(rand__pool); + size_t c; + + T( trace(TRACE_RAND, "rand: churning pool"); ) + + rand__i = 0; + rand__r = 0; + + while (sz) { + c = (sz >= sizeof(mdbuf)) ? sizeof(mdbuf) : sz; + md5_init(&md); + md5_buffer(&md, rand__pool, sizeof(rand__pool)); + md5_final(&md, mdbuf); + rand_add(mdbuf, c); + sz -= c; + } + + rand__i = 0; + rand__r = 0; + + burn(mdbuf); burn(md); + + T( trace(TRACE_RAND, "rand: finished churning pool"); ) +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/src/rand.h b/src/rand.h new file mode 100644 index 0000000..bbd0fff --- /dev/null +++ b/src/rand.h @@ -0,0 +1,141 @@ +/* -*-c-*- + * + * $Id: rand.h,v 1.1 1997/08/07 09:46:05 mdw Exp $ + * + * Random number generation + * + * (c) 1997 EBI + */ + +/*----- Licencing notice --------------------------------------------------* + * + * This file is part of Become. + * + * Become is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * Become is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Become; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: rand.h,v $ + * Revision 1.1 1997/08/07 09:46:05 mdw + * New source file added to maintain a randomness pool. + * + */ + +#ifndef RAND_H +#define RAND_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Required headers --------------------------------------------------*/ + +#include + +#ifndef ICRYPT_H +# include "icrypt.h" +#endif + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @rand_read@ --- * + * + * Arguments: @FILE *fp@ = pointer to file to read from + * + * Returns: --- + * + * Use: Reads a random number seed from the stream. + */ + +extern void rand_read(FILE */*fp*/); + +/* --- @rand_write@ --- * + * + * Arguments: @FILE *fp@ = pointer to file to write on + * + * Returns: --- + * + * Use: Writes a random number seed back to the stream. + */ + +extern void rand_write(FILE */*fp*/); + +/* --- @rand_clear@ --- * + * + * Arguments: --- + * + * Returns: --- + * + * Use: Clears the random number pool. + */ + +extern void rand_clear(void); + +/* --- @rand_encrypt@ --- * + * + * Arguments: @icrypt_job *j@ = pointer to an encryption job to apply + * + * Returns: --- + * + * Use: Encrypts the randomness pool with a given key. This should + * be done before use, in case the pool gets compromised. + */ + +extern void rand_encrypt(icrypt_job */*j*/); + +/* --- @rand_add@ --- * + * + * Arguments: @const void *p@ = pointer to some data + * @size_t sz@ = size of the data in bytes + * + * Returns: --- + * + * Use: Adds entropy to the pool. + */ + +extern void rand_add(const void */*p*/, size_t /*sz*/); + +/* --- @rand_extract@ --- * + * + * Arguments: @unsigned char *b@ = pointer to output buffer + * @size_t sz@ = number of bytes wanted + * + * Returns: --- + * + * Use: Produces a number of random bytes. + */ + +extern void rand_extract(unsigned char */*b*/, size_t /*sz*/); + +/* --- @rand_churn@ --- * + * + * Arguments: --- + * + * Returns: --- + * + * Use: Churns the randomness pool completely. The pool is replaced + * by repeated MD5-ings of itself. + */ + +extern void rand_churn(void); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif