Fortuna PRNG C++ Source Code

Fortuna

This is an implementation of the Fortuna PRNG by Niels Ferguson and Bruce Schneier. The design is from their book 'Practical Cryptography'. I have tried to follow their design as closely as possible, but there are a few differences.

The main differences are:

	The seed file is encrypted with a user supplied password.
	The state of each of the 32 entropy pools is written to the seed file.
	I developed a fast linked list structure to hold the pool data in memory.

Introduction

Generating good random numbers is an essential part of any cryptographic system. Random numbers are used to generate keys, initialization vectors, nonces etc. Particularly in the case of encryption keys generated from a software PRNG, an attacker must not be able to predict past or future keys by examining the output from the PRNG.

Fortuna

Fortuna has a number of novel features as designed by Ferguson and Schneier. Fortuna does not involve any entropy estimators. This has the benefit that even if entropy is not being fed to the PRNG for a period of time, Fortuna will continue to generate good PRN's as long as the state of the entropy pools has not been compromised.

Fortuna uses 32 entropy pools, to allow recovery from a compromise of the pool state. Pool i is only used once every 2^i reseeds. Because some pools will not be used very often an attacker will not be able to deduce the pool contents very easily.

Overview

Fortuna is composed of 4 parts:

	Generator - generates the actual pseudo random numbers
	Pool Manager and Pools - accumluates entropy and hashes state as required
	Source Manager and Sources - collects entropy and feeds entropy to the pools
	Seed File - Encrypts the prng state and reads from and writes to disk

Generator

The generator uses AES encryption in CTR mode to generate random numbers. The entropy pools are used to create a 256 bit key by hashing their state using SHA-256. A 64 bit nonce and 64 bit counter are encrypted in a 128 bit block using the key from the hashed entropy pools. The encrypted nonce and key become the random data returned by Fortuna. When a specific request for random numbers is complete, the key is replaced by generating another 256 bytes of random data. This prevents a user from compromising previously generated PRN's.

PoolMgr

Each pool executes on it's own thread. Pools accumulate the entropy sent by the Source objects. When a pool exceeds a certain size, a manual reset event is signalled. The pool thread then wakes up and compacts the pool state using SHA-256.

SourceMgr

Each souce executes on it's own thread. Sources are as follows:

	QueryPerformanceCounter - there are 32 threads that collect entropy by using QueryPerformanceCounter on Sleep(1)
	There are 4 threads that walk the registry. This forces an attacker to capture the registry of the machine running Fortuna.
	There is 1 thread monitoring the process data for each process (virtual memory, page faults, I/O Read and Write bytes, etc)
	There is 1 thread which uses the Microsoft Crypto API as a random data source. This way an attacker has to break the Microsoft Crypto API as part of attacking this implementation of Fortuna.

Adding new sources is very easy in this design. Each source is derived from the base class Source, see Source.cpp / .h for details.

SeedFile

The seed file persists the state of the generator and the 32 entropy pools using password based encryption.