The Fortuna Random Number Generator

Contents

• Introduction
• Installation and Usage
• Example
• Testing
  • Comparison to the Python Cryptography Toolkit
  • A Pseudorandom Number Sequence Test Program
  • Dieharder Test Suite
• A Call for Help
• Alternative Implementations
  • Go
  • Python
  • Java
  • C
• References

Introduction

This page describes an implementation of the Fortuna random number generator in the Go programming language.

Fortuna is a cryptographically strong random number generator (RNG). The term cryptographically strong indicates that even a very clever and active attacker, who knows some of the random outputs of the RNG, cannot use this knowledge to predict future or past outputs. This property allows, for example, to use the output of the RNG to generate keys for encryption schemes, and to generate session tokens for web pages.

Random number generators are hard to implement and easy to get wrong; even seemingly small details can make a huge difference to the security of the method. For this reason, this implementation tries to follow the original description of the Fortuna generator (chapter 10 of Ferguson and Schneier, 2003) as closely as possible.

Design principles of this implementation:

• Implement the description of the Fortuna generator from chapter 10 of Ferguson and Schneier (2003) as faithfully as possible.
• Keep the code as simple as possible to minimise the risk of mistakes.
• Design the API of the package so that correct usage is easy and incorrect usage is less likely.

Installation and Usage

The Fortuna Go package can be installed using the go get command:

  go get github.com/seehuhn/fortuna

The source code can be found at github.com/seehuhn/fortuna for download or inspection.

Detailed usage instructions are available via the package's online help, either on godoc.org or on the command line:

  godoc github.com/seehuhn/fortuna

Example

The following program shows how to write 1GB worth of random bytes to the file fortuna.out. Careful: this is a lot of data and also any pre-existing file of the same name will be silently overwritten.

package main

import (
    "io"
    "log"
    "os"

    "github.com/seehuhn/fortuna"
)

const (
    outputFileName = "fortuna.out"
    outputFileSize = 1024 * 1024 * 1024
)

func main() {
    rng, _ := fortuna.NewRNG("")

    out, err := os.Create(outputFileName)
    if err != nil {
	log.Fatalf("cannot open %s: %s", outputFileName, err.Error())
    }
    defer out.Close()

    n, _ := io.CopyN(out, rng, outputFileSize)
    log.Printf("wrote %d random bytes to %s", n, outputFileName)
}

The approach shown in this listing is only valid for throw-away programs which are only run a few times and which exit quickly. More realistic programs, in particular long-running servers, must use a seed file, specified using the argument to NewRNG(), and should submit entropy via go channels allocated by the NewEntropyDataSink() or NewEntropyTimeStampSink() methods. An example program illustrating full use of the accumulator can be found in the fortuna source code.

Testing

Comparison to the Python Cryptography Toolkit

To gain confidence that I have implemented the algorithm correctly, I compared the output of my implementation to the output of the implementation included in the Python Cryptography Toolkit.

To test the implementation of the underlying, AES-based generator, I performed the following three tests:

• Starting with a newly initialised generator, I call the Reseed() method, with the four-byte sequence [1, 2, 3, 4] as the argument and then generate 100 random bytes. The output is as follows:

      82, 254, 233, 139, 254, 85, 6, 222, 222, 149, 120, 35, 173, 71, 89,
      232, 51, 182, 252, 139, 153, 153, 111, 30, 16, 7, 124, 185, 159, 24,
      50, 68, 236, 107, 133, 18, 217, 219, 46, 134, 169, 156, 211, 74, 163,
      17, 100, 173, 26, 70, 246, 193, 57, 164, 167, 175, 233, 220, 160, 114,
      2, 200, 215, 80, 207, 218, 85, 58, 235, 117, 177, 223, 87, 192, 50,
      251, 61, 65, 141, 100, 59, 228, 23, 215, 58, 107, 248, 248, 103, 57,
      127, 31, 241, 91, 230, 33, 0, 164, 77, 46
  

• Continuing with the state of the generator after the first experiment, I generate 2²⁰ + 100 more random random bytes. The last 100 bytes of the resulting output are as follows:

      122, 164, 26, 67, 102, 65, 30, 217, 219, 113, 14, 86, 214, 146, 185,
      17, 107, 135, 183, 7, 18, 162, 126, 206, 46, 38, 54, 172, 248, 194,
      118, 84, 162, 146, 83, 156, 152, 96, 192, 15, 23, 224, 113, 76, 21,
      8, 226, 41, 161, 171, 197, 180, 138, 236, 126, 137, 101, 25, 219, 225,
      3, 189, 16, 242, 33, 91, 34, 27, 8, 171, 171, 115, 157, 109, 248,
      198, 227, 18, 204, 211, 42, 184, 92, 42, 171, 222, 198, 117, 162, 134,
      116, 109, 77, 195, 187, 139, 37, 78, 224, 63
  

• Continuing with the state the generator was in after the previous test, I called the Reseed() using the single byte 5 as the new seed and the generate 100 more random numbers. The resulting output is as follows:

      217, 168, 141, 167, 46, 9, 218, 188, 98, 124, 109, 128, 242, 22, 189,
      120, 180, 124, 15, 192, 116, 149, 211, 136, 253, 132, 60, 3, 29, 250,
      95, 66, 133, 195, 37, 78, 242, 255, 160, 209, 185, 106, 68, 105, 83,
      145, 165, 72, 179, 167, 53, 254, 183, 251, 128, 69, 78, 156, 219, 26,
      124, 202, 35, 9, 174, 167, 41, 128, 184, 25, 2, 1, 63, 142, 205,
      162, 69, 68, 207, 251, 101, 10, 29, 33, 133, 87, 189, 36, 229, 56,
      17, 100, 138, 49, 79, 239, 210, 189, 141, 46
  

The first test checks basic functionality, the second test checks the re-keying which takes place after every 2²⁰ bytes, and the third test checks re-seeding.

To test the accumulator component of Fortuna, I performed the following three tests:

• Allocate a new accumulator, and initialise it as follows:

      rng.addRandomEvent(0, 0, make([]byte, 32))
      rng.addRandomEvent(0, 0, make([]byte, 32))
      for i := 0; i < 1000; i++ {
  	rng.addRandomEvent(1, uint(i), []byte{1, 2})
      }
  

  The first two of these commands each add 32 zero-bytes to the accumulator, using source 0 and pool 0. Then generate 100 random bytes. The output is as follows:

      226, 104, 210, 56, 80, 187, 224, 232, 131, 211, 35, 163, 49, 237, 24,
      137, 170, 13, 117, 170, 229, 75, 237, 29, 33, 53, 46, 187, 21, 154,
      18, 26, 157, 186, 69, 166, 241, 28, 148, 72, 62, 241, 150, 175, 15,
      70, 24, 125, 111, 133, 219, 77, 43, 112, 255, 243, 222, 152, 218, 61,
      101, 196, 45, 130, 161, 29, 73, 117, 91, 81, 24, 173, 24, 45, 48,
      90, 222, 127, 26, 195, 88, 191, 216, 22, 200, 245, 158, 162, 218, 10,
      72, 243, 193, 132, 171, 27, 179, 99, 54, 208
  

• Starting with the state after the previous test, and within 100ms of the previous test, add more entropy as follows

      rng.addRandomEvent(0, 0, make([]byte, 32))
      rng.addRandomEvent(0, 0, make([]byte, 32))
  

  and then generate 100 more random numbers. The output is

      34, 163, 146, 161, 13, 93, 118, 204, 224, 58, 215, 141, 198, 90, 38,
      26, 174, 151, 129, 91, 249, 30, 91, 23, 199, 5, 180, 150, 94, 201,
      10, 223, 129, 189, 162, 116, 22, 255, 130, 183, 50, 39, 168, 7, 98,
      138, 223, 129, 231, 222, 193, 66, 59, 187, 16, 100, 171, 169, 194, 12,
      197, 121, 10, 238, 39, 203, 43, 201, 110, 91, 56, 44, 56, 44, 246,
      38, 25, 28, 94, 93, 65, 183, 85, 46, 61, 132, 18, 96, 131, 16,
      138, 241, 1, 22, 192, 249, 66, 242, 153, 112
  

• Wait 200ms (to allow the generator to reseed from pool 0) and generate 100 more random numbers. The output is

      98, 9, 233, 102, 1, 195, 243, 88, 163, 4, 58, 74, 146, 155, 152,
      92, 11, 229, 110, 108, 123, 100, 237, 1, 151, 50, 103, 163, 120, 47,
      209, 232, 249, 100, 33, 102, 126, 37, 133, 104, 57, 148, 187, 255, 186,
      232, 145, 182, 144, 141, 7, 12, 241, 184, 190, 72, 204, 123, 227, 250,
      14, 72, 4, 217, 167, 142, 222, 13, 245, 77, 224, 219, 176, 74, 20,
      13, 151, 138, 231, 135, 34, 192, 236, 5, 161, 249, 223, 212, 154, 198,
      14, 222, 197, 232, 75, 199, 134, 56, 58, 212
  

For all six tests described above, the output generated by my Fortuna implementation and the output of the Fortuna implementation from the Python Cryptography Toolkit coincide. The corresponding source code is available in the files generator_test.go, accumulator_test.go and debug-helper.py in the Fortuna package source.

A Pseudorandom Number Sequence Test Program

I ran the output of the program from section Example through the test program ent by John Walker. The output, 1GB of random bytes, passes this test with the following output:

  Entropy = 8.000000 bits per byte.

  Optimum compression would reduce the size
  of this 1073741824 byte file by 0 percent.

  Chi square distribution for 1073741824 samples is 236.09, and randomly
  would exceed this value 79.65 percent of the times.

  Arithmetic mean value of data bytes is 127.4995 (127.5 = random).
  Monte Carlo value for Pi is 3.141458933 (error 0.00 percent).
  Serial correlation coefficient is -0.000012 (totally uncorrelated = 0.0).

Dieharder Test Suite

Graham Hay has tested the output of fortuna using the dieharder test suite. I am happy to report that my fortuna implementation passes all tests included in the dieharder suite.

A Call for Help

The Fortuna package is a new package which is only lightly tested so far. Also, I am not a trained cryptographer. For these reasons, the package is likely to still contain mistakes. Help with finding these mistakes would be most welcome:

• If you are a good Go programmer and could review my Go code, this would be great! Is my code idiomatic? Did I get the locking right?
• Are there any test vectors for Fortuna available? Currently I am using output from the Python Cryptography Toolkit for comparison, but a more authoritative source of test data would be useful.
• If you know about other implementations of Fortuna and could check whether, for identical seeds, these give the same output as my implementation, this would be great!
• If you know how to use automated tests for random number generators (e.g. the diehard test or FIPS SP 800-22) and if you could test the output of my implementation, this would be great. Section Example, below, shows a program which can be used to write 1GB of random output into a file; the result could probably used as input for the tests.

The source code for my Fortuna implementation is available for inspection at github.com/seehuhn/fortuna. To report problems, suggest improvements or send comments you can either use the GitHub issue tracker / code review system or you can email me directly at <voss@seehuhn.de>. Any feedback is welcome!

Alternative Implementations

Go

• An older implementation of Fortuna in Go is available at github.com/welterde/crypto-fortuna/fortuna. This project seems to not have been updated in a long time and I failed to get this to work with current go versions.
• Raïf S. Naffah also implemented Fortuna in Go; the code is available at code.google.com/p/crypto-fortuna. This project seems to not have been updated in a long time and I failed to get this to work with current go versions.

Python

• A Fortuna implementation in Python by Dwayne Litzenberger. I currently use this library to generate test output for my unit tests.

Java

• A Java implementation of Fortuna, by John Wästerlund, is available at github.com/grunka/Fortuna.
• Another Java implementation of Fortuna, by Ingo Bauersachs, is available at github.com/jitsi/bccontrib. From reading the source code I got the impression that the handling of entropy pools in this implementation differs from the original algorithm.

C

• An implementation of Fortuna in C by Waitman Gobble. This is forked from the PostgreSQL source. I haven't looked at this implementation in detail, but it seems to come with extensive testing.

References

• N. Ferguson and B. Schneier: Practical Cryptography. John Wiley & Sons, 2003.
• The Fortuna Wikipedia page.