The Fortuna Random Number Generator

By Jochen Voss, last updated 2014-11-15

Contents

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:

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:

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

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

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:

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

Python

Java

C

References

Copyright © 2014 Jochen Voss. All content on this website (including text, pictures, and any other original works), unless otherwise noted, is licensed under the CC BY-SA 4.0 license.