--- /dev/null
+/* -*-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 <ctype.h>
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+/* --- 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 -------------------------------------------------*/
--- /dev/null
+/* -*-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 <stdio.h>
+
+#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
~mdw / become / commitdiff