README
¶
Fortuna
=======
An implementation of Ferguson and Schneier's Fortuna_ random number
generator in Go.
Copyright (C) 2013 Jochen Voss
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
The homepage of this package is at <http://www.seehuhn.de/pages/fortuna>.
Please send any comments or bug reports to the program's author,
Jochen Voss <voss@seehuhn.de>.
.. _Fortuna: http://en.wikipedia.org/wiki/Fortuna_(PRNG)
Overview
--------
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.
.. _cryptographically strong: http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator
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 [FS03]_) as closely as possible. In addition, some effort was made
to ensure that, given identical seeds, the output of this
implementation coincides with the output of the implementation from
the `Python Cryptography Toolkit`_.
.. [FS03] Niels Ferguson, Bruce Schneier: *Practical Cryptography*, Wiley, 2003.
.. _Python Cryptography Toolkit: https://www.dlitz.net/software/pycrypto/
Installation
------------
This package can be installed using the ``go get`` command::
go get github.com/seehuhn/fortuna
Usage
-----
The Fortuna random number generator consists of two parts: The
accumulator collects caller-provided randomness (e.g. timings between
the user's key presses). This randomness is then used to seed a
pseudo random number generator. During operation, the randomness from
the accumulator is also used to periodically reseed the generator,
thus allowing to recover from limited compromises of the generator's
state.
The accumulator and the generator are described in separate sections,
below. 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
.. _godoc.org: http://godoc.org/github.com/seehuhn/fortuna
Accumulator
...........
The usual way to use the Fortuna random number generator is by
creating an object of type ``Accumulator``. A new ``Accumulator`` can
be allocated using the ``NewRNG()`` function::
rng, err := fortuna.NewRNG(seedFileName)
if err != nil {
panic("cannot initialise the RNG: " + err.Error())
}
defer rng.Close()
The argument ``seedFileName`` is the name of a file where a small
amount of randomness can be stored between runs of the program. The
program must be able to both read and write this file, and the
contents must be kept confidential. If the ``seedFileName`` argument
equals the empty string ``""``, no entropy is stored between runs. In
this case, the initial seed is only based on the current time of day,
the current user name, the list of currently installed network
interfaces, and output of the system random number generator. Not
using a seed file can lead to more predictable output in the initial
period after the generator has been created; a seed file must be used
in security sensitive applications.
If a seed file is used, the Accumulator must be closed using the
``Close()`` method after use.
Randomness can be extracted from the Accumulator using the
``RandomData()`` and ``Read()`` methods. For example, a slice of 16
random bytes can be obtained using the following command::
data := rng.RandomData(16)
Entropy Pools
.............
The Accumulator uses 32 entropy pools to collect randomness from the
environment. The use of external entropy helps to recover from
situations where an attacker obtained (partial) knowledge of the
generator state.
Any program using the Fortuna generator should continuously collect
random/unpredictable data and should submit this data to the
Accumulator. For example, code like the following could be used to
submit the times between requests in a web-server::
sink := rng.NewEntropyTimeStampSink()
defer close(sink)
http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
sink <- time.Now()
...
})
Generator
.........
The ``Generator`` class provides a pseudo random number generator
which forms the basis of the accumulator described above. New
instances of the Fortuna pseudo random number generator can be created
using the ``NewGenerator()`` function. The argument ``newCipher``
should normally be ``aes.NewCipher`` from the ``crypto/aes`` package,
but the Serpent_ or Twofish_ ciphers can also be used::
gen := fortuna.NewGenerator(aes.NewCipher)
.. _Serpent: http://en.wikipedia.org/wiki/Serpent_(cipher)
.. _Twofish: http://en.wikipedia.org/wiki/Twofish
The generator can be seeded using the ``.Seed()`` or ``.Reseed()``
methods::
gen.Seed(1234)
The method ``.Seed()`` should be used if reproducible output is
required, whereas ``.Reseed()`` can be used to add entropy in order to
achieve less predictable output.
Uniformly distributed random bytes can then be extracted using the
``.PseudoRandomData()`` method::
data := gen.PseudoRandomData(16)
``Generator`` implements the ``rand.Source`` interface and thus the
functions from the ``math/rand`` package can be used to obtain pseudo
random samples from more complicated distributions.
Documentation
¶
Overview ¶
Package fortuna implements the Fortuna random number generator by Niels Ferguson and Bruce Schneier. Fortuna is a cryptographically strong pseudo-random number generator; typical use cases include generation of keys in cryptographic ciphers and session tokens for web apps.
The homepage of this package is at http://www.seehuhn.de/pages/fortuna . Please send any comments or bug reports to the program's author, Jochen Voss <voss@seehuhn.de>.
The Fortuna random number generator consists of two parts: The accumulator collects caller-provided randomness (e.g. timings between the user's key presses). This randomness is then used to seed a pseudo random number generator. During operation, the randomness from the accumulator is also used to periodically reseed the generator, thus allowing to recover from limited compromises of the generator's state. The accumulator and the generator are described in separate sections, below.
Accumulator ¶
The usual way to use the Fortuna random number generator is by creating an object of type Accumulator. A new Accumulator can be allocated using the NewRNG() function:
rng, err := fortuna.NewRNG(seedFileName)
if err != nil {
panic("cannot initialise the RNG: " + err.Error())
}
defer rng.Close()
The argument seedFileName is the name of a file where a small amount of randomness can be stored between runs of the program. The program must be able to both read and write this file, and the contents must be kept confidential. If the seedFileName argument equals the empty string "", no entropy is stored between runs. In this case, the initial seed is only based on the current time of day, the current user name, the list of currently installed network interfaces, and output of the system random number generator. Not using a seed file can lead to more predictable output in the initial period after the generator has been created; a seed file must be used in security sensitive applications.
If a seed file is used, the Accumulator must be closed using the Close() method after use.
Randomness can be extracted from the Accumulator using the RandomData() and Read() methods. For example, a slice of 16 random bytes can be obtained using the following command:
data := rng.RandomData(16)
Entropy Pools ¶
The Accumulator uses 32 entropy pools to collect randomness from the environment. The use of external entropy helps to recover from situations where an attacker obtained (partial) knowledge of the generator state.
Any program using the Fortuna generator should continuously collect random/unpredictable data and should submit this data to the Accumulator. For example, code like the following could be used to submit the times between requests in a web-server:
sink := rng.NewEntropyTimeStampSink()
defer close(sink)
http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
sink <- time.Now()
...
})
Generator ¶
The Generator class provides a pseudo random number generator which forms the basis of the Accumulator described above. New instances of the Fortuna pseudo random number generator can be created using the NewGenerator() function. The argument newCipher should normally be aes.NewCipher from the crypto/aes package, but the Serpent or Twofish ciphers can also be used:
gen := fortuna.NewGenerator(aes.NewCipher)
The generator can be seeded using the Seed() or Reseed() methods:
gen.Seed(1234)
The method .Seed() should be used if reproducible output is required, whereas .Reseed() can be used to add entropy in order to achieve less predictable output.
Uniformly distributed random bytes can then be extracted using the .PseudoRandomData() method:
data := gen.PseudoRandomData(16)
Generator implements the rand.Source interface and thus the functions from the math/rand package can be used to obtain pseudo random samples from more complicated distributions.
Index ¶
- Variables
- type Accumulator
- func (acc *Accumulator) Close() error
- func (acc *Accumulator) Int63() int64
- func (acc *Accumulator) NewEntropyDataSink() chan<- []byte
- func (acc *Accumulator) NewEntropyTimeStampSink() chan<- time.Time
- func (acc *Accumulator) RandomData(n uint) []byte
- func (acc *Accumulator) Read(p []byte) (n int, err error)
- func (acc *Accumulator) Seed(seed int64)
- func (acc *Accumulator) Uint64() uint64
- type Generator
- type NewCipher
Constants ¶
This section is empty.
Variables ¶
var ( ErrCorruptedSeed = errors.New("seed file corrupted") ErrInsecureSeed = errors.New("seed file with insecure permissions") )
Error codes relating to seed files.
var ( // NewAccumulatorAES is an alias for NewRNG, provided for backward // compatibility. It should not be used in new code. NewAccumulatorAES = NewRNG )
Functions ¶
This section is empty.
Types ¶
type Accumulator ¶
type Accumulator struct {
// contains filtered or unexported fields
}
Accumulator holds the state of one instance of the Fortuna random number generator. Randomness can be extracted using the RandomData() and Read() methods. Entropy from the environment should be submitted regularly using channels allocated by the NewEntropyDataSink() or NewEntropyTimeStampSink() methods.
It is safe to access an Accumulator object concurrently from different goroutines.
func NewAccumulator ¶
func NewAccumulator(newCipher NewCipher, seedFileName string) (*Accumulator, error)
NewAccumulator allocates a new instance of the Fortuna random number generator. The argument 'newCipher' allows to choose a block cipher like Serpent or Twofish instead of the default AES. NewAccumulator(aes.NewCipher, seedFileName) is the same as NewRNG(seedFileName). See the documentation for NewRNG() for more information.
func NewRNG ¶
func NewRNG(seedFileName string) (*Accumulator, error)
NewRNG allocates a new instance of the Fortuna random number generator.
The argument seedFileName gives the name of a file where a small amount of randomness can be stored between runs of the program; the program must be able to both read and write this file. The contents of the seed file must be kept secret and seed files must not be shared between concurrently running instances of the random number generator.
In case the seed file does not exist, a new seed file is created. If a corrupted seed file is found, ErrCorruptedSeed is returned. If a seed file with insecure file permissions is found, ErrInsecureSeed is returned. If reading or writing the seed otherwise fails, the corresponding error is returned.
The returned random generator must be closed using the .Close() method after use.
func (*Accumulator) Close ¶
func (acc *Accumulator) Close() error
Close must be called before the program exits to ensure that the seed file is correctly updated. After Close has been called the Accumulator must not be used any more.
func (*Accumulator) Int63 ¶
func (acc *Accumulator) Int63() int64
Int63 returns a positive random integer, uniformly distributed on the range 0, 1, ..., 2^63-1. This function is part of the rand.Source interface.
func (*Accumulator) NewEntropyDataSink ¶
func (acc *Accumulator) NewEntropyDataSink() chan<- []byte
NewEntropyDataSink returns a channel through which data can be submitted to the Accumulator's entropy pools. Data should be written to the returned channel periodically to add entropy to the state of the random number generator. The written data should be derived from quantities which change between calls and which cannot be (completely) known to an attacker. Typical sources of randomness include noise from a microphone/camera, CPU cycle counters, or the number of processes running on the system.
If the data written to the channel is longer than 32 bytes, the data is hashed internally and the hash is submitted to the entropy pools instead of the data itself.
The channel can be closed by the caller to indicate that no more entropy will be sent via this channel.
func (*Accumulator) NewEntropyTimeStampSink ¶
func (acc *Accumulator) NewEntropyTimeStampSink() chan<- time.Time
NewEntropyTimeStampSink returns a channel through which timing data can be submitted to the Accumulator's entropy pools. The current time should be written to the returned channel regularly to add entropy to the state of the random number generator. The submitted times should be chosen such that they cannot be (completely) known to an attacker. Typical sources of randomness include the arrival times of network packets or the times of key-presses by the user.
The channel can be closed by the caller to indicate that no more entropy will be sent via this channel.
func (*Accumulator) RandomData ¶
func (acc *Accumulator) RandomData(n uint) []byte
RandomData returns a slice of n random bytes. The result can be used as a replacement for a sequence of uniformly distributed and independent bytes, and will be difficult to guess for an attacker.
func (*Accumulator) Read ¶
func (acc *Accumulator) Read(p []byte) (n int, err error)
Read allows to extract randomness from the Accumulator using the io.Reader interface. Read fills the byte slice p with random bytes. The method always reads len(p) bytes and never returns an error.
func (*Accumulator) Seed ¶
func (acc *Accumulator) Seed(seed int64)
Seed is part of the rand.Source interface. This method is only present so that Accumulator objects can be used with the functions from the math/rand package. Do not call this method!
func (*Accumulator) Uint64 ¶
func (acc *Accumulator) Uint64() uint64
Uint64 returns a positive random integer, uniformly distributed on the range 0, 1, ..., 2^64-1. This function is part of the rand.Source64 interface.
type Generator ¶
type Generator struct {
// contains filtered or unexported fields
}
Generator holds the state of one instance of the Fortuna pseudo random number generator. Before use, the generator must be seeded using the Reseed() or Seed() method. Randomness can then be extracted using the PseudoRandomData() method. The Generator class implements the rand.Source interface.
This Generator class is not safe for use with concurrent accesss. If the generator is accessed from different Go-routines, the callers must synchronise access using sync.Mutex or similar.
func NewGenerator ¶
NewGenerator creates a new instance of the Fortuna pseudo random number generator. The function newCipher should normally be aes.NewCipher from the crypto/aes package, but the Serpent or Twofish ciphers can also be used.
The initial seed is chosen based on the current time, the current user name, the currently installed network interfaces and randomness from the system random number generator.
func (*Generator) Int63 ¶
Int63 returns a positive random integer, uniformly distributed on the range 0, 1, ..., 2^63-1. This function is part of the rand.Source interface.
func (*Generator) PseudoRandomData ¶
PseudoRandomData returns a slice of n pseudo-random bytes. The result can be used as a replacement for a sequence of n uniformly distributed and independent bytes.
func (*Generator) Reseed ¶
Reseed uses the current generator state and the given seed value to update the generator state. Care is taken to make sure that knowledge of the new state after a reseed does not allow to reconstruct previous output values of the generator.
This is like the ReseedInt64() method, but the seed is given as a byte slice instead of as an int64.
func (*Generator) ReseedInt64 ¶
ReseedInt64 uses the current generator state and the given seed value to update the generator state. Care is taken to make sure that knowledge of the new state after a reseed does not allow to reconstruct previous output values of the generator.
This is like the Reseed() method, but the seed is given as an int64 instead of as a byte slice.
func (*Generator) Seed ¶
Seed uses the given seed value to set a new generator state. In contrast to the Reseed() method, the Seed() method discards all previous state, thus allowing to generate reproducible output. This function is part of the rand.Source interface.
Use of this method should be avoided in cryptographic applications, since reproducible output will lead to security vulnerabilities.
Source Files