The accumulator to buffer incoming entropy and generate new seed material.
You can read other Turninger posts which outline my progress building a the Fortuna CPRNG.
So far, we have the PRNG
CypherBasedPrngGenerator with various options, a console app which outputs random data to file or stdout, and can produce random numbers as well as bytes.
Build the accumulator for Fortuna, as specified in section 9.5.
Effectively, the accumulator is a buffer which receives entropy from multiple sources, distributes that into many pools, then uses those pools to generate material to re-seed the core PRNG from time to time.
Or, as a very crude ascii diagram:
The accumulator is designed in such a way that the seed material it produces is extraordinarily unpredictable. So unpredictable that an attacker would need to control every incoming source of entropy, over the entire lifetime of the generator to compromise it.
But before I get into to actual accumulator, I’m going to introduce an
There are numerous counters which will be ticking up over the lifetime of a Fortuna or Terninger instance.
Given that section 9.5.2 allows for a minimum lifetime for a Fortuna instance of 13 years, I’m not convinced
Int64 will be big enough.
I’m not interested in building my own
Int128 type, so decided on Alexander Logger’s BigMath implementation.
And I updated any counters in the
CypherBasedPrngGenerator class to be
The main issue I found with
BigMath.Int128 is it was build with unchecked on by default (which is the default for C#), while I have it off for Terninger (for paranoia sake).
Various unit tests failed with
OverflowException; I needed to add a few
unchecked blocks to make it work.
Pools are defined in section 9.5.2 of the Fortuna spec. 32 of them are specified for an accumulator, and entropy is distributed into them.
In theory, each pool is a binary buffer, of unlimited length. In practise (and assumed in the spec), they are a hash function which keeps partially computing the hash of all incoming entropy, and produces the final result when they are emptied.
Compared to the accumulator itself, a pool is very simple.
The spec recommends SHA256, but I am using SHA512 as the default.
Add() accepts some entropy, accumulates it in the hash function and then increments counters.
GetDigest() finalises the partial hash computation, resets a counter and returns the hash.
Section 126.96.36.199 discusses what a “packet” of entropy should look like. The entropy, length and pool number.
My implementation is a very basic immutable class. C# arrays encode both the entropy and length, and I include the entropy source rather than destination pool, for reasons outlined below.
Fortuna specifies that the entropy sources should specify which pool to place their entropy in. That assumes the sources are, at least for the most part, trustworthy. Which the spec itself admits is an assumption which will not always be true: an attacker must be assumed to control some entropy source: either with knowledge of entropy produced, or ability to influence the entropy’s content. The spec goes on for some length about how it might guarantee entropy is correctly distributed amoung pools, before basically admitting it can’t.
Time to play threat model: Fortuna assumes it will be implemented in an OS kernel with public C style functions.
As such, it can’t tell the difference between an attacker calling
Pool.Add() with malicious or known entropy, and legitimate calls from real entropy sources.
Turninger is going to be in user processes without any cross-process public interface (at least out of the box). So the above scenario is much less likely. (Plugin entropy sources are planned, so that’s a potential source of malicious code / entropy). But the standard process boundary provides a reasonable degree of protection.
The other defence I have planned involves the
If an attacker seeds the accumulator with known entropy, its goal is to flood pools such that they are entirely known by the attacker.
Thus the attacker could derive the internal key.
However, as pools know the
Source of entropy, they could simply discard tainted packets.
Deciding tainted vs legitimate is impossible, but a pool can prevent any one source filling it.
That way, as long as some entropy is received from different sources, the attacker can never completely control a pool.
Now, a malicious source could simply lie and put the wrong type in the
This is basically the same attack the Fortuna spec considers.
However, its possible to verify the
Source type matches the actual source instance at run time in the CLR (although the pool and accumulator probably can’t do that).
And I’ll take advantage of that fact in future work.
As a final note, and as mentioned in 188.8.131.52 of the spec, if an attacker has arbitrary access to the address space of the process, all bets will be off. And, it will probably be simpler for them to just read (or even set) the current key material and be done with it (and in the CLR, all that would take is a reflected call against a private field or method).
The accumulator contains multiple pool objects and manages access to them. 9.5.2 specifies 32 pools, and I’ll allow between 4 and 64.
(There are a stack of counters, statistics and other properties on the class. In the interest of brevity, I’ll omit them here).
So far, this follows the Fortuna spec quite closely (aside from the accumulator managing the pools, which is disallowed in section 184.108.40.206, but I’ll mitigate in other ways, as outlines above).
Add() distributes the incoming entropy across pools in a round-robin fashion.
It assumes all incoming entropy is of similar size, which won’t be the case, so it could split larger chunks into 8 or 16 bytes and distribute across more pools.
Otherwise, it doesn’t get much simpler.
The real interest is in
This walks all pools and checks if each will be used in deriving key material.
Based on the Fortuna spec, larger numbered pools are included less often.
Pool zero is always used, pool one is used every second request, pool two every fourth, and so on.
This means that entropy accumulated in the distant past (possibly weeks or years ago) is occasionally included in a new seed, which makes for a very unpredictable result - just what a crypto random number generator needs!
As mentioned above, a 1kB packet of entropy (say from a hardware random number generator) would be placed in a single pool.
As would an 8 byte result from
This isn’t particularly fair, so lets fix it.
A 16 byte chunk size works well. It’s smaller than any common hash function, so ensures good distribution of entropy from multiple sources against each pool.
Dodis et al proposes distributing entropy using a PRNG in sections 5.2 and 6.3; that is in
Their rationale is it reduces the time for the accumulator to recover when faced with an attacker pushing large amounts of entropy into the generator.
That is, someone with a fire hose and flooding the lower numbered pools may be able to guess the internal state / key of the generator.
And it would take a while before enough untainted entropy arrived and enough re-seeds happened before the attacker loses that edge.
I don’t quite understand Dodis’s maths, but I would like to achieve the same end.
So, rather than randomising in
Add(), Terninger will allow for random pools which are selected at random in
The original pools are referred to as Linear Pools, for the sake of clarity.
Turninger now adds entropy from the random pools to the normal / “linear” pools. Currently, there is a 1 in 8 chance each of the random pools will be used. A simple bit mask is used to determine if each pool will be included. And their usage pattern should be unpredictable (unless you know the key behind the PRNG).
So now higher order pools are used, which gains the best of both worlds.
There are a variety of unit tests which sanity check core behaviours of the accumulator and pools. But I also include some statistics of the first 1000 seeds generated as a text file, which should illustrate how the whole accumulator works (and sanity check its working correctly).
The output below is the first 64 seeds. It’s a delimited / fixed width text file with the following columns:
- Seed number
- Entropy in the accumulator before the seed was generated
- Number of pools drawn on for that seed
- Bit mask of linear pools drawn on
- Bit mask of random pools drawn on
Things of note:
- The accumulated and unused entropy is slowly ticking up, as not all pools are drawn on for each seed.
- There is a clear pattern to how the linear pools are used.
- There is no clear pattern to the random pools.
There are a few improvements I can think of.
The accumulator is currently not thread safe. This almost certainly needs to change when entropy comes from real sources. But I’m hesitant to add locks until I know what the access and usage patterns will be.
I already mentioned that pools could reject incoming entropy based on its source. Preventing any single source dominating a pool is the most obvious use of this property. Other heuristics could be used as well, but I can’t think of any with such a clear benefit for minimal effort.
Pools could validate the source
Type implements an appropriate interface.
This very slightly raises the bar for any attacker.
Although its trivial for a malicious source to implement the right interface, so there seems little point.
The accumulator has been implemented and does everything Fortuna requires, plus more.
It even produces new seed material to send to the
CypherBasedPrngGenerator, which would make the PRNG crypto safe.
You can see the actual code in BitBucket.
Next up, we’ll implement some basic entropy sources (very similar to the cheap entropy already generated). And the key component to connect all our objects together and make them useful: a scheduler to do all the things which need doing. (That is, a thread to actually do the work).