Fortuna as default PRNG

Rewrite prng_fortuna.c to much more closely match the description of
Fortuna in chapter 9 of Cryptography Engineering.  Add a facility to
get OS entropy and implement it for Unix and Windows (not yet tested
on Windows) to replace prng/fortuna/entropy.c.  Rewrite the test
harness to always ensure stable output and perform a statistical test
on the predictable internal state resulting from the stable-output
tests.

ticket: 6874

git-svn-id: svn://anonsvn.mit.edu/krb5/trunk@24652 dc483132-0cff-0310-8789-dd5450dbe970

12 files changed, 497 insertions, 839 deletions

diff --git a/src/lib/crypto/krb/prng/fortuna/Makefile.in b/src/lib/crypto/krb/prng/fortuna/Makefile.in
index 544f4a1540..f78ecef5c1 100644
--- a/src/lib/crypto/krb/prng/fortuna/Makefile.in
+++ b/src/lib/crypto/krb/prng/fortuna/Makefile.in
@@ -11,13 +11,11 @@ PROG_LIBPATH=-L$(TOPLIBD)
 PROG_RPATH=$(KRB5_LIBDIR)
 
 STLIBOBJS= \
-	prng_fortuna.o entropy.o
+	prng_fortuna.o
 OBJS= \
-	$(OUTPRE)prng_fortuna.$(OBJEXT) \
-	$(OUTPRE)entropy.$(OBJEXT)
+	$(OUTPRE)prng_fortuna.$(OBJEXT)
 
 SRCS=\
-	$(srcdir)/entropy.c \
 	$(srcdir)/prng_fortuna.c 
 
 all-unix:: all-libobjs
@@ -27,24 +25,15 @@ includes:: depend
 depend:: $(SRCS)
 
 t_fortuna: t_fortuna.$(OBJEXT) $(SUPPORT_DEPLIB)
-	$(CC_LINK) -o t_fortuna t_fortuna.$(OBJEXT) -lcom_err $(SUPPORT_LIB) $(CRYPTO_DEPLIB)
-
-t_fortuna_make_oct: t_fortuna_make_oct.$(OBJEXT) $(SUPPORT_DEPLIB)
-	$(CC_LINK) -o t_fortuna_make_oct t_fortuna_make_oct.$(OBJEXT) -lcom_err $(SUPPORT_LIB) $(CRYPTO_DEPLIB)
+	$(CC_LINK) -o t_fortuna t_fortuna.$(OBJEXT) -lcom_err $(SUPPORT_LIB) \
+		$(CRYPTO_DEPLIB)
 
 check-unix:: t_fortuna t_fortuna_make_oct
-# ifdef TEST_FORTUNA
-ifeq ("@PRNG_FORTUNA_TEST@","yes")
-	$(RUN_SETUP) $(VALGRIND) ./t_fortuna_make_oct > t_fortuna_make_oct.result && \
-	diff t_fortuna_make_oct.result t_fortuna_make_oct.expected
-else
-	$(RUN_SETUP) $(VALGRIND) ./t_fortuna
-	$(RUN_SETUP) $(VALGRIND) ./t_fortuna_make_oct > t_fortuna_make_oct.result
-endif
+	$(RUN_SETUP) $(VALGRIND) ./t_fortuna >t_fortuna.output
+	cmp t_fortuna.output $(srcdir)/t_fortuna.expected
 
 clean::
-	$(RM) t_fortuna$(EXEEXT) t_fortuna.$(OBJEXT)  t_fortuna_make_oct.result  t_fortuna_make_oct$(EXEEXT)  t_fortuna_make_oct.$(OBJEXT)
-
+	$(RM) t_fortuna t_fortuna.$(OBJEXT)
 
 clean-unix:: clean-libobjs
 
diff --git a/src/lib/crypto/krb/prng/fortuna/deps b/src/lib/crypto/krb/prng/fortuna/deps
index 1d420c571b..2518c95c31 100644
--- a/src/lib/crypto/krb/prng/fortuna/deps
+++ b/src/lib/crypto/krb/prng/fortuna/deps
@@ -1,45 +1,17 @@
 # 
 # Generated makefile dependencies follow.
 #
-prng_fortuna.so prng_fortuna.po $(OUTPRE)prng_fortuna.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \
-  $(BUILDTOP)/include/krb5/krb5.h $(BUILDTOP)/include/osconf.h \
-  $(BUILDTOP)/include/profile.h $(COM_ERR_DEPS) $(srcdir)/../../../builtin/aes/aes.h \
-  $(srcdir)/../prng.h \
-  $(srcdir)/../../../builtin/sha2/sha2.h \
-  $(top_srcdir)/include/k5-buf.h \
-  $(top_srcdir)/include/k5-err.h $(top_srcdir)/include/k5-gmt_mktime.h \
-  $(top_srcdir)/include/k5-int-pkinit.h $(top_srcdir)/include/k5-int.h \
-  $(top_srcdir)/include/k5-platform.h $(top_srcdir)/include/k5-plugin.h \
-  $(top_srcdir)/include/k5-thread.h $(top_srcdir)/include/k5-trace.h \
-  $(top_srcdir)/include/krb5.h $(top_srcdir)/include/krb5/authdata_plugin.h \
-  $(top_srcdir)/include/krb5/locate_plugin.h $(top_srcdir)/include/krb5/preauth_plugin.h \
-  $(top_srcdir)/include/port-sockets.h $(top_srcdir)/include/socket-utils.h \
-  prng_fortuna.c fortuna.h 
-entropy.so entropy.po $(OUTPRE)entropy.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \
-  $(BUILDTOP)/include/krb5/krb5.h $(BUILDTOP)/include/osconf.h \
-  $(BUILDTOP)/include/profile.h $(COM_ERR_DEPS)	\
-  $(top_srcdir)/include/k5-buf.h \
-  $(srcdir)/../prng.h \
-  $(top_srcdir)/include/k5-err.h $(top_srcdir)/include/k5-gmt_mktime.h \
-  $(top_srcdir)/include/k5-int-pkinit.h $(top_srcdir)/include/k5-int.h \
-  $(top_srcdir)/include/k5-platform.h $(top_srcdir)/include/k5-plugin.h \
-  $(top_srcdir)/include/k5-thread.h $(top_srcdir)/include/k5-trace.h \
-  $(top_srcdir)/include/krb5.h $(top_srcdir)/include/krb5/authdata_plugin.h \
-  $(top_srcdir)/include/krb5/locate_plugin.h $(top_srcdir)/include/krb5/preauth_plugin.h \
-  $(top_srcdir)/include/port-sockets.h $(top_srcdir)/include/socket-utils.h \
-  entropy.c
-t_fortuna.so t_fortuna.po $(OUTPRE)t_fortuna.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \
-  $(BUILDTOP)/include/krb5/krb5.h $(BUILDTOP)/include/osconf.h \
-  $(BUILDTOP)/include/profile.h $(COM_ERR_DEPS) $(srcdir)/../../../builtin/aes/aes.h \
-  $(srcdir)/../prng.h \
-  $(srcdir)/../../../builtin/sha2/sha2.h \
-  $(top_srcdir)/include/k5-buf.h \
-  $(top_srcdir)/include/k5-err.h $(top_srcdir)/include/k5-gmt_mktime.h \
-  $(top_srcdir)/include/k5-int-pkinit.h $(top_srcdir)/include/k5-int.h \
-  $(top_srcdir)/include/k5-platform.h $(top_srcdir)/include/k5-plugin.h \
-  $(top_srcdir)/include/k5-thread.h $(top_srcdir)/include/k5-trace.h \
-  $(top_srcdir)/include/krb5.h $(top_srcdir)/include/krb5/authdata_plugin.h \
-  $(top_srcdir)/include/krb5/locate_plugin.h $(top_srcdir)/include/krb5/preauth_plugin.h \
-  $(top_srcdir)/include/port-sockets.h $(top_srcdir)/include/socket-utils.h \
-  t_fortuna.c fortuna.h 
-
+prng_fortuna.so prng_fortuna.po $(OUTPRE)prng_fortuna.$(OBJEXT): \
+  $(BUILDTOP)/include/autoconf.h $(BUILDTOP)/include/krb5/krb5.h \
+  $(BUILDTOP)/include/osconf.h $(BUILDTOP)/include/profile.h \
+  $(COM_ERR_DEPS) $(srcdir)/../../../builtin/aes/aes.h \
+  $(srcdir)/../../../builtin/aes/uitypes.h $(srcdir)/../../../builtin/enc_provider/enc_provider.h \
+  $(srcdir)/../../../builtin/sha2/sha2.h $(srcdir)/../prng.h \
+  $(top_srcdir)/include/k5-buf.h $(top_srcdir)/include/k5-err.h \
+  $(top_srcdir)/include/k5-gmt_mktime.h $(top_srcdir)/include/k5-int-pkinit.h \
+  $(top_srcdir)/include/k5-int.h $(top_srcdir)/include/k5-platform.h \
+  $(top_srcdir)/include/k5-plugin.h $(top_srcdir)/include/k5-thread.h \
+  $(top_srcdir)/include/k5-trace.h $(top_srcdir)/include/krb5.h \
+  $(top_srcdir)/include/krb5/authdata_plugin.h $(top_srcdir)/include/krb5/plugin.h \
+  $(top_srcdir)/include/krb5/preauth_plugin.h $(top_srcdir)/include/port-sockets.h \
+  $(top_srcdir)/include/socket-utils.h prng_fortuna.c
diff --git a/src/lib/crypto/krb/prng/fortuna/entropy.c b/src/lib/crypto/krb/prng/fortuna/entropy.c
deleted file mode 100644
index b4dabdc3a6..0000000000
--- a/src/lib/crypto/krb/prng/fortuna/entropy.c
+++ /dev/null
@@ -1,112 +0,0 @@
-/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
-/*
- * lib/crypto/krb/prng/fortuna/entropy.c
- *
- * Copyright 2010 by the Massachusetts Institute of Technology.
- * All Rights Reserved.
- *
- * Export of this software from the United States of America may
- *   require a specific license from the United States Government.
- *   It is the responsibility of any person or organization contemplating
- *   export to obtain such a license before exporting.
- *
- * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
- * distribute this software and its documentation for any purpose and
- * without fee is hereby granted, provided that the above copyright
- * notice appear in all copies and that both that copyright notice and
- * this permission notice appear in supporting documentation, and that
- * the name of M.I.T. not be used in advertising or publicity pertaining
- * to distribution of the software without specific, written prior
- * permission.  Furthermore if you modify this software you must label
- * your software as modified software and not distribute it in such a
- * fashion that it might be confused with the original M.I.T. software.
- * M.I.T. makes no representations about the suitability of
- * this software for any purpose.  It is provided "as is" without express
- * or implied warranty.
- */
-
-/* various methods to collect entropy */
-
-#include "prng.h"
-
-#include "fortuna.h"
-#include "k5-int.h"
-
-#ifndef min
-#define min(a, b)       ((a) < (b) ? (a) : (b))
-#endif
-
-krb5_error_code
-k5_entropy_from_device(krb5_context context, const char *device, unsigned char* buf, int buflen)
-{
-    struct stat sb;
-    int fd;
-    unsigned char *bp;
-    size_t left;
-    fd = open(device, O_RDONLY);
-    if (fd == -1)
-        return 0;
-    set_cloexec_fd(fd);
-    if (fstat(fd, &sb) == -1 || S_ISREG(sb.st_mode)) {
-        close(fd);
-        return 0;
-    }
-
-    for (bp = buf, left = sizeof(buf); left > 0;) {
-        ssize_t count;
-        count = read(fd, bp, (unsigned) left);
-        if (count <= 0) {
-            close(fd);
-            return 0;
-        }
-        left -= count;
-        bp += count;
-    }
-    close(fd);
-    return 0;
-}
-
-krb5_error_code
-k5_entropy_dev_random(krb5_context context, unsigned char* buf, int buflen)
-{
-    memset(buf, 0, buflen);
-    return k5_entropy_from_device(context,"/dev/random", buf, buflen);
-}
-
-krb5_error_code
-k5_entropy_dev_urandom(krb5_context context, unsigned char* buf, int buflen)
-{
-    memset(buf, 0, buflen);
-    return k5_entropy_from_device(context,"/dev/urandom", buf, buflen);
-}
-
-krb5_error_code
-k5_entropy_pid(krb5_context context, unsigned char* buf, int buflen)
-{
-    pid_t pid = getpid(); 
-    int pidlen = min(buflen,(int)sizeof(&pid));
-    memset(buf, 0, buflen);
-    memcpy(buf, &pid, pidlen);
-    return 0;
-}
-
-krb5_error_code
-k5_entropy_uid(krb5_context context, unsigned char* buf, int buflen)
-{
-    pid_t uid = getuid(); 
-    int uidlen=min(buflen,(int)sizeof(&uid));
-    memset(buf, 0, buflen);
-    memcpy(buf, &uid, uidlen);
-    return 0;
-}
-
-#ifdef TEST_FORTUNA
-int
-test_entr(krb5_context context, unsigned char* buf, int buflen)
-{
-    char buf1[26] = "Seed To Test Fortuna PRNG";
-    memset(buf, 0, buflen);
-    memcpy(buf, buf1, min(buflen, 26));
-    return 0;
-}
-#endif
diff --git a/src/lib/crypto/krb/prng/fortuna/fortuna.h b/src/lib/crypto/krb/prng/fortuna/fortuna.h
deleted file mode 100644
index c98b858205..0000000000
--- a/src/lib/crypto/krb/prng/fortuna/fortuna.h
+++ /dev/null
@@ -1,62 +0,0 @@
-/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
-/*
- * lib/crypto/krb/prng/fortuna/fortuna.h
- *
- * Copyright 2010 by the Massachusetts Institute of Technology.
- * All Rights Reserved.
- *
- * Export of this software from the United States of America may
- *   require a specific license from the United States Government.
- *   It is the responsibility of any person or organization contemplating
- *   export to obtain such a license before exporting.
- *
- * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
- * distribute this software and its documentation for any purpose and
- * without fee is hereby granted, provided that the above copyright
- * notice appear in all copies and that both that copyright notice and
- * this permission notice appear in supporting documentation, and that
- * the name of M.I.T. not be used in advertising or publicity pertaining
- * to distribution of the software without specific, written prior
- * permission.  Furthermore if you modify this software you must label
- * your software as modified software and not distribute it in such a
- * fashion that it might be confused with the original M.I.T. software.
- * M.I.T. makes no representations about the suitability of
- * this software for any purpose.  It is provided "as is" without express
- * or implied warranty.
- */
-
-#ifndef FORTUNA_H
-#define FORTUNA_H
-
-#include "k5-int.h"
-#include "prng.h"
-#ifndef OPENSSL
-#include "aes.h"
-#endif
-#include "enc_provider.h"
-#include "sha2.h"
-#include "enc_provider.h"
-
-extern const struct krb5_prng_provider krb5int_prng_fortuna;
-
-/* various entropy collect functions */
-krb5_error_code
-k5_entropy_from_device(krb5_context context, const char *device, unsigned char* buf, int buflen);
-krb5_error_code
-k5_entropy_dev_random(krb5_context context, unsigned char* buf, int buflen);
-krb5_error_code
-k5_entropy_dev_urandom(krb5_context context, unsigned char* buf, int buflen);
-krb5_error_code
-k5_entropy_pid(krb5_context context, unsigned char* buf, int buflen);
-krb5_error_code
-k5_entropy_uid(krb5_context context, unsigned char* buf, int buflen);
-
-#ifdef TEST_FORTUNA
-int test_entr(krb5_context context, unsigned char* buf, int buflen);
-#endif
-
-#define FORTUNA_OK                1  /* All is well */
-#define FORTUNA_FAIL              0  /* generic failure */
-#define FORTUNA_LOCKING          -12
-
-#endif
diff --git a/src/lib/crypto/krb/prng/fortuna/prng_fortuna.c b/src/lib/crypto/krb/prng/fortuna/prng_fortuna.c
index 4bca844899..72eac2035b 100644
--- a/src/lib/crypto/krb/prng/fortuna/prng_fortuna.c
+++ b/src/lib/crypto/krb/prng/fortuna/prng_fortuna.c
@@ -1,10 +1,6 @@
 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
-/* prng_fortuna.c */
+/* lib/crypto/krb/prng/fortuna/prng_fortuna.c - Fortuna PRNG implementation */
 /*
- * prng_fortuna.c
- *
- *		Fortuna-like PRNG.
- *
  * Copyright (c) 2005 Marko Kreen
  * All rights reserved.
  *
@@ -12,15 +8,15 @@
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
- *	  notice, this list of conditions and the following disclaimer.
+ *        notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
- *	  notice, this list of conditions and the following disclaimer in the
- *	  documentation and/or other materials provided with the distribution.
+ *        notice, this list of conditions and the following disclaimer in the
+ *        documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.	IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * ARE DISCLAIMED.      IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
@@ -28,11 +24,9 @@
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
- *
- * $PostgreSQL: pgsql/contrib/pgcrypto/fortuna.c,v 1.8 2006/10/04 00:29:46 momjian Exp $
  */
 /*
- * Copyright (C) 2010 by the Massachusetts Institute of Technology.
+ * Copyright (C) 2010, 2011 by the Massachusetts Institute of Technology.
  * All rights reserved.
  *
  *
@@ -56,552 +50,393 @@
  *  or implied warranty.
  */
 
-#include "fortuna.h"
-#include "k5-int.h"
-
-
-#include "k5-thread.h"
-k5_mutex_t fortuna_lock = K5_MUTEX_PARTIAL_INITIALIZER;
-
-/*
- * Why Fortuna-like: There does not seem to be any definitive reference
- * on Fortuna in the net.  Instead this implementation is based on
- * following references:
- *
- * http://en.wikipedia.org/wiki/Fortuna_(PRNG)
- *	 - Wikipedia article
- * http://jlcooke.ca/random/
- *	 - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux.
- */
-
 /*
- * There is some confusion about whether and how to carry forward
- * the state of the pools.	Seems like original Fortuna does not
- * do it, resetting hash after each request.  I guess expecting
- * feeding to happen more often that requesting.   This is absolutely
- * unsuitable for pgcrypto, as nothing asynchronous happens here.
- *
- * J.L. Cooke fixed this by feeding previous hash to new re-initialized
- * hash context.
+ * This file implements the generator and accumulator parts of the Fortuna PRNG
+ * as described in chapter 9 of _Cryptography Engineering_ by Ferguson,
+ * Schneier, and Kohno.
  *
- * Fortuna predecessor Yarrow requires ability to query intermediate
- * 'final result' from hash, without affecting it.
+ * The generator, once seeded with an unguessable value, produces an unlimited
+ * number of pseudo-random outputs which cannot be used to determine the
+ * internal state of the generator (without an unreasonable amount of
+ * computational power).  The generator protects against the case where the OS
+ * random number generator is not cryptographically secure, but can produce an
+ * unguessable initial seed.  Successive reseeds of the generator will not make
+ * the internal state any more guessable than it was before.
  *
- * This implementation uses the Yarrow method - asking intermediate
- * results, but continuing with old state.
+ * The accumulator is layered on top of the generator, and seeks to eventually
+ * recover from the case where the OS random number generator did not produce
+ * an unguessable initial seed.  Unreliable entropy inputs are collected into
+ * 32 pools, which are used to reseed the generator when enough entropy has
+ * been collected.  Each pool collects twice as much entropy between reseeds as
+ * the previous one; eventually a reseed will occur involving a pool with
+ * enough entropy that an attacker cannot maintain knowledge of the generator's
+ * internal state.  The accumulator is only helpful for a long-running process
+ * such as a KDC which can submit periodic entropy inputs to the PRNG.
  */
 
-/*
- * Algorithm parameters
- */
-
-#define NUM_POOLS 	32
-
-/* in microseconds */
-#define RESEED_INTERVAL 100000	/* 0.1 sec */
-
-/* for one big request, reseed after this many bytes */
-#define RESEED_BYTES	(1024*1024)
-
-/*
- * Skip reseed if pool 0 has less than this many
- * bytes added since last reseed.
- */
-#define POOL0_FILL		(256/8)
-
-/* Entropy gathering */
-int (*entropy_collector[])(krb5_context context, unsigned char buf[], int buflen) =
-{
-#ifndef TEST_FORTUNA
- /*   k5_entropy_dev_random, */
-    k5_entropy_dev_urandom,
-    k5_entropy_pid,
-    k5_entropy_uid
-#else
-    test_entr
+#include "k5-int.h"
+#include "prng.h"
+#ifndef OPENSSL
+#include "aes.h"
 #endif
-};
+#include "enc_provider.h"
+#include "sha2.h"
+#include "enc_provider.h"
 
-/*
- * Algorithm constants
- */
+/* The accumulator's number of pools. */
+#define NUM_POOLS 32
+
+/* Minimum reseed interval in microseconds. */
+#define RESEED_INTERVAL 100000  /* 0.1 sec */
 
-#define AES_BLOCK_SIZE 16
-#define AES_MAXNR 14
+/* For one big request, change the key after this many bytes. */
+#define MAX_BYTES_PER_KEY (1 << 20)
 
-#define AES_ENCRYPT 1
-#define AES_DECRYPT 0
+/* Reseed if pool 0 has had this many bytes added since last reseed. */
+#define MIN_POOL_LEN 64
 
-/* Both cipher key size and hash result size */
-#define BLOCK			32
+/* AES-256 key size in bytes. */
+#define AES256_KEYSIZE (256/8)
 
-/* cipher block size */
-#define CIPH_BLOCK		16
+/* AES-256 block size in bytes. */
+#define AES256_BLOCKSIZE (128/8)
 
-/* for internal wrappers */
+/* SHA-256 block size in bytes. */
+#define SHA256_BLOCKSIZE (512/8)
 
-#define MD_CTX			SHA256_CTX
-#define CIPH_CTX		aes_ctx
+/* SHA-256 result size in bytes. */
+#define SHA256_HASHSIZE (256/8)
 
 /* Genarator - block cipher in CTR mode */
 struct fortuna_state
 {
-    unsigned char	counter[CIPH_BLOCK];
-    unsigned char	result[CIPH_BLOCK];
-    unsigned char	key[BLOCK];
-    MD_CTX		pool[NUM_POOLS];
-    CIPH_CTX		ciph;
-    unsigned		reseed_count;
-    struct timeval	last_reseed_time;
-    unsigned		pool0_bytes;
-    unsigned		rnd_pos;
-    int			tricks_done;
-    pid_t		pid;
+    /* Generator state. */
+    unsigned char counter[AES256_BLOCKSIZE];
+    unsigned char key[AES256_KEYSIZE];
+    aes_ctx ciph;
+
+    /* Accumulator state. */
+    SHA256_CTX pool[NUM_POOLS];
+    unsigned int pool_index;
+    unsigned int reseed_count;
+    struct timeval last_reseed_time;
+    unsigned int pool0_bytes;
+
+    /* Current pid as of last request, for fork safety. */
+    pid_t pid;
 };
-typedef struct fortuna_state FState;
-
 
 /*
- * Use our own wrappers here.
- * - Need to get intermediate result from digest, without affecting it.
- * - Need re-set key on a cipher context.
- * - Algorithms are guaranteed to exist.
- * - No memory allocations.
+ * SHA[d]-256(m) is defined as SHA-256(SHA-256(0^512||m))--that is, hash a
+ * block full of zeros followed by the input data, then re-hash the result.
+ * These functions implement the SHA[d]-256 function on incremental inputs.
  */
 
 static void
-ciph_init(CIPH_CTX * ctx /*out*/, const unsigned char *key, int klen)
+shad256_init(SHA256_CTX *ctx)
 {
-    krb5int_aes_enc_key(key, klen, ctx);
+    unsigned char zero[SHA256_BLOCKSIZE];
+
+    /* Initialize the inner SHA-256 context and update it with a zero block. */
+    memset(zero, 0, sizeof(zero));
+    sha2Init(ctx);
+    sha2Update(ctx, zero, sizeof(zero));
 }
 
 static void
-ciph_encrypt(CIPH_CTX *ctx, const unsigned char *in, unsigned char *out)
+shad256_update(SHA256_CTX *ctx, const unsigned char *data, int len)
 {
-    aes_enc_blk(in, out, ctx);
+    /* Feed the input to the inner SHA-256 context. */
+    sha2Update(ctx, data, len);
 }
 
 static void
-md_init(MD_CTX * ctx)
+shad256_result(SHA256_CTX *ctx, unsigned char *dst)
 {
+    /* Finalize the inner context, then feed the result back through SHA256. */
+    sha2Final(dst, ctx);
     sha2Init(ctx);
+    sha2Update(ctx, dst, SHA256_HASHSIZE);
+    sha2Final(dst, ctx);
 }
 
+/* Initialize state. */
 static void
-md_update(MD_CTX * ctx, const unsigned char *data, int len)
+init_state(struct fortuna_state *st)
 {
-    sha2Update(ctx, data, len);
+    unsigned int i;
+
+    memset(st, 0, sizeof(*st));
+    for (i = 0; i < NUM_POOLS; i++)
+        shad256_init(&st->pool[i]);
 }
 
+/* Increment st->counter using least significant byte first. */
 static void
-md_result(MD_CTX * ctx, unsigned char *dst)
+inc_counter(struct fortuna_state *st)
 {
-    MD_CTX	tmp_ctx;
+    UINT64_TYPE val;
 
-    memcpy(&tmp_ctx, ctx, sizeof(*ctx));
-    sha2Final(dst, &tmp_ctx);
-    memset(&tmp_ctx, 0, sizeof(tmp_ctx));
+    val = load_64_le(st->counter) + 1;
+    store_64_le(val, st->counter);
+    if (val == 0) {
+        val = load_64_le(st->counter + 8) + 1;
+        store_64_le(val, st->counter + 8);
+    }
 }
 
-/*
- * initialize state
- */
-static  krb5_error_code
-init_state(FState * st)
+/* Encrypt and increment st->counter in the current cipher context. */
+static void
+encrypt_counter(struct fortuna_state *st, unsigned char *dst)
 {
-    int	i;
-    krb5_error_code ret = 0;
-
-    ret = k5_mutex_finish_init(&fortuna_lock);
-    if (ret)
-        return ret;
-
-    memset(st, 0, sizeof(*st));
-    for (i = 0; i < NUM_POOLS; i++)
-	md_init(&st->pool[i]);
-    st->pid = getpid();
-
-    return 0;
+    aes_enc_blk(st->counter, dst, &st->ciph);
+    inc_counter(st);
 }
 
-/*
- * Endianess does not matter.
- * It just needs to change without repeating.
- */
+/* Reseed the generator based on hopefully non-guessable input. */
 static void
-inc_counter(FState * st)
+generator_reseed(struct fortuna_state *st, const unsigned char *data,
+                 size_t len)
 {
-    uint32_t   *val = (uint32_t *) st->counter;
-
-    if (++val[0])
-	return;
-    if (++val[1])
-	return;
-    if (++val[2])
-	return;
-    ++val[3];
+    SHA256_CTX ctx;
+
+    /* Calculate SHA[d]-256(key||s) and make that the new key.  Depend on the
+     * SHA-256 hash size being the AES-256 key size. */
+    shad256_init(&ctx);
+    shad256_update(&ctx, st->key, AES256_KEYSIZE);
+    shad256_update(&ctx, data, len);
+    shad256_result(&ctx, st->key);
+    zap(&ctx, sizeof(ctx));
+    krb5int_aes_enc_key(st->key, AES256_KEYSIZE, &st->ciph);
+
+    /* Increment counter. */
+    inc_counter(st);
 }
 
-/*
- * This is called 'cipher in counter mode'.
- */
+/* Generate two blocks in counter mode and replace the key with the result. */
 static void
-encrypt_counter(FState * st, unsigned char *dst)
+change_key(struct fortuna_state *st)
 {
-    ciph_encrypt(&st->ciph, st->counter, dst);
-    inc_counter(st);
+    encrypt_counter(st, st->key);
+    encrypt_counter(st, st->key + AES256_BLOCKSIZE);
+    krb5int_aes_enc_key(st->key, AES256_KEYSIZE, &st->ciph);
 }
 
-
-/*
- * The time between reseed must be at least RESEED_INTERVAL microseconds.
- */
-static int
-enough_time_passed(FState * st)
+/* Output pseudo-random data from the generator. */
+static void
+generator_output(struct fortuna_state *st, unsigned char *dst, size_t len)
 {
-    int    ok = FORTUNA_FAIL;
-    struct timeval tv;
-    struct timeval *last = &st->last_reseed_time;
-
-    gettimeofday(&tv, NULL);
-
-    /* check how much time has passed */
-    if (tv.tv_sec > last->tv_sec + 1)
-	ok = FORTUNA_OK;
-    else if (tv.tv_sec == last->tv_sec + 1) {
-	if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
-	    ok = FORTUNA_OK;
-    } else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
-	ok = FORTUNA_OK;
-
-    /* reseed will happen, update last_reseed_time */
-    if (ok)
-	memcpy(last, &tv, sizeof(tv));
-
-    memset(&tv, 0, sizeof(tv));
+    unsigned char result[AES256_BLOCKSIZE];
+    size_t n, count = 0;
+
+    while (len > 0) {
+        /* Produce bytes and copy the result into dst. */
+        encrypt_counter(st, result);
+        n = (len < AES256_BLOCKSIZE) ? len : AES256_BLOCKSIZE;
+        memcpy(dst, result, n);
+        dst += n;
+        len -= n;
+
+        /* Each time we reach MAX_BYTES_PER_KEY bytes, change the key. */
+        count += AES256_BLOCKSIZE;
+        if (count >= MAX_BYTES_PER_KEY) {
+            change_key(st);
+            count = 0;
+        }
+    }
+    zap(result, sizeof(result));
 
-    return ok;
+    /* Change the key after each request. */
+    change_key(st);
 }
 
-/*
- * generate new key from all the pools
- */
+/* Reseed the generator using the accumulator pools. */
 static void
-reseed(FState * st)
+accumulator_reseed(struct fortuna_state *st)
 {
-    unsigned	k;
-    unsigned	n;
-    MD_CTX		key_md;
-    unsigned char	buf[BLOCK];
-
-    /* set pool as empty */
-    st->pool0_bytes = 0;
+    unsigned int i, n;
+    SHA256_CTX ctx;
+    unsigned char hash_result[SHA256_HASHSIZE];
 
-    /*
-     * Both #0 and #1 reseed would use only pool 0. Just skip #0 then.
-     */
     n = ++st->reseed_count;
 
     /*
-     * The goal: use k-th pool only 1/(2^k) of the time.
+     * Collect entropy from pools.  We use the i-th pool only 1/(2^i) of the
+     * time so that each pool collects twice as much entropy between uses as
+     * the last.
      */
-    md_init(&key_md);
-    for (k = 0; k < NUM_POOLS; k++) {
-	md_result(&st->pool[k], buf);
-	md_update(&key_md, buf, BLOCK);
-
-	if (n & 1 || !n)
-	    break;
-	n >>= 1;
+    shad256_init(&ctx);
+    for (i = 0; i < NUM_POOLS; i++) {
+        if (n % (1 << i) != 0)
+            break;
+
+        /* Harvest this pool's hash result into ctx, then reset the pool. */
+        shad256_result(&st->pool[i], hash_result);
+        shad256_init(&st->pool[i]);
+        shad256_update(&ctx, hash_result, SHA256_HASHSIZE);
     }
-    /* add old key into mix too */
-    md_update(&key_md, st->key, BLOCK);
-
-#ifndef TEST_FORTUNA
-    /* add pid to make output diverse after fork() */
-    md_update(&key_md, (const unsigned char *)&st->pid, sizeof(st->pid));
-#endif
-
-    /* now we have new key */
-    md_result(&key_md, st->key);
-    /* use new key */
-    ciph_init(&st->ciph, st->key, BLOCK);
+    shad256_result(&ctx, hash_result);
+    generator_reseed(st, hash_result, SHA256_HASHSIZE);
+    zap(hash_result, SHA256_HASHSIZE);
+    zap(&ctx, sizeof(ctx));
 
-    memset(&key_md, 0, sizeof(key_md));
-    memset(buf, 0, BLOCK);
-}
-
-/*
- * Pick a random pool.	This uses key bytes as random source.
- */
-static unsigned
-get_rand_pool(FState * st)
-{
-    unsigned	rnd;
-
-    /*
-     * This slightly prefers lower pools - thats OK.
-     */
-    rnd = st->key[st->rnd_pos] % NUM_POOLS;
-
-    st->rnd_pos++;
-    if (st->rnd_pos >= BLOCK)
-	st->rnd_pos = 0;
-
-    return rnd;
+    /* Reset the count of bytes added to pool 0. */
+    st->pool0_bytes = 0;
 }
 
-/*
- * update pools
- */
+/* Add possibly unguessable data to the next accumulator pool. */
 static void
-add_entropy(FState * st, const unsigned char data[], unsigned len)
+accumulator_add_event(struct fortuna_state *st, const unsigned char *data,
+                      size_t len)
 {
-    unsigned		pos;
-    unsigned char	hash[BLOCK];
-    MD_CTX		md;
+    unsigned char lenbuf[2];
+    SHA256_CTX *pool;
+
+    /* Track how many bytes have been added to pool 0. */
+    if (st->pool_index == 0 && st->pool0_bytes < MIN_POOL_LEN)
+        st->pool0_bytes += len;
 
-    /* hash given data */
-    md_init(&md);
-    md_update(&md, data, len);
-    md_result(&md, hash);
+    /* Hash events into successive accumulator pools. */
+    pool = &st->pool[st->pool_index];
+    st->pool_index = (st->pool_index + 1) % NUM_POOLS;
 
     /*
-     * Make sure the pool 0 is initialized, then update randomly.
+     * Fortuna specifies that events are encoded with a source identifier byte,
+     * a length byte, and the event data itself.  We do not have source
+     * identifiers and they're not really important, so just encode the
+     * length in two bytes instead.
      */
-    if (st->reseed_count == 0)
-	pos = 0;
-    else
-	pos = get_rand_pool(st);
-    md_update(&st->pool[pos], hash, BLOCK);
-
-    if (pos == 0)
-	st->pool0_bytes += len;
-
-    memset(hash, 0, BLOCK);
-    memset(&md, 0, sizeof(md));
+    store_16_be(len, lenbuf);
+    shad256_update(pool, lenbuf, 2);
+    shad256_update(pool, data, len);
 }
 
-/*
- * Just take 2 next blocks as new key
- */
-static void
-rekey(FState * st)
-{
-    encrypt_counter(st, st->key);
-    encrypt_counter(st, st->key + CIPH_BLOCK);
-    ciph_init(&st->ciph, st->key, BLOCK);
-}
+/* Limit dependencies for test program. */
+#ifndef TEST
 
-/*
- * Hide public constants. (counter, pools > 0)
- *
- * This can also be viewed as spreading the startup
- * entropy over all of the components.
- */
-static void
-startup_tricks(FState * st)
+/* Return true if RESEED_INTERVAL microseconds have passed since the last
+ * reseed. */
+static krb5_boolean
+enough_time_passed(struct fortuna_state *st)
 {
-    int			i;
-    unsigned char	buf[BLOCK];
+    struct timeval tv, *last = &st->last_reseed_time;
+    krb5_boolean ok = FALSE;
 
-    /* Use next block as counter. */
-    encrypt_counter(st, st->counter);
+    gettimeofday(&tv, NULL);
 
-    /* Now shuffle pools, excluding #0 */
-    for (i = 1; i < NUM_POOLS; i++) {
-	encrypt_counter(st, buf);
-	encrypt_counter(st, buf + CIPH_BLOCK);
-	md_update(&st->pool[i], buf, BLOCK);
-    }
-    memset(buf, 0, BLOCK);
+    /* Check how much time has passed. */
+    if (tv.tv_sec > last->tv_sec + 1)
+        ok = TRUE;
+    else if (tv.tv_sec == last->tv_sec + 1) {
+        if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
+            ok = TRUE;
+    } else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
+        ok = TRUE;
 
-    /* Hide the key. */
-    rekey(st);
+    /* Update last_reseed_time if we're returning success. */
+    if (ok)
+        memcpy(last, &tv, sizeof(tv));
 
-    /* This can be done only once. */
-    st->tricks_done = 1;
+    return ok;
 }
 
 static void
-extract_data(FState * st, unsigned count, unsigned char *dst)
+accumulator_output(struct fortuna_state *st, unsigned char *dst, size_t len)
 {
-    unsigned	n;
-    unsigned	block_nr = 0;
-    pid_t	pid = getpid();
-
-    /* Should we reseed? */
-    if (st->pool0_bytes >= POOL0_FILL || st->reseed_count == 0)
-	if (enough_time_passed(st))
-	    reseed(st);
-
-    /* Do some randomization on first call */
-    if (!st->tricks_done)
-	startup_tricks(st);
-
-    /* If we forked, force a reseed again */
-    if (pid != st->pid) {
-	st->pid = pid;
-	reseed(st);
-    }
-    while (count > 0) {
-	/* produce bytes */
-	encrypt_counter(st, st->result);
-
-	/* copy result */
-	if (count > CIPH_BLOCK)
-	    n = CIPH_BLOCK;
-	else
-	    n = count;
-	memcpy(dst, st->result, n);
-	dst += n;
-	count -= n;
-
-	/* must not give out too many bytes with one key */
-	block_nr++;
-	if (block_nr > (RESEED_BYTES / CIPH_BLOCK)) {
-	    rekey(st);
-	    block_nr = 0;
-	}
-    }
-    /* Set new key for next request. */
-    rekey(st);
-}
+    /* Reseed the generator with data from pools if we have accumulated enough
+     * data and enough time has passed since the last accumulator reseed. */
+    if (st->pool0_bytes >= MIN_POOL_LEN && enough_time_passed(st))
+        accumulator_reseed(st);
 
-/*
- * public interface
- */
-
-static FState	main_state;
-static int	init_done;
-static int	have_entropy;
-static int      resend_bytes;
-
-#define FORTUNA_RESEED_BYTE	10000
-
-/*
- * Try our best to do an inital seed
- */
-#define INIT_BYTES	128
-
-static int
-fortuna_reseed(void)
-{
-    int entropy_p = 0;
-    krb5_context ctx;
-    unsigned char buf[ENTROPY_BUFSIZE];
-    int num = sizeof(entropy_collector)/sizeof(entropy_collector[0]);
-
-    if (!init_done)
-	abort();
-    
-    while(num > 0){
-        entropy_collector[num-1](ctx, buf, ENTROPY_BUFSIZE);
-        add_entropy(&main_state, buf, sizeof(buf));
-        num--;
-    }
-    memset (buf,0,ENTROPY_BUFSIZE);
-    entropy_p = 1; 
-
-    return entropy_p;
+    generator_output(st, dst, len);
 }
 
-static int
-fortuna_init(void)
-{
-    krb5_error_code ret = 0;
-
-    if (!init_done) {
-        ret = init_state(&main_state);
-        if (ret == 0)
-            init_done = 1;
-    }
-    if (!have_entropy)
-	have_entropy = fortuna_reseed();
-    return (init_done && have_entropy);
-}
-
-static  krb5_error_code
-fortuna_seed(const unsigned char *indata, int size)
-{
-    krb5_error_code ret = 0;
-
-    fortuna_init();
-
-    ret = k5_mutex_lock(&fortuna_lock);
-    if (ret)
-        return FORTUNA_LOCKING;
-
-    add_entropy(&main_state, indata, size);
-    if (size >= INIT_BYTES)
-	have_entropy = 1;
-
-    k5_mutex_unlock(&fortuna_lock);
-
-    return FORTUNA_OK;
-}
+static k5_mutex_t fortuna_lock = K5_MUTEX_PARTIAL_INITIALIZER;
+static struct fortuna_state main_state;
+static pid_t last_pid;
+static krb5_boolean have_entropy = FALSE;
 
 static int
-fortuna_bytes(unsigned char *outdata, int size)
+fortuna_init(void)
 {
     krb5_error_code ret = 0;
+    unsigned char osbuf[64];
 
-    if (!fortuna_init()){
-	return FORTUNA_FAIL;
-    }
-
-    ret = k5_mutex_lock(&fortuna_lock);
+    ret = k5_mutex_finish_init(&fortuna_lock);
     if (ret)
-        return FORTUNA_LOCKING;
+        return ret;
 
-    resend_bytes += size;
-    if (resend_bytes > FORTUNA_RESEED_BYTE || resend_bytes < size) {
-	resend_bytes = 0;
-	fortuna_reseed();
+    init_state(&main_state);
+    last_pid = getpid();
+    if (k5_get_os_entropy(osbuf, sizeof(osbuf))) {
+        generator_reseed(&main_state, osbuf, sizeof(osbuf));
+        have_entropy = TRUE;
     }
-    extract_data(&main_state, size, outdata);
 
-    k5_mutex_unlock(&fortuna_lock);
-
-    return FORTUNA_OK;
+    return 0;
 }
 
 static void
 fortuna_cleanup(void)
 {
-    krb5_error_code ret = 0;
-
-    ret = k5_mutex_lock(&fortuna_lock);
-
-    init_done = 0;
-    have_entropy = 0;
-    memset(&main_state, 0, sizeof(main_state));
-
-    if (!ret)
-        k5_mutex_unlock(&fortuna_lock);
-
+    have_entropy = FALSE;
+    zap(&main_state, sizeof(main_state));
     k5_mutex_destroy(&fortuna_lock);
-
 }
 
 static krb5_error_code
 fortuna_add_entropy(krb5_context context, unsigned int randsource,
-                          const krb5_data *indata)
+                    const krb5_data *indata)
 {
-    krb5_error_code ret = 0;
-    ret = fortuna_seed((const unsigned char *)indata->data, indata->length);
-    if (ret != FORTUNA_OK)
-        return KRB5_CRYPTO_INTERNAL;
+    krb5_error_code ret;
+
+    ret = krb5int_crypto_init();
+    if (ret)
+        return ret;
+    ret = k5_mutex_lock(&fortuna_lock);
+    if (ret)
+        return ret;
+    if (randsource == KRB5_C_RANDSOURCE_OSRAND ||
+        randsource == KRB5_C_RANDSOURCE_TRUSTEDPARTY) {
+        /* These sources contain enough entropy that we should use them
+         * immediately, so that they benefit the next request. */
+        generator_reseed(&main_state, (unsigned char *)indata->data,
+                         indata->length);
+        have_entropy = TRUE;
+    } else {
+        /* Other sources should just go into the pools and be used according to
+         * the accumulator logic. */
+        accumulator_add_event(&main_state, (unsigned char *)indata->data,
+                              indata->length);
+    }
+    k5_mutex_unlock(&fortuna_lock);
     return 0;
 }
 
 static krb5_error_code
 fortuna_make_octets(krb5_context context, krb5_data *outdata)
 {
-    krb5_error_code ret = 0;
-    ret = fortuna_bytes((unsigned char *)outdata->data, outdata->length);
-    if (ret != FORTUNA_OK)
+    krb5_error_code ret;
+    pid_t pid = getpid();
+    unsigned char pidbuf[4];
+
+    ret = k5_mutex_lock(&fortuna_lock);
+    if (ret)
+        return ret;
+
+    if (!have_entropy)
         return KRB5_CRYPTO_INTERNAL;
+
+    if (pid != last_pid) {
+        /* We forked; make sure child's PRNG stream differs from parent's. */
+        store_32_be(pid, pidbuf);
+        generator_reseed(&main_state, pidbuf, 4);
+        last_pid = pid;
+    }
+
+    accumulator_output(&main_state, (unsigned char *)outdata->data,
+                       outdata->length);
+    k5_mutex_unlock(&fortuna_lock);
     return 0;
 }
 
@@ -613,3 +448,4 @@ const struct krb5_prng_provider krb5int_prng_fortuna = {
     fortuna_cleanup
 };
 
+#endif /* not TEST */
diff --git a/src/lib/crypto/krb/prng/fortuna/t_fortuna.c b/src/lib/crypto/krb/prng/fortuna/t_fortuna.c
index 3365f66933..bd0002566f 100644
--- a/src/lib/crypto/krb/prng/fortuna/t_fortuna.c
+++ b/src/lib/crypto/krb/prng/fortuna/t_fortuna.c
@@ -1,3 +1,5 @@
+/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+/* lib/crypto/krb/prng/fortuna/t_fortuna.c - Fortuna test program */
 /*
  * Copyright (c) 2007 Kungliga Tekniska Högskolan
  * (Royal Institute of Technology, Stockholm, Sweden).
@@ -30,34 +32,64 @@
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
+/*
+ * Copyright (C) 2011 by the Massachusetts Institute of Technology.
+ * All rights reserved.
+ *
+ * Export of this software from the United States of America may
+ *   require a specific license from the United States Government.
+ *   It is the responsibility of any person or organization contemplating
+ *   export to obtain such a license before exporting.
+ *
+ * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
+ * distribute this software and its documentation for any purpose and
+ * without fee is hereby granted, provided that the above copyright
+ * notice appear in all copies and that both that copyright notice and
+ * this permission notice appear in supporting documentation, and that
+ * the name of M.I.T. not be used in advertising or publicity pertaining
+ * to distribution of the software without specific, written prior
+ * permission.  Furthermore if you modify this software you must label
+ * your software as modified software and not distribute it in such a
+ * fashion that it might be confused with the original M.I.T. software.
+ * M.I.T. makes no representations about the suitability of
+ * this software for any purpose.  It is provided "as is" without express
+ * or implied warranty.
+ */
 
-#include "prng.h"
-#include "fortuna.h"
-#include <k5-int.h>
+/* Include most of prng_fortuna.c so we can test the PRNG internals. */
+#define TEST
+#include "prng_fortuna.c"
 
+static void
+display(const unsigned char *data, size_t len)
+{
+    size_t i;
 
-#define LEN_TEST_BUF 1024 * 1024
-static int len = LEN_TEST_BUF;
+    for (i = 0; i < len; i++)
+        printf("%02X", data[i]);
+    printf("\n");
+}
 
-int
-main(int argc, char **argv)
+/*
+ * Generate data from st with its current internal state and check for
+ * significant bias in each bit of the resulting bytes.  This test would have a
+ * small chance of failure on random inputs, but we have a predictable state
+ * after all the other tests have been run, so it will never fail if the PRNG
+ * operates the way we expect.
+ */
+static void
+head_tail_test(struct fortuna_state *st)
 {
-    char buffer[LEN_TEST_BUF];
-    krb5_data data = {0, LEN_TEST_BUF, (char*)buffer};
-    int bit, i;
+    unsigned char buffer[1024 * 1024], c;
+    size_t i, len = sizeof(buffer);
+    int bit, bits[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
     double res;
-    int bits[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
-
-    if (len < 100000) 
-        return 0;
 
-    for (i = 0; i < LEN_TEST_BUF; i++)
-         buffer[i] = 0;
+    memset(buffer, 0, len);
 
-    /* head vs tail */
-    krb5_c_random_make_octets(NULL, &data);
+    generator_output(st, buffer, len);
     for (i = 0; i < len; i++) {
-        unsigned char c = ((unsigned char *)buffer)[i];
+        c = buffer[i];
         for (bit = 0; bit < 8 && c; bit++) {
             if (c & 1)
                 bits[bit]++;
@@ -66,16 +98,68 @@ main(int argc, char **argv)
     }
     
     for (bit = 0; bit < 8; bit++) {
-
         res = ((double)abs(len - bits[bit] * 2)) / (double)len;
         if (res > 0.005){
-            printf("head %d vs tail %d > 0.5%%%% %lf == %d vs %d\n",
-                 bit, bit, res, len, bits[bit]);
-            return 1;
+            fprintf(stderr,
+                    "Bit %d: %d zero, %d one exceeds 0.5%% variance (%lf)\n",
+                    bit, (int)len - bits[bit], bits[bit], res);
+            exit(1);
         }
+    }
+}
+
+int
+main(int argc, char **argv)
+{
+    struct fortuna_state test_state;
+    struct fortuna_state *st = &test_state;
+    unsigned char buf[2 * 1024 * 1024];
+    unsigned int i;
+
+    /* Seed the generator with a known state. */
+    init_state(&test_state);
+    generator_reseed(st, (unsigned char *)"test", 4);
+
+    /* Generate two pieces of output; key should change for each request. */
+    generator_output(st, buf, 32);
+    display(buf, 32);
+    generator_output(st, buf, 32);
+    display(buf, 32);
 
-        printf("head vs tails bit %d is %lf\n", bit, res);
+    /* Generate a lot of output to test key changes during request. */
+    generator_output(st, buf, sizeof(buf));
+    display(buf, 32);
+    display(buf + sizeof(buf) - 32, 32);
+
+    /* Reseed the generator and generate more output. */
+    generator_reseed(st, (unsigned char *)"retest", 6);
+    generator_output(st, buf, 32);
+    display(buf, 32);
+
+    /* Add sample data to accumulator pools. */
+    for (i = 0; i < 44; i++) {
+        store_32_be(i, buf);
+        accumulator_add_event(st, buf, 4);
     }
+    assert(st->pool_index == 12);
+    assert(st->pool0_bytes == 8);
+
+    /* Exercise accumulator reseeds. */
+    accumulator_reseed(st);
+    generator_output(st, buf, 32);
+    display(buf, 32);
+    accumulator_reseed(st);
+    generator_output(st, buf, 32);
+    display(buf, 32);
+    accumulator_reseed(st);
+    generator_output(st, buf, 32);
+    display(buf, 32);
+    for (i = 0; i < 1000; i++)
+        accumulator_reseed(st);
+    assert(st->reseed_count == 1003);
+    generator_output(st, buf, 32);
+    display(buf, 32);
 
+    head_tail_test(st);
     return 0;
 }
diff --git a/src/lib/crypto/krb/prng/fortuna/t_fortuna.expected b/src/lib/crypto/krb/prng/fortuna/t_fortuna.expected
new file mode 100644
index 0000000000..2d5738c15f
--- /dev/null
+++ b/src/lib/crypto/krb/prng/fortuna/t_fortuna.expected
@@ -0,0 +1,9 @@
+A7C846B4EEAF6AB78AB33FFC77197BB0364C364E5A4259593464162B14C494F1
+EDC0776CA17E4FC395823653D1956D6873A55A1829D85D8B46340F3C9DD113F2
+B551F4EDF860BEB49E89BFF9B60BFD955ED85B070E18667189450962C503CBE5
+069A4F41D88CC12927672F1039C50DD50A0713E0AD542A6CDCD1E75CC4E7FB36
+E4EBA939FB027DACF1E7406461703C57B48D8BC0A1039A170FAD5E35C088B789
+68199B6755105BC22C343BD339EA2035E7A3F9535DC83DE3436C794EABA18B34
+49AD3C22E015666A269F37CA47EEF075860CC21588F3CF8D7EB5A9DC4D59C0F4
+9EFCB204F1B588A918B6A81D1E0E25C78C0921CF4839BE38D698EE8E30097BED
+66B252E879C2548A3FC3FEAF6B7ABCDBAFB1A45F5FB68EB49AB12CC13B1A091B
diff --git a/src/lib/crypto/krb/prng/fortuna/t_fortuna_make_oct.c b/src/lib/crypto/krb/prng/fortuna/t_fortuna_make_oct.c
deleted file mode 100644
index 42a5be2098..0000000000
--- a/src/lib/crypto/krb/prng/fortuna/t_fortuna_make_oct.c
+++ /dev/null
@@ -1,85 +0,0 @@
-/*
- * Copyright (c) 2007 Kungliga Tekniska Högskolan
- * (Royal Institute of Technology, Stockholm, Sweden).
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * 3. Neither the name of the Institute nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#include "prng.h"
-#include "fortuna.h"
-#include <k5-int.h>
-
-#define LEN_TEST_BUF 1024
-static int len = LEN_TEST_BUF;
-
-static void hex_print( FILE* f, const char* var, void* data, size_t size );
-
-int
-main(int argc, char **argv)
-{
-    char buffer[LEN_TEST_BUF];
-    krb5_data data = {0, LEN_TEST_BUF, (char*)buffer};
-    int i;
-
-    for (i = 0; i < LEN_TEST_BUF; i++)
-         buffer[i] = 0;
-
-    krb5_c_random_make_octets(NULL, &data);
-
-    hex_print( stdout, "random1", data.data, data.length );
-
-    /* To target FORTUNA_RESEED_BYTE */
-    i = 0;
-    while (i++ < 11){
-        krb5_c_random_make_octets(NULL, &data);
-    }
-
-    hex_print( stdout, "random2", data.data, data.length );
-
-    return 0;
-}
-static void
-hex_print( FILE* f, const char* var, void* data, size_t size )
-{
-    const char* conv = "0123456789abcdef";
-    size_t i;
-    char* p = (char*) data;
-    char c, d;
-
-    fprintf( f, var );
-    fprintf( f, " = " );
-    for ( i = 0; i < size; i++ )
-    {
-        c = conv[ (p[ i ] >> 4) & 0xf ];
-        d = conv[ p[ i ] & 0xf ];
-        fprintf( f, "%c%c", c, d );
-    }
-    fprintf( f, "\n" );
-}
-
diff --git a/src/lib/crypto/krb/prng/fortuna/t_fortuna_make_oct.expected b/src/lib/crypto/krb/prng/fortuna/t_fortuna_make_oct.expected
deleted file mode 100644
index 89789a67b4..0000000000
--- a/src/lib/crypto/krb/prng/fortuna/t_fortuna_make_oct.expected
+++ /dev/null
@@ -1,2 +0,0 @@
-random1 = c27d031fce09ad26525e107021c1038062c9e05672065bce1139a9ae583d9cd70319e9a68d1f4da2cf24099af05ab1a910c781035864ab7e45337199cfa7ece05111d3604215feac555e847148dcf47fa8361746ce162201edbb83f4f753ad9933f9c618f86e15ff28eecdddbcaacd2ff212c236141b2edc5e5b91f2a95f89af5070eed9652f2857963801cff9f21d6a08f8c1480270009ebde555a00dcc60b0688cba89950aeeac8a0806922ea1baae494e1bc1be7920fa6c9b980a80f374a5ea53f3e10ffeef047bea388949fc0b66252d25c8775dd01a03a27528a4c801993129e581e3c4d77ecca9efaf27047d7eec025f6f0601d469a93f5be5cbac10b773a392a3d0a167ec76637014974fe6808e88b9b8fbd51dfbad7192d1edad971b11404f96849cc88dab07b21ff14d5d528d60c3bb7ad4b1ddc3e6b082df9d89b020d276db81676ffcf6521b2bab33c404b27f15f5547ee4a37654680fb331afb256a6cd83146a5baf70a6a5a455c7ead49493f7aa85d4afde951f33f44a99c49ea1e3f568b70735c46dce20460150d2c96aa0849cd5b7062253fdb11ba4a7e046fe24ccd3c87bbebe3351c10a8b6fb4b1e2dd46803782982970cf9805fa2a8540d9f910ea4e360a342a320cce34101472fdc258ba339038e464da6bc20b79df5fc6ae27762a7315d3b342d99eca5d23c5ce2f1ba800bdb68882a6b520e31037e8c1e1ea3444334ed6ec3913994344b714009b9cc816d57d5a74e1cbfe3f038f0def48f43ef81983a872068f60e808ed75997d23e4896faba5542738bd403b3d5fc33f64d606d376e936f89a60cf0ad417ba0f9cd4bb70287437e9f7d63572432d859473dadd9b8c51a8813e3e734968288afdb22a5779c1f6ccc681cf2332f634096f4d40088bdee97270a7d7c04d7b367001b7c154da3f69734fd91590710e54af97f4e03b80c800ccef3282b519aaa4a76f9cb06d6746211be6ca8ac910b3b0bb799ae185dbc92c8ac2d91f0c6e5bc7095e41ebd2b3217648ba62616a3820f282154ab2787f26c47c47bb099810b65e862ed44b9d47ac87d693d2f87295834274310f337b15a4d7b33d91ffefa7b3dfec270327db4b46a5e0e1cdc072e5d0a2e8392a2bede194ee715070785f1d1cb6a5bcd2f13b4aa644541b9e6336bbb87d88bead71858dfc4c211589865faf08c8cc9ba47728dc8d2ebc3fb6d9c434b8ad7f99fbc14124fb5ffaa24fb0c7650bb19e5e17379fb58579d3b41a007e3783f68cf523a9b1fbbbab2e40c9aa8049f4e2a609c4adc528b904792121e139bbf340980adc38ac32f9538790cad55351b46faae28a0c8d5a995d55e254694102901556c9ce648da6803c6480d5ad0e567ace44d88f5d45cc02e55f81b011d2c2188cd6e89aa6a7cffed6a14a8dbb592e4f386b5a7204d6a0d56cb0844c8df76f7697
-random2 = 9d87e8e1b4b74803357d0cc36ca668584c2bba571cb38f66fba3a2d03f897fcf392fd2f88184d330ca03e85b7c4531269849864ee6bc61d81501b7a5796377a73aa6c594b9b37f0e7c130acfac926a329d742ca0bf9edbc39d5bb64dffbbd81467be1fab250eaedbeff79bb2a697584a0b14626833d06f92dbdddd6bc12d6caba725d1eae4a899b4fd75b9bbd9ed05cca9f96c7cc41ae236f3c904f0d9ee4c83111e8dc2bf520a30bcfb2afb8943f61cfd4ef9364dab069276b282f831e1abad31048926ca3cccaa7406998620c941b1ded73d623c0659462e13bf68c0ceafbd5a23afb402b2477297e431182d964cd57cc494b26886af5037964467df5b2f0f981a5aaac9a1718b5b00c174adb0d4de383eb46ffb0ecffc4a432822b9af3d21e7b5b10b7e221978ffb47d058f33456518bc647f78d5e3f5e2850957a12f83b9a0c5a8736b509336eced539c9c0faeb37285f90bb12e3499ef9aaae8c5de67ac2e5b374dffe4e1c5c3f14c4cd8905c7a7db03ac69dbdcf627c2bd4f98dda671dd0da9b70495e476fdba17894665ee2c3f8bb9e5d015b0ee727ddf85115d5833fd13633afd2dd4d5bfa751c9a4b7e937c77939cb72f057714ad94a112d28b578ce265306b415339280748fd20977967f5b04ff92d93e994fe3fd4b887bb8fb7c8cd16af9877532e49df4ee3b7132fed5920d5fc5aeda6784f4371af614d1502f036c1519c53bec2a79303050562b1b929cf705254607486c550fbb40fb7445262929bb4ef8ed658c9e4a825ca0d3e796e5e681a5ce19c2c8880a44c78f205add4c8092a790f7a8d2fbae663d32ac0640317a9735e43369ed680247789330a372910a7ce356f8eafd8776972315bb83794589f22f21770cb1b7c17f25861da3fd142398a85ba357865da0684e916eade4d078deb78ccd5442c27d4e4973eb582d2d55fd5877c64f234a61dcc11a828afa5a52ddea02ad8001c09a60fc7a14bd7118486722db6bf3a54dded4691a7937c3cb546395fc99e49954216f203aaee05985a25ea284022c72dd0a156f030c6a2604b9332ab5324c35f77674836321bcd263f8c2176558d83e23cc00d0fa4d438e9536ab7e574067baeeaeda20b2af5f8ee0821e5ff7949a50c286da61b19d8c32cca7ce1459989731cedd2852a297a6b65637413747b47286a62cf4eabfb5308acbf2d593769f0e8d148945556f1fcfdc7cadd8a6e0c0e174ddb301610d201c7b78b079c2270ac5737fe4771d9bab5257dcf5cca173af2f374c6f68e4658189f1aff3bb81c99e56dc69d14249b07d36c2f73adcb5fa1b71b629a0957b571bf6af13c12983056b6263c9c484b0778c3c1eb1261399644e942eb54479461af9397d7413822a4f267304b1dafc32744ef543a3f3442e05d70c727ac1afb846454aa50d2d979349c508f46981c297672ee78a1
diff --git a/src/lib/crypto/krb/prng/prng.c b/src/lib/crypto/krb/prng/prng.c
index e064599bc6..10e5d71df8 100644
--- a/src/lib/crypto/krb/prng/prng.c
+++ b/src/lib/crypto/krb/prng/prng.c
@@ -27,7 +27,7 @@
 #include "prng.h"
 
 #ifdef FORTUNA
-#include "fortuna.h"
+extern struct krb5_prng_provider krb5int_prng_fortuna;
 const struct krb5_prng_provider *prng = &krb5int_prng_fortuna;
 #elif defined(CRYPTO_IMPL_NSS)
 #include "prng_nss.h"
@@ -40,11 +40,10 @@ const struct krb5_prng_provider *prng = &krb5int_prng_yarrow;
 /*
  * krb5int_prng_init - Returns 0 on success
  */
-int krb5int_prng_init(void)
+int
+krb5int_prng_init(void)
 {
-    int err = 0;
-    err = prng->init();
-    return err;
+    return prng->init();
 }
 
 /*
@@ -54,9 +53,7 @@ krb5_error_code KRB5_CALLCONV
 krb5_c_random_add_entropy(krb5_context context, unsigned int randsource,
                           const krb5_data *data)
 {
-    krb5_error_code err = 0;
-    err = prng->add_entropy(context, randsource, data);
-    return err;
+    return prng->add_entropy(context, randsource, data);
 }
 
 /*
@@ -74,16 +71,13 @@ krb5_c_random_seed(krb5_context context, krb5_data *data)
 krb5_error_code KRB5_CALLCONV
 krb5_c_random_make_octets(krb5_context context, krb5_data *data)
 {
-    krb5_error_code err = 0;
-    err = prng->make_octets(context, data);
-    return err;
+    return prng->make_octets(context, data);
 }
 
 void
-krb5int_prng_cleanup (void)
+krb5int_prng_cleanup(void)
 {
     prng->cleanup();
-    return;
 }
 
 
@@ -93,15 +87,35 @@ krb5int_prng_cleanup (void)
  */
 #if defined(_WIN32)
 
+krb5_boolean
+k5_get_os_entropy(unsigned char *buf, size_t len)
+{
+    krb5_boolean result;
+
+    if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL, 0))
+        return FALSE;
+    result = CryptGenRandom(provider, len, buf);
+    (void)CryptReleaseContext(provider, 0);
+    return result;
+}
+
 krb5_error_code KRB5_CALLCONV
 krb5_c_random_os_entropy(krb5_context context, int strong, int *success)
 {
-    if (success)
-        *success = 0;
+    int oursuccess = 0;
+    char buf[1024];
+    krb5_data data = make_data(buf, sizeof(buf));
+
+    if (k5_get_os_entropy(buf, sizeof(buf)) &&
+        krb5_c_random_add_entropy(context, KRB5_C_RANDSOURCE_OSRAND,
+                                  &data) == 0)
+        oursuccess = 1;
+    if (success != NULL)
+        *success = oursuccess;
     return 0;
 }
 
-#else /*Windows*/
+#else /* not Windows */
 #ifdef HAVE_UNISTD_H
 #include <unistd.h>
 #endif
@@ -109,58 +123,65 @@ krb5_c_random_os_entropy(krb5_context context, int strong, int *success)
 #include <sys/stat.h>
 #endif
 
-/*
- * Helper function to read entropy from  a random device.  Takes the
- * name of a device, opens it, makes sure it is a device and if so,
- * reads entropy.  Returns  a boolean indicating whether entropy was
- * read.
- */
-
-/* 
- * read_entropy_from_device - Returns 0 on success
- */
-static int
-read_entropy_from_device(krb5_context context, const char *device)
+/* Open device, ensure that it is not a regular file, and read entropy.  Return
+ * true on success, false on failure. */
+static krb5_boolean
+read_entropy_from_device(const char *device, unsigned char *buf, size_t len)
 {
-    krb5_data data;
     struct stat sb;
     int fd;
-    unsigned char buf[ENTROPY_BUFSIZE], *bp;
-    int left;
-    fd = open (device, O_RDONLY);
+    unsigned char *bp;
+    size_t left;
+    ssize_t count;
+    krb5_boolean result = FALSE;
+
+    fd = open(device, O_RDONLY);
     if (fd == -1)
-        return 0;
+        return FALSE;
     set_cloexec_fd(fd);
-    if (fstat(fd, &sb) == -1 || S_ISREG(sb.st_mode)) {
-        close(fd);
-        return 0;
-    }
+    if (fstat(fd, &sb) == -1 || S_ISREG(sb.st_mode))
+        goto cleanup;
 
-    for (bp = buf, left = sizeof(buf); left > 0;) {
-        ssize_t count;
-        count = read(fd, bp, (unsigned) left);
-        if (count <= 0) {
-            close(fd);
-            return 0;
-        }
+    for (bp = buf, left = len; left > 0;) {
+        count = read(fd, bp, left);
+        if (count <= 0)
+            goto cleanup;
         left -= count;
         bp += count;
     }
+    result = TRUE;
+
+cleanup:
     close(fd);
-    data.length = sizeof (buf);
-    data.data = (char *) buf;
+    return result;
+}
+
+krb5_boolean
+k5_get_os_entropy(unsigned char *buf, size_t len)
+{
+    return read_entropy_from_device("/dev/urandom", buf, len);
+}
+
+/* Read entropy from device and contribute it to the PRNG.  Returns true on
+ * success. */
+static krb5_boolean
+add_entropy_from_device(krb5_context context, const char *device)
+{
+    krb5_data data;
+    unsigned char buf[ENTROPY_BUFSIZE];
+
+    if (!read_entropy_from_device(device, buf, sizeof(buf)))
+        return FALSE;
+    data = make_data(buf, sizeof(buf));
     return (krb5_c_random_add_entropy(context, KRB5_C_RANDSOURCE_OSRAND,
                                       &data) == 0);
 }
 
-/* 
- * krb5_c_random_os_entropy - Returns 0 on success
- */
 krb5_error_code KRB5_CALLCONV
 krb5_c_random_os_entropy(krb5_context context, int strong, int *success)
 {
     int unused;
-    int *oursuccess = success ? success : &unused;
+    int *oursuccess = (success != NULL) ? success : &unused;
 
     *oursuccess = 0;
     /* If we are getting strong data then try that first.  We are
@@ -168,13 +189,12 @@ krb5_c_random_os_entropy(krb5_context context, int strong, int *success)
        we have both /dev/random and /dev/urandom.  We want the strong
        data included in the reseed so we get it first.*/
     if (strong) {
-        if (read_entropy_from_device(context, "/dev/random"))
+        if (add_entropy_from_device(context, "/dev/random"))
             *oursuccess = 1;
     }
-    if (read_entropy_from_device(context, "/dev/urandom"))
+    if (add_entropy_from_device(context, "/dev/urandom"))
         *oursuccess = 1;
     return 0;
 }
 
-#endif /*Windows or pre-OSX Mac*/
-
+#endif /* not Windows */
diff --git a/src/lib/crypto/krb/prng/prng.h b/src/lib/crypto/krb/prng/prng.h
index f4a0e6fa82..d072507e66 100644
--- a/src/lib/crypto/krb/prng/prng.h
+++ b/src/lib/crypto/krb/prng/prng.h
@@ -44,6 +44,10 @@
 #define ENTROPY_BUFSIZE YARROW_SLOW_THRESH/8  /* SHA1 digest length*/
 #endif
 
+/* Used by PRNG implementations to gather OS entropy.  Returns true on
+ * success. */
+krb5_boolean k5_get_os_entropy(unsigned char *buf, size_t len);
+
 /* prng.h */
 struct krb5_prng_provider {
     char prng_name[8];
diff --git a/src/lib/crypto/libk5crypto.exports b/src/lib/crypto/libk5crypto.exports
index 37db683a32..810c90df8e 100644
--- a/src/lib/crypto/libk5crypto.exports
+++ b/src/lib/crypto/libk5crypto.exports
@@ -102,3 +102,8 @@ krb5int_enc_aes256
 krb5int_enc_camellia128
 krb5int_enc_camellia256
 krb5int_derive_key
+sha2Final
+sha2Init
+sha2Update
+krb5int_aes_enc_blk
+krb5int_aes_enc_key