2
\$\begingroup\$

I'm writing a C# implementation of Fortuna, and have implemented the core PRNG / DRBG which should produce a uniform distribution. I've run a variety of statistical random test suites over the output (Dieharder, TestU01, RaBiGeTe, PractRand) and there were enough border-line results that I'm slightly worried something is wrong.

My question is: is my implementation correctly following the Fortuna algorithm as outlined in 9.4? Have I mucked something up which is subtly skewing the random output?

Other feedback on the code is welcome, but I'm primarily interested in correctness.

As outlined in section 9.4 of Fortuna, I'm using the result of AES encrypting a 128 bit counter as the source of randomness. I've tried really hard to follow the algorithm as clearly and naively as possible (resisting the urge for performance shortcuts, and configuration of the cryptographic primitives).

The code in this post has kept references to the algorithm, but removed assertions and non-essential code. Link to full source code.

public class BlockCypherCprngGenerator
{
    // AES with 256 bit key, as specified in 9.4
    // K, as specified in 9.4.1, is stored in _Cypher.Key
    private readonly SymmetricAlgorithm _Cypher;

    // C, as specified in 9.4.1
    // A 128 bit integer, and a string of bytes to be encrypted.
    private readonly byte[] _CounterData;           

    private const int _BlockSizeInBytes = 128 / 8;
    private const int _KeySizeInBytes = 256 / 8;

    // SHA256, as specified in 9.4
    private readonly HashAlgorithm _HashFunction;

    public int MaxRequestBytes => 2 << 20;      // As sepecified in 9.4.4.


    /// <summary>
    /// Initialise the CPRNG with the given key material.
    /// </summary>
    public BlockCypherCprngGenerator(byte[] key) 
    {
        // Section 9.4.1 - Initialisation
        // Main difference from spec: we accept a key rather than waiting for a Reseed event.
        _Cypher = new AesManaged() {
            KeySize = 256,
            Key = new byte[_KeySizeInBytes],
            IV = new byte[_BlockSizeInBytes],
            Mode = CipherMode.CBC,
        };
        _CounterData = new byte[_BlockSizeInBytes];
        _HashFunction = new SHA256Managed();

        // Difference from spec: re key our cypher immediately with the supplied key.
        Reseed(key);
    }

    public void FillWithRandomBytes(byte[] toFill) => FillWithRandomBytes(toFill, 0, toFill.Length);
    public void FillWithRandomBytes(byte[] toFill, int offset, int count)
    {
        // Section 9.4.4 - Generate Random Data
        // Difference from spec: does not return byte[] but fills a byte[] argument to allow for less allocations.

        // Determine the number of blocks required to fullfil the request.
        int remainder;
        var blocksRequired = Math.DivRem(count, _BlockSizeInBytes, out remainder);
        if (remainder > 0)
            blocksRequired = blocksRequired + 1;

        // As per spec: generate blocks and copy to output.
        // In the event the requested bytes are not a multiple of the block size, additional bytes are discarded.
        var randomData = GenerateRandomBlocks(blocksRequired);
        Buffer.BlockCopy(randomData, 0, toFill, offset, count);

        // As per spec: After each request for random bytes, rekey to destroy evidence of previous key.
        // This ensures you cannot "rewind" the generator if you discover the key.
        var newKeyData = GenerateRandomBlocks(2);
        Reseed(newKeyData);
    }

    public void Reseed(byte[] newSeed)
    {
        // Section 9.4.2 - Reseed
        // As per spec: Compute new key by combining the current key and new seed material using SHA 256.
        var combinedKeyMaterial = _Cypher.Key.Concat(newSeed).ToArray();
        _Cypher.Key = _HashFunction.ComputeHash(combinedKeyMaterial).ToArray();

        // As per spec: Increment the counter data.
        // Implementation specific: this is a separate method to abstract the duel byte[] and Int128 type.
        IncrementCounterData();
    }


    private byte[] GenerateRandomBlocks(int blockCount)
    {
        // Section 9.4.3 - Generate Blocks
        // As per spec: blockCount is k, the number of blocks to generate.
        // As per spec: result is r, an empty string of bytes
        var result = new byte[blockCount * _BlockSizeInBytes];

        var encryptor = _Cypher.CreateEncryptor();
        // Append the necessary blocks.
        for (int i = 0; i < blockCount; i++)
        {
            // As per spec: Encrypt and accumulate - but we don't need to concat as we have preallocted the array.
            var encryptedCount = encryptor.TransformBlock(_CounterData, 0, _CounterData.Length, result, i * _BlockSizeInBytes);
            // As per spec: Increment the counter
            IncrementCounterData();
        }
        return result;
    }

    private void IncrementCounterData()
    {
        // Assumption: 16 byte counter data which is incremented in two 64 bit halves.
        try
        {
            ulong c1 = BitConverter.ToUInt64(_CounterData, 0) + 1;
            var c1Bytes = BitConverter.GetBytes(c1);
            Buffer.BlockCopy(c1Bytes, 0, _CounterData, 0, c1Bytes.Length);
        }
        catch (OverflowException)
        {
            // Lower half overflowed: increment the upper half and reset lower.
            try
            {
                ulong c2 = BitConverter.ToUInt64(_CounterData, 8) + 1;
                var c2Bytes = BitConverter.GetBytes(c2);
                Array.Clear(_CounterData, 0, 8);
                Buffer.BlockCopy(c2Bytes, 0, _CounterData, 8, c2Bytes.Length);
            }
            catch (OverflowException)
            {
                // Both overflowed: reset counter.
                Array.Clear(_CounterData, 0, _CounterData.Length);
            }
        }
    }
}

Link to blog post with full details of random tests, if that's a helpful thing.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.