fortuna Algorithm
The Fortuna Algorithm is a cryptographically secure pseudorandom number generator (CSPRNG) designed by cryptographers Bruce Schneier and Niels Ferguson. Introduced in their book, "Practical Cryptography," the Fortuna algorithm was developed to address potential weaknesses and improve upon existing random number generators. It is highly suitable for various cryptographic applications, including key generation, encryption, and digital signatures. Fortuna is designed to be highly resistant to attacks, even in situations where the attacker can monitor or manipulate the internal state of the generator.
Fortuna is built upon a series of entropy accumulators, which collect random data from various unpredictable sources, such as user inputs, network traffic, or system timings. The collected entropy is then fed into a deterministic generator, which uses a symmetric encryption algorithm, such as AES, to produce a stream of pseudorandom bits. This approach ensures that the generated random numbers are of high quality and difficult to predict, even if some of the entropy sources are compromised. Furthermore, the Fortuna algorithm implements a reseeding mechanism to periodically refresh the generator's state, enhancing its security and ensuring a continuous supply of fresh entropy.
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
/*!
* An implementation of the Fortuna CSPRNG
*
* First create a `FortunaRng` object using either the `new_unseeded`
* constructor or `SeedableRng::from_seed`. Additional entropy may be
* added using the method `add_random_event`, or the underlying RNG
* maybe reseeded directly by `SeedableRng::reseed`. Note that this is
* not recommended, since the generator automatically reseeds itself
* using the data provided by `add_random_events` through an
* accumulator. The accumulator is part of Fortuna's design and using
* `SeedableRng::reseed` directly bypasses it.
*
* Note that the underlying block cipher is `AesSafe256Encryptor` which
* is designed to be timing-attack resistant. The speed hit from this
* is in line with a "safety first" API, but be aware of it.
*
* Fortuna was originally described in
* Practical Cryptography, Niels Ferguson and Bruce Schneier.
* John Wiley & Sons, 2003.
*
* Comments throughout this file contain references of the form
* (PC 1.2.3); these refer to sections within this text.
*
* # A note on forking
*
* Proper behaviour for a CSRNG on a process fork is to reseed itself with
* the timestamp and new process ID, to ensure that after forking the child
* process does not share the same RNG state (and therefore the same output)
* as its parent.
*
* However, this appears not to be possible in Rust, due to
* https://github.com/rust-lang/rust/issues/16799
* The reason is that Rust's process management all happens through its
* stdlib runtime, which explicitly does not support forking, so it provides
* no mechanism with which to detect forks.
*
* What this means is that if you are writing forking code (using `#![no_std]`
* say) then you need to EXPLICITLY RESEED THE RNG AFTER FORKING.
*/
use cryptoutil::copy_memory;
use rand::{Rng, SeedableRng};
use time::precise_time_s;
use aessafe::AesSafe256Encryptor;
use cryptoutil::read_u32_le;
use digest::Digest;
use sha2::Sha256;
use symmetriccipher::BlockEncryptor;
/// Length in bytes that the first pool must be before a "catastrophic
/// reseed" is allowed to happen. (A direct reseed through the
/// `SeedableRng` API is not affected by this limit.)
pub const MIN_POOL_SIZE: usize = 64;
/// Maximum number of bytes to generate before rekeying
const MAX_GEN_SIZE: usize = (1 << 20);
/// Length in bytes of the AES key
const KEY_LEN: usize = 32;
/// Length in bytes of the AES counter
const CTR_LEN: usize = 16;
/// Length in bytes of the AES block
const AES_BLOCK_SIZE: usize = 16;
/// Number of pools used to accumulate entropy
const NUM_POOLS: usize = 32;
/// The underlying PRNG (PC 9.4)
struct FortunaGenerator {
key: [u8; KEY_LEN],
ctr: [u8; CTR_LEN],
}
impl FortunaGenerator {
/// Creates a new generator (PC 9.4.1)
fn new() -> FortunaGenerator {
FortunaGenerator {
key: [0; KEY_LEN],
ctr: [0; CTR_LEN],
}
}
/// Increments the counter in place
fn increment_counter(&mut self) {
for i in 0..self.ctr.len() {
self.ctr[i] = self.ctr[i].wrapping_add(1);
// As soon as we don't carry, stop
if self.ctr[i] != 0 {
break;
}
}
}
/// Reseeds the generator (PC 9.4.2)
fn reseed(&mut self, s: &[u8]) {
// Compute key as Sha256d( key || s )
let mut hasher = Sha256::new();
hasher.input(&self.key[..]);
hasher.input(s);
hasher.result(&mut self.key);
hasher = Sha256::new();
hasher.input(&self.key[..]);
hasher.result(&mut self.key[..]);
// Increment the counter
self.increment_counter();
}
/// Generates some `k` 16-byte blocks of random output (PC 9.4.3)
/// This should never be used directly, except by `generate_random_data`.
fn generate_blocks(&mut self, k: usize, out: &mut [u8]) {
assert!(self.ctr[..] != [0; CTR_LEN][..]);
// Setup AES encryptor
let block_encryptor = AesSafe256Encryptor::new(&self.key[..]);
// Concatenate all the blocks
for j in 0..k {
block_encryptor.encrypt_block(&self.ctr[..],
&mut out[AES_BLOCK_SIZE * j..AES_BLOCK_SIZE * (j + 1)]);
self.increment_counter();
}
}
/// Generates `n` bytes of random data (9.4.4)
fn generate_random_data(&mut self, out: &mut [u8]) {
let (n, rem) = (out.len() / AES_BLOCK_SIZE, out.len() % AES_BLOCK_SIZE);
assert!(n <= MAX_GEN_SIZE);
// Generate output
self.generate_blocks(n, &mut out[..(n * AES_BLOCK_SIZE)]);
if rem > 0 {
let mut buf = [0; AES_BLOCK_SIZE];
self.generate_blocks(1, &mut buf);
copy_memory(&buf[..rem], &mut out[(n * AES_BLOCK_SIZE)..]);
}
// Rekey
let mut new_key = [0; KEY_LEN];
self.generate_blocks(KEY_LEN / AES_BLOCK_SIZE, &mut new_key);
self.key = new_key;
}
}
/// A single entropy pool (not public)
#[derive(Clone, Copy)]
struct Pool {
state: Sha256,
count: usize
}
impl Pool {
fn new() -> Pool {
Pool { state: Sha256::new(), count: 0 }
}
fn input(&mut self, data: &[u8]) {
self.state.input(data);
self.count += data.len();
}
fn result(&mut self, output: &mut [u8]) {
self.state.result(output);
// Double-SHA256 it
self.state = Sha256::new();
self.state.input(output);
self.state.result(output);
// Clear the pool state
self.state = Sha256::new();
self.count = 0;
}
}
/// The `Fortuna` CSPRNG (PC 9.5)
pub struct Fortuna {
pool: [Pool; NUM_POOLS],
generator: FortunaGenerator,
reseed_count: u32,
last_reseed_time: f64
}
impl Fortuna {
/// Creates a new unseeded `Fortuna` (PC 9.5.4)
pub fn new_unseeded() -> Fortuna {
Fortuna {
pool: [Pool::new(); NUM_POOLS],
generator: FortunaGenerator::new(),
reseed_count: 0,
last_reseed_time: 0.0
}
}
/// Adds a random event `e` from source `s` to entropy pool `i` (PC 9.5.6)
pub fn add_random_event(&mut self, s: u8, i: usize, e: &[u8]) {
assert!(i <= NUM_POOLS);
// These restrictions (and `s` in [0, 255]) are part of the Fortuna spec.
assert!(e.len() > 0);
assert!(e.len() <= 32);
(&mut self.pool[i]).input(&[s]);
(&mut self.pool[i]).input(&[e.len() as u8]);
(&mut self.pool[i]).input(e);
}
}
impl Rng for Fortuna {
/// Generate a bunch of random data into `dest` (PC 9.5.5)
///
/// # Failure modes
///
/// If the RNG has not been seeded, and there is less than
/// `MIN_POOL_SIZE` bytes of data in the first accumulator
/// pool, this function will fail the task.
fn fill_bytes(&mut self, dest: &mut [u8]) {
// Reseed if necessary
let now = precise_time_s();
if self.pool[0].count >= MIN_POOL_SIZE &&
now - self.last_reseed_time > 0.1 {
self.reseed_count += 1;
self.last_reseed_time = now;
// Compute key as Sha256d( key || s )
let mut hash = [0; (32 * NUM_POOLS)];
let mut n_pools = 0;
while self.reseed_count % (1 << n_pools) == 0 {
(&mut self.pool[n_pools]).result(&mut hash[n_pools * 32..(n_pools + 1) * 32]);
n_pools += 1;
assert!(n_pools < NUM_POOLS);
assert!(n_pools < 32); // width of counter
}
self.generator.reseed(&hash[..n_pools * 32]);
}
// Fail on unseeded RNG
if self.reseed_count == 0 {
panic!("rust-crypto: an unseeded Fortuna was asked for random bytes!");
}
// Generate return data
for dest in dest.chunks_mut(MAX_GEN_SIZE) {
self.generator.generate_random_data(dest);
}
}
fn next_u32(&mut self) -> u32 {
let mut ret = [0; 4];
self.fill_bytes(&mut ret);
read_u32_le(&ret[..])
}
}
impl<'a> SeedableRng<&'a [u8]> for Fortuna {
fn from_seed(seed: &'a [u8]) -> Fortuna {
let mut ret = Fortuna::new_unseeded();
ret.reseed(seed);
ret
}
fn reseed(&mut self, seed: &'a [u8]) {
self.reseed_count += 1;
self.last_reseed_time = precise_time_s();
self.generator.reseed(seed);
}
}
#[cfg(test)]
fn test_force_reseed(f: &mut Fortuna) {
f.last_reseed_time -= 0.2;
}
#[cfg(test)]
mod tests {
use rand::{SeedableRng, Rng};
use super::{Fortuna, Pool, NUM_POOLS, test_force_reseed};
#[test]
fn test_create_unseeded() {
let _: Fortuna = Fortuna::new_unseeded();
}
#[test]
#[should_panic]
fn test_use_unseeded() {
let mut f: Fortuna = Fortuna::new_unseeded();
let _ = f.next_u32();
}
#[test]
#[should_panic]
fn test_badly_seeded() {
let mut f: Fortuna = Fortuna::new_unseeded();
f.add_random_event(0, 0, &[10; 32]);
let _ = f.next_u32();
}
#[test]
#[should_panic]
fn test_too_big_event() {
let mut f: Fortuna = Fortuna::new_unseeded();
f.add_random_event(0, 0, &[10; 33]);
}
#[test]
fn test_seeded() {
// NB for this test I'm just trusting the output of the RNG to be correct.
// I do check for some high-level features: changing most anything should
// change the output, there should be no tests, etc.
let mut f1: Fortuna = SeedableRng::from_seed(&[0, 1, 2, 3, 4, 5][..]);
assert_eq!(f1.next_u32(), 3369034117);
let mut f2: Fortuna = Fortuna::new_unseeded();
f2.reseed(&[0, 1, 2, 3, 4, 5]);
assert_eq!(f2.next_u32(), 3369034117);
// Ensure reseeding doesn't totally reset the seed. That is, this output should
// be different from the above
let mut f3: Fortuna = Fortuna::new_unseeded();
f3.reseed(&[0, 1, 2, 3, 4, 5]);
f3.reseed(&[0, 1, 2, 3, 4, 5]);
assert_eq!(f3.next_u32(), 2689122182);
// These three should all be different
let mut f4: Fortuna = Fortuna::new_unseeded();
f4.add_random_event(0, 0, &[10; 32]);
f4.add_random_event(0, 0, &[10; 32]);
let x = f4.next_u32();
let mut f5: Fortuna = Fortuna::new_unseeded();
f5.add_random_event(0, 0, &[10; 32]);
f5.add_random_event(0, 0, &[20; 32]);
let y = f5.next_u32();
let mut f6: Fortuna = Fortuna::new_unseeded();
f6.add_random_event(0, 0, &[20; 32]);
f6.add_random_event(0, 0, &[10; 32]);
let z = f6.next_u32();
assert!(x != y);
assert!(y != z);
assert!(x != z);
}
#[test]
fn test_generator_correctness() {
let mut output = [0; 100];
// Expected output as in http://www.seehuhn.de/pages/fortuna
let expected = [ 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];
let mut f: Fortuna = SeedableRng::from_seed(&[1, 2, 3, 4][..]);
f.fill_bytes(&mut output);
assert_eq!(&expected[..], &output[..]);
let mut scratch = [0; (1 << 20)];
f.generator.generate_random_data(&mut scratch);
let expected = [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];
f.fill_bytes(&mut output);
assert_eq!(&expected[..], &output[..]);
f.reseed(&[5]);
let expected = [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];
f.fill_bytes(&mut output);
assert_eq!(&expected[..], &output[..]);
}
#[test]
fn test_accumulator_correctness() {
let mut output = [0; 100];
// Expected output from experiments with pycryto
// Note that this does not match the results for the Go implementation
// as described at http://www.seehuhn.de/pages/fortuna ... I believe
// this is because the author there is reusing some Fortuna state from
// the previous test. These results agree with pycrypto on a fresh slate
let mut f = Fortuna::new_unseeded();
f.pool = [Pool::new(); NUM_POOLS];
f.add_random_event(0, 0, &[0; 32]);
f.add_random_event(0, 0, &[0; 32]);
for i in 0..32 {
f.add_random_event(1, i, &[1, 2]);
}
// from Crypto.Random.Fortuna import FortunaAccumulator
// x = FortunaAccumulator.FortunaAccumulator()
// x.add_random_event(0, 0, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0")
// x.add_random_event(0, 0, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0")
// x.add_random_event(1, 0, "\1\2")
// x.add_random_event(1, 1, "\1\2")
// print list(bytearray(x.random_data(100)))
let expected = [ 21, 42, 103, 180, 211, 46, 177, 231, 172, 210,
109, 198, 34, 40, 245, 199, 76, 114, 105, 185,
186, 112, 183, 213, 19, 72, 186, 26, 182, 211,
254, 88, 67, 142, 246, 102, 80, 93, 144, 152,
123, 191, 168, 26, 21, 194, 69, 214, 249, 80,
182, 165, 203, 69, 134, 140, 11, 208, 50, 175,
180, 210, 110, 119, 3, 75, 1, 8, 5, 142,
226, 168, 179, 246, 82, 42, 223, 239, 201, 23,
28, 30, 195, 195, 9, 154, 31, 172, 209, 232,
238, 111, 75, 251, 196, 43, 217, 241, 93, 237];
f.fill_bytes(&mut output);
assert_eq!(&expected[..], &output[..]);
// Immediately (less than 100ms)
f.add_random_event(0, 0, &[0; 32]);
f.add_random_event(0, 0, &[0; 32]);
// x.add_random_event(0, 0, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0")
// x.add_random_event(0, 0, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0")
// print list(bytearray(x.random_data(100)))
let expected = [101, 123, 175, 157, 142, 202, 211, 47, 149, 214,
135, 249, 148, 19, 50, 116, 169, 188, 240, 218,
91, 62, 35, 44, 142, 108, 95, 20, 37, 185,
19, 121, 128, 231, 213, 23, 94, 147, 14, 41,
199, 253, 246, 14, 230, 152, 11, 17, 118, 254,
96, 251, 171, 115, 66, 21, 196, 164, 82, 6,
139, 238, 135, 22, 179, 6, 6, 252, 115, 87,
19, 167, 56, 192, 140, 93, 132, 78, 22, 16,
114, 68, 123, 200, 37, 183, 163, 224, 201, 155,
233, 71, 111, 26, 8, 114, 232, 181, 13, 51];
f.fill_bytes(&mut output);
assert_eq!(&expected[..], &output[..]);
// Simulate more than 100 ms passing
test_force_reseed(&mut f);
// time.sleep(0.2)
// print list(bytearray(x.random_data(100)))
let expected = [ 62, 147, 205, 228, 22, 3, 225, 217, 211, 202,
49, 148, 236, 125, 132, 43, 25, 177, 172, 93,
98, 177, 112, 160, 76, 101, 60, 98, 225, 9,
223, 120, 161, 98, 173, 178, 71, 15, 90, 153,
64, 179, 143, 22, 43, 165, 87, 147, 177, 128,
21, 105, 214, 197, 224, 187, 22, 139, 16, 153,
251, 48, 244, 87, 10, 104, 119, 179, 27, 255,
67, 148, 192, 52, 147, 216, 79, 204, 106, 112,
238, 0, 239, 99, 159, 96, 184, 90, 54, 122,
184, 241, 221, 151, 169, 29, 197, 45, 80, 6];
f.fill_bytes(&mut output);
assert_eq!(&expected[..], &output[..]);
}
}
#[cfg(all(test, feature = "with-bench"))]
mod bench {
use rand::{SeedableRng, Rng};
use test::Bencher;
use super::Fortuna;
#[bench]
pub fn fortuna_new_32(bh: &mut Bencher) {
let mut f: Fortuna = SeedableRng::from_seed(&[100; 64][..]);
bh.iter( || {
f.next_u32();
});
bh.bytes = 4;
}
#[bench]
pub fn fortuna_new_64(bh: &mut Bencher) {
let mut f: Fortuna = SeedableRng::from_seed(&[100; 64][..]);
bh.iter( || {
f.next_u64();
});
bh.bytes = 8;
}
#[bench]
pub fn fortuna_new_1k(bh: &mut Bencher) {
let mut f: Fortuna = SeedableRng::from_seed(&[100; 64][..]);
let mut bytes = [0u8; 1024];
bh.iter( || {
f.fill_bytes(&mut bytes);
});
bh.bytes = bytes.len() as u64;
}
#[bench]
pub fn fortuna_new_64k(bh: &mut Bencher) {
let mut f: Fortuna = SeedableRng::from_seed(&[100; 64][..]);
let mut bytes = [0u8; 65536];
bh.iter( || {
f.fill_bytes(&mut bytes);
});
bh.bytes = bytes.len() as u64;
}
}
