Give developers the option to use other block cyphers or hash algorithms.
You can read other Turninger posts which outline my progress building a the Fortuna CPRNG.
So far, we have the PRNG
BlockCypherCprngGenerator, a console app which outputs random data to file or stdout, and can produce random numbers as well as bytes.
Programmers love options, even if we won’t end up using them. Although the Fortuna spec specifies the use of AES-256 and SHA256 the the cryptographic primitives, it says other block cyphers could be used (Blowfish is mentioned by name).
I want the PRNG to be able to use any logical combination of crypto functions. Note the PRNG needs a random bit generator (which could be a block cypher or hash function) and a hash function (for mixing key material).
Eg: AES-128 + SHA256, or Rijndael-256 + SHA512, or HMAC-SHA256 + SHA256.
We should also be able to use different implementations of a cypher / hash function (eg: managed vs native).
Fortuna assumed a 16 byte block size. While 16 bytes is a good minimum, but there’s no reason why that block size couldn’t be larger.
Fortuna treats this block as both a buffer (which it encrypts to generate pseudorandom bits) and a counter (which it increments). My original implementation used a fixed 16 byte buffer, which it incremented in two 64 bit parts (using exception handling as flow control):
I toyed with various obscure c# constructs (like [fixed buffers in a struct]) to create a really nice abstraction of an
(Perhaps the Span
byte, so it was just easier to use a byte array and
BitConverter to create the counter.
The basic interface is straight forward enough: the counter is now encapsulated in a class.
The former is mostly there for unit testing, the later means the
_Counter never leaves this class, and is called from the PRNG.
The constructor (not shown) ensures the counter cypher block size and
_Counter are correct (they should be equal).
And the class implements
IDisposable (not shown) such that after it is destroyed it will throw an exception on use.
Increment() is split into a simple case (which only handles the lower
UInt64), and the overflow case (which handles any size of counter).
Again, they use exception handling as flow control.
Currently, it works in
UInt64 chunks, which means
_Counter must be a multiple of 8 bytes.
This is no problem for most modern cyphers and hash functions.
But to support older functions like 3DES
IncrementNested() would need to handle
Byte sized parts in the last iteration of the loop, and that’s just too much complexity for now.
Now the counter is abstracted away, we can allow a cypher to be passed via the constructor, as long as it implements
At this point, we simply keep adding arguments to the constructor (while leaving a nice sane default in place) to use with every combination of cypher and hash algorithm you can think of. We can accept a specific counter value as well, so we don’t have to start at zero.
We just need to make sure we pass a reasonable combination of algorithms. A list of validation criteria:
- The cypher controls the block size (16, 32 and 64 bytes are possible, 32 only available via Rijndael (the cypher underlying AES) or hash functions, 64 bytes only via SHA512).
- Block and key sizes must be 16, 32 or 64 bytes.
- The length of the initial key passed in must actually match the cypher key size.
- The counter length must match the cypher block size.
- The hash algorithm must produce at least as many bytes as the key.
A rather embarrassing problem I ran into with my ReadablePassphrase KeePass plugin was the random number generator got disposed when I didn’t expect, but kept on producing predictable random numbers (basically from a zero seed). One way to mitigate this is to allow a source of entropy to be injected into the re-key events. (The other way is for the generator to throw an exception when disposed, but that doesn’t make for a very exciting blog post).
The generator accepts a
Func<byte> which is expected to produce some amount of entropy,
which is incorporated into each new key.
The core generator should be as fast as possible, so the default providers of this entropy are classified as cheap.
On my laptop (which is ~5 years old),
CheapEntropy.Get16() takes around 250ns, which is plenty fast enough.
It also needs to be highly portable (as I’d like to make Turninger run on .NET Core), so entropy sources must be standard to .NET. That leaves the most “interesting” sources of entropy unavailable, and we have to use timing and memory statistics.
Two sources of time are used:
And two memory based sources: the current process working set and garbage collector statistics.
These are merged to fit in the 16 byte result.
Note, there is a
CheapEntropy.Get32() which uses the same sources but does less merging.
This is slightly slower than the 16 byte version (~300ns).
An important feature of injecting additional entropy into the generator is it becomes non-deterministic. When producing cryptographic keys, this is a desirable feature. However, the same random number generator may be used for other tasks where determinism is preferred (eg: a monte carlo simulation could be re-run using the same seed and produce the same result). Also, when this generator is used with the larger Fortuna algorithm, Fortuna itself takes care of incorporating higher quality (and much more expensive) entropy.
The generator can use any block cypher which implements
That lets us use managed and native versions of AES, and managed Rijndael (the algorithm which underlies AES).
But there are no other block cyphers in the .NET 4.5 BCL.
There are a bunch of hash functions, which should work just as well as a crypto primitive in generating pseudo random bits.
However, they don’t implement
Instead, they all either directly implement
ICryptoTransform, or can create an object which implements it.
And this is the core interface used to encrypt data (and thus create pseudo random bits).
So, there is an interface used to abstract all the different cyphers and hash algorithms to be crypto primitives.
This is effectively a drop in replacement for anything implementing
SymmetricAlgorithm, as far as the PRNG is concerned.
(At this point,
BlockCypherCprngGenerator got renamed to
BlockCypherCryptoPrimitive is a simple wrapper around any
So I won’t bore you with details.
Things are more interesting with a
This lets you use anything that implements
HashAlgorithm as a random bit generator (eg: MD5, SHA1, SHA2).
The key and block size is defined as the hash length (eg: 16 bytes for MD5, 32 for SHA256, 64 for SHA512).
HashAndKeyTransform class implements
It combines the key and counter material in an array twice as large as the block / key size.
The key sits in the lower “chunk”, the counter value is copied into the upper “chunk”.
Then a hash is derived to get random bits.
HmacCryptoPrimitive works for any HMAC implementation (eg: HMAC-SHA256 or HMAC-SHA512).
In some ways, its a more natural fit to
ICryptoTransform, as an HMAC already has a key.
However, there is a hitch: the .NET HMAC implementations don’t let you change key part way through
HmacCryptoPrimitive needs a
Func<HMAC> to be able to create new instances, which happens whenever you set the Key property.
Again, there is an internal class responsible for implementing
This is simpler than normal hashes, as the key has already been incorporated into the HMAC.
CryptoPrimitive static class provides boiler plate methods to crate various common crypto primitives with the correct parameters.
These are used through the unit tests.
I updated the console app to allow the above features to be used. This isn’t particularly exciting, but does allow a simple way to test different combinations of crypto primitives.
The generator can create around 60MB of random bytes per second (on an i3-7100), however this assumes it is creating relatively large chunks of randomness at a time (32kB chunks).
Most random generators are asked for individual
And the generator in its current state is highly inefficient at this (although I haven’t tried benchmarking it yet).
It generates one block (16 or more bytes), derives the number from it, discards any unused bytes, and then generates 2 more blocks to re-key itself.
A buffered generator would greatly improve performance, at the cost of having some randomness pre-generator and potentially observable.
We’ve added various options to the core PRNG, allowing for different crypto primitives (cyphers and hash functions) and incorporation of some cheap, low quality entropy.
You can see the actual code in BitBucket.
We’re going to start building the accumulator part of Fortuna. That is, the part that gathers entropy, mixes it up and uses that to regularly re-seed the generator.