crypto/
fortuna.rs

1// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
2// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
3// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
4// option. This file may not be copied, modified, or distributed
5// except according to those terms.
6
7/*!
8 * An implementation of the Fortuna CSPRNG
9 *
10 * First create a `FortunaRng` object using either the `new_unseeded`
11 * constructor or `SeedableRng::from_seed`. Additional entropy may be
12 * added using the method `add_random_event`, or the underlying RNG
13 * maybe reseeded directly by `SeedableRng::reseed`. Note that this is
14 * not recommended, since the generator automatically reseeds itself
15 * using the data provided by `add_random_events` through an
16 * accumulator. The accumulator is part of Fortuna's design and using
17 * `SeedableRng::reseed` directly bypasses it.
18 *
19 * Note that the underlying block cipher is `AesSafe256Encryptor` which
20 * is designed to be timing-attack resistant. The speed hit from this
21 * is in line with a "safety first" API, but be aware of it.
22 *
23 * Fortuna was originally described in
24 *   Practical Cryptography, Niels Ferguson and Bruce Schneier.
25 *   John Wiley & Sons, 2003.
26 *
27 * Comments throughout this file contain references of the form
28 * (PC 1.2.3); these refer to sections within this text.
29 *
30 * # A note on forking
31 *
32 * Proper behaviour for a CSRNG on a process fork is to reseed itself with
33 * the timestamp and new process ID, to ensure that after forking the child
34 * process does not share the same RNG state (and therefore the same output)
35 * as its parent.
36 *
37 * However, this appears not to be possible in Rust, due to
38 *     https://github.com/rust-lang/rust/issues/16799
39 * The reason is that Rust's process management all happens through its
40 * stdlib runtime, which explicitly does not support forking, so it provides
41 * no mechanism with which to detect forks.
42 *
43 * What this means is that if you are writing forking code (using `#![no_std]`
44 * say) then you need to EXPLICITLY RESEED THE RNG AFTER FORKING.
45 */
46
47use cryptoutil::copy_memory;
48
49use rand::{Rng, SeedableRng};
50use time::precise_time_s;
51
52use aessafe::AesSafe256Encryptor;
53use cryptoutil::read_u32_le;
54use digest::Digest;
55use sha2::Sha256;
56use symmetriccipher::BlockEncryptor;
57
58/// Length in bytes that the first pool must be before a "catastrophic
59/// reseed" is allowed to happen. (A direct reseed through the
60/// `SeedableRng` API is not affected by this limit.)
61pub const MIN_POOL_SIZE: usize = 64;
62/// Maximum number of bytes to generate before rekeying
63const MAX_GEN_SIZE: usize = (1 << 20);
64/// Length in bytes of the AES key
65const KEY_LEN: usize = 32;
66/// Length in bytes of the AES counter
67const CTR_LEN: usize = 16;
68/// Length in bytes of the AES block
69const AES_BLOCK_SIZE: usize = 16;
70/// Number of pools used to accumulate entropy
71const NUM_POOLS: usize = 32;
72
73/// The underlying PRNG (PC 9.4)
74struct FortunaGenerator {
75    key: [u8; KEY_LEN],
76    ctr: [u8; CTR_LEN],
77}
78
79impl FortunaGenerator {
80    /// Creates a new generator (PC 9.4.1)
81    fn new() -> FortunaGenerator {
82        FortunaGenerator {
83            key: [0; KEY_LEN],
84            ctr: [0; CTR_LEN],
85        }
86    }
87
88    /// Increments the counter in place
89    fn increment_counter(&mut self) {
90        for i in 0..self.ctr.len() {
91            self.ctr[i] = self.ctr[i].wrapping_add(1);
92            // As soon as we don't carry, stop
93            if self.ctr[i] != 0 {
94                break;
95            }
96        }
97    }
98
99    /// Reseeds the generator (PC 9.4.2)
100    fn reseed(&mut self, s: &[u8]) {
101        // Compute key as Sha256d( key || s )
102        let mut hasher = Sha256::new();
103        hasher.input(&self.key[..]);
104        hasher.input(s);
105        hasher.result(&mut self.key);
106        hasher = Sha256::new();
107        hasher.input(&self.key[..]);
108        hasher.result(&mut self.key[..]);
109        // Increment the counter
110        self.increment_counter();
111    }
112
113    /// Generates some `k` 16-byte blocks of random output (PC 9.4.3)
114    /// This should never be used directly, except by `generate_random_data`.
115    fn generate_blocks(&mut self, k: usize, out: &mut [u8]) {
116        assert!(self.ctr[..] != [0; CTR_LEN][..]);
117
118        // Setup AES encryptor
119        let block_encryptor = AesSafe256Encryptor::new(&self.key[..]);
120        // Concatenate all the blocks
121        for j in 0..k {
122            block_encryptor.encrypt_block(&self.ctr[..],
123                                          &mut out[AES_BLOCK_SIZE * j..AES_BLOCK_SIZE * (j + 1)]);
124            self.increment_counter();
125        }
126    }
127
128    /// Generates `n` bytes of random data (9.4.4)
129    fn generate_random_data(&mut self, out: &mut [u8]) {
130        let (n, rem) = (out.len() / AES_BLOCK_SIZE, out.len() % AES_BLOCK_SIZE);
131        assert!(n <= MAX_GEN_SIZE);
132
133        // Generate output
134        self.generate_blocks(n, &mut out[..(n * AES_BLOCK_SIZE)]);
135        if rem > 0 {
136            let mut buf = [0; AES_BLOCK_SIZE];
137            self.generate_blocks(1, &mut buf);
138            copy_memory(&buf[..rem], &mut out[(n * AES_BLOCK_SIZE)..]);
139        }
140
141        // Rekey
142        let mut new_key = [0; KEY_LEN];
143        self.generate_blocks(KEY_LEN / AES_BLOCK_SIZE, &mut new_key);
144        self.key = new_key;
145    }
146}
147
148
149/// A single entropy pool (not public)
150#[derive(Clone, Copy)]
151struct Pool {
152    state: Sha256,
153    count: usize
154}
155
156impl Pool {
157    fn new() -> Pool {
158        Pool { state: Sha256::new(), count: 0 }
159    }
160
161    fn input(&mut self, data: &[u8]) {
162        self.state.input(data);
163        self.count += data.len();
164    }
165
166    fn result(&mut self, output: &mut [u8]) {
167        self.state.result(output);
168        // Double-SHA256 it
169        self.state = Sha256::new();
170        self.state.input(output);
171        self.state.result(output);
172        // Clear the pool state
173        self.state = Sha256::new();
174        self.count = 0;
175    }
176}
177
178/// The `Fortuna` CSPRNG (PC 9.5)
179pub struct Fortuna {
180    pool: [Pool; NUM_POOLS],
181    generator: FortunaGenerator,
182    reseed_count: u32,
183    last_reseed_time: f64
184}
185
186impl Fortuna {
187    /// Creates a new unseeded `Fortuna` (PC 9.5.4)
188    pub fn new_unseeded() -> Fortuna {
189        Fortuna {
190            pool: [Pool::new(); NUM_POOLS],
191            generator: FortunaGenerator::new(),
192            reseed_count: 0,
193            last_reseed_time: 0.0
194        }
195    }
196
197    /// Adds a random event `e` from source `s` to entropy pool `i` (PC 9.5.6)
198    pub fn add_random_event(&mut self, s: u8, i: usize, e: &[u8]) {
199        assert!(i <= NUM_POOLS);
200        // These restrictions (and `s` in [0, 255]) are part of the Fortuna spec.
201        assert!(e.len() > 0);
202        assert!(e.len() <= 32);
203        (&mut self.pool[i]).input(&[s]);
204        (&mut self.pool[i]).input(&[e.len() as u8]);
205        (&mut self.pool[i]).input(e);
206    }
207}
208
209impl Rng for Fortuna {
210    /// Generate a bunch of random data into `dest` (PC 9.5.5)
211    ///
212    /// # Failure modes
213    ///
214    /// If the RNG has not been seeded, and there is less than
215    /// `MIN_POOL_SIZE` bytes of data in the first accumulator
216    /// pool, this function will fail the task.
217    fn fill_bytes(&mut self, dest: &mut [u8]) {
218        // Reseed if necessary
219        let now = precise_time_s();
220        if self.pool[0].count >= MIN_POOL_SIZE &&
221           now - self.last_reseed_time > 0.1 {
222            self.reseed_count += 1;
223            self.last_reseed_time = now;
224            // Compute key as Sha256d( key || s )
225            let mut hash = [0; (32 * NUM_POOLS)];
226            let mut n_pools = 0;
227            while self.reseed_count % (1 << n_pools) == 0 {
228                (&mut self.pool[n_pools]).result(&mut hash[n_pools * 32..(n_pools + 1) * 32]);
229                n_pools += 1;
230                assert!(n_pools < NUM_POOLS);
231                assert!(n_pools < 32); // width of counter
232            }
233            self.generator.reseed(&hash[..n_pools * 32]);
234        }
235        // Fail on unseeded RNG
236        if self.reseed_count == 0 {
237            panic!("rust-crypto: an unseeded Fortuna was asked for random bytes!");
238        }
239        // Generate return data
240        for dest in dest.chunks_mut(MAX_GEN_SIZE) {
241            self.generator.generate_random_data(dest);
242        }
243    }
244
245    fn next_u32(&mut self) -> u32 {
246        let mut ret = [0; 4];
247        self.fill_bytes(&mut ret);
248        read_u32_le(&ret[..])
249    }
250}
251
252
253impl<'a> SeedableRng<&'a [u8]> for Fortuna {
254    fn from_seed(seed: &'a [u8]) -> Fortuna {
255        let mut ret = Fortuna::new_unseeded();
256        ret.reseed(seed);
257        ret
258    }
259
260    fn reseed(&mut self, seed: &'a [u8]) {
261        self.reseed_count += 1;
262        self.last_reseed_time = precise_time_s();
263        self.generator.reseed(seed);
264    }
265}
266
267#[cfg(test)]
268fn test_force_reseed(f: &mut Fortuna) {
269    f.last_reseed_time -= 0.2;
270}
271
272#[cfg(test)]
273mod tests {
274    use rand::{SeedableRng, Rng};
275
276    use super::{Fortuna, Pool, NUM_POOLS, test_force_reseed};
277
278    #[test]
279    fn test_create_unseeded() {
280        let _: Fortuna = Fortuna::new_unseeded();
281    }
282
283    #[test]
284    #[should_panic]
285    fn test_use_unseeded() {
286        let mut f: Fortuna = Fortuna::new_unseeded();
287        let _ = f.next_u32();
288    }
289
290    #[test]
291    #[should_panic]
292    fn test_badly_seeded() {
293        let mut f: Fortuna = Fortuna::new_unseeded();
294        f.add_random_event(0, 0, &[10; 32]);
295        let _ = f.next_u32();
296    }
297
298    #[test]
299    #[should_panic]
300    fn test_too_big_event() {
301        let mut f: Fortuna = Fortuna::new_unseeded();
302        f.add_random_event(0, 0, &[10; 33]);
303    }
304
305    #[test]
306    fn test_seeded() {
307        // NB for this test I'm just trusting the output of the RNG to be correct.
308        // I do check for some high-level features: changing most anything should
309        // change the output, there should be no tests, etc.
310        let mut f1: Fortuna = SeedableRng::from_seed(&[0, 1, 2, 3, 4, 5][..]);
311        assert_eq!(f1.next_u32(), 3369034117);
312
313        let mut f2: Fortuna = Fortuna::new_unseeded();
314        f2.reseed(&[0, 1, 2, 3, 4, 5]);
315        assert_eq!(f2.next_u32(), 3369034117);
316
317        // Ensure reseeding doesn't totally reset the seed. That is, this output should
318        // be different from the above
319        let mut f3: Fortuna = Fortuna::new_unseeded();
320        f3.reseed(&[0, 1, 2, 3, 4, 5]);
321        f3.reseed(&[0, 1, 2, 3, 4, 5]);
322        assert_eq!(f3.next_u32(), 2689122182);
323
324        // These three should all be different
325        let mut f4: Fortuna = Fortuna::new_unseeded();
326        f4.add_random_event(0, 0, &[10; 32]);
327        f4.add_random_event(0, 0, &[10; 32]);
328        let x = f4.next_u32();
329
330        let mut f5: Fortuna = Fortuna::new_unseeded();
331        f5.add_random_event(0, 0, &[10; 32]);
332        f5.add_random_event(0, 0, &[20; 32]);
333        let y = f5.next_u32();
334
335        let mut f6: Fortuna = Fortuna::new_unseeded();
336        f6.add_random_event(0, 0, &[20; 32]);
337        f6.add_random_event(0, 0, &[10; 32]);
338        let z = f6.next_u32();
339
340        assert!(x != y);
341        assert!(y != z);
342        assert!(x != z);
343    }
344
345    #[test]
346    fn test_generator_correctness() {
347        let mut output = [0; 100];
348        // Expected output as in http://www.seehuhn.de/pages/fortuna
349        let expected = [ 82, 254, 233, 139, 254,  85,   6, 222, 222, 149,
350                        120,  35, 173,  71,  89, 232,  51, 182, 252, 139,
351                        153, 153, 111,  30,  16,   7, 124, 185, 159,  24,
352                         50,  68, 236, 107, 133,  18, 217, 219,  46, 134,
353                        169, 156, 211,  74, 163,  17, 100, 173,  26,  70,
354                        246, 193,  57, 164, 167, 175, 233, 220, 160, 114,
355                          2, 200, 215,  80, 207, 218,  85,  58, 235, 117,
356                        177, 223,  87, 192,  50, 251,  61,  65, 141, 100,
357                         59, 228,  23, 215,  58, 107, 248, 248, 103,  57,
358                        127,  31, 241,  91, 230,  33,   0, 164,  77, 46];
359        let mut f: Fortuna = SeedableRng::from_seed(&[1, 2, 3, 4][..]);
360        f.fill_bytes(&mut output);
361        assert_eq!(&expected[..], &output[..]);
362
363        let mut scratch = [0; (1 << 20)];
364        f.generator.generate_random_data(&mut scratch);
365
366        let expected = [122, 164,  26,  67, 102,  65,  30, 217, 219, 113,
367                         14,  86, 214, 146, 185,  17, 107, 135, 183,   7,
368                         18, 162, 126, 206,  46,  38,  54, 172, 248, 194,
369                        118,  84, 162, 146,  83, 156, 152,  96, 192,  15,
370                         23, 224, 113,  76,  21,   8, 226,  41, 161, 171,
371                        197, 180, 138, 236, 126, 137, 101,  25, 219, 225,
372                          3, 189,  16, 242,  33,  91,  34,  27,   8, 171,
373                        171, 115, 157, 109, 248, 198, 227,  18, 204, 211,
374                         42, 184,  92,  42, 171, 222, 198, 117, 162, 134,
375                        116, 109,  77, 195, 187, 139,  37,  78, 224,  63];
376        f.fill_bytes(&mut output);
377        assert_eq!(&expected[..], &output[..]);
378
379        f.reseed(&[5]);
380
381        let expected = [217, 168, 141, 167,  46,   9, 218, 188,  98, 124,
382                        109, 128, 242,  22, 189, 120, 180, 124,  15, 192,
383                        116, 149, 211, 136, 253, 132,  60,   3,  29, 250,
384                         95,  66, 133, 195,  37,  78, 242, 255, 160, 209,
385                        185, 106,  68, 105,  83, 145, 165,  72, 179, 167,
386                         53, 254, 183, 251, 128,  69,  78, 156, 219,  26,
387                        124, 202,  35,   9, 174, 167,  41, 128, 184,  25,
388                          2,   1,  63, 142, 205, 162,  69,  68, 207, 251,
389                        101,  10,  29,  33, 133,  87, 189,  36, 229,  56,
390                         17, 100, 138,  49,  79, 239, 210, 189, 141,  46];
391
392        f.fill_bytes(&mut output);
393        assert_eq!(&expected[..], &output[..]);
394    }
395
396    #[test]
397    fn test_accumulator_correctness() {
398        let mut output = [0; 100];
399        // Expected output from experiments with pycryto
400        // Note that this does not match the results for the Go implementation
401        // as described at http://www.seehuhn.de/pages/fortuna ... I believe
402        // this is because the author there is reusing some Fortuna state from
403        // the previous test. These results agree with pycrypto on a fresh slate
404        let mut f = Fortuna::new_unseeded();
405        f.pool = [Pool::new(); NUM_POOLS];
406        f.add_random_event(0, 0, &[0; 32]);
407        f.add_random_event(0, 0, &[0; 32]);
408        for i in 0..32 {
409            f.add_random_event(1, i, &[1, 2]);
410        }
411
412        // from Crypto.Random.Fortuna import FortunaAccumulator
413        // x = FortunaAccumulator.FortunaAccumulator()
414        // 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")
415        // 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")
416        // x.add_random_event(1, 0, "\1\2")
417        // x.add_random_event(1, 1, "\1\2")
418        // print list(bytearray(x.random_data(100)))
419        let expected = [ 21,  42, 103, 180, 211,  46, 177, 231, 172, 210,
420                        109, 198,  34,  40, 245, 199,  76, 114, 105, 185,
421                        186, 112, 183, 213,  19,  72, 186,  26, 182, 211,
422                        254,  88,  67, 142, 246, 102,  80,  93, 144, 152,
423                        123, 191, 168,  26,  21, 194,  69, 214, 249,  80,
424                        182, 165, 203,  69, 134, 140,  11, 208,  50, 175,
425                        180, 210, 110, 119,   3,  75,   1,   8,   5, 142,
426                        226, 168, 179, 246,  82,  42, 223, 239, 201,  23,
427                         28,  30, 195, 195,   9, 154,  31, 172, 209, 232,
428                        238, 111,  75, 251, 196,  43, 217, 241,  93, 237];
429        f.fill_bytes(&mut output);
430        assert_eq!(&expected[..], &output[..]);
431
432        // Immediately (less than 100ms)
433        f.add_random_event(0, 0, &[0; 32]);
434        f.add_random_event(0, 0, &[0; 32]);
435
436        // 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")
437        // 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")
438        // print list(bytearray(x.random_data(100)))
439        let expected = [101, 123, 175, 157, 142, 202, 211,  47, 149, 214,
440                        135, 249, 148,  19,  50, 116, 169, 188, 240, 218,
441                         91,  62,  35,  44, 142, 108,  95,  20,  37, 185,
442                         19, 121, 128, 231, 213,  23,  94, 147,  14,  41,
443                        199, 253, 246,  14, 230, 152,  11,  17, 118, 254,
444                         96, 251, 171, 115,  66,  21, 196, 164,  82,   6,
445                        139, 238, 135,  22, 179,   6,   6, 252, 115,  87,
446                         19, 167,  56, 192, 140,  93, 132,  78,  22,  16,
447                        114,  68, 123, 200,  37, 183, 163, 224, 201, 155,
448                        233,  71, 111,  26,   8, 114, 232, 181,  13,  51];
449        f.fill_bytes(&mut output);
450        assert_eq!(&expected[..], &output[..]);
451
452        // Simulate more than 100 ms passing
453        test_force_reseed(&mut f);
454        // time.sleep(0.2)
455        // print list(bytearray(x.random_data(100)))
456        let expected = [ 62, 147, 205, 228,  22,   3, 225, 217, 211, 202,
457                         49, 148, 236, 125, 132,  43,  25, 177, 172,  93,
458                         98, 177, 112, 160,  76, 101,  60,  98, 225,   9,
459                        223, 120, 161,  98, 173, 178,  71,  15,  90, 153,
460                         64, 179, 143,  22,  43, 165,  87, 147, 177, 128,
461                         21, 105, 214, 197, 224, 187,  22, 139,  16, 153,
462                        251,  48, 244,  87,  10, 104, 119, 179,  27, 255,
463                         67, 148, 192,  52, 147, 216,  79, 204, 106, 112,
464                        238,   0, 239,  99, 159,  96, 184,  90,  54, 122,
465                        184, 241, 221, 151, 169,  29, 197,  45,  80,   6];
466        f.fill_bytes(&mut output);
467        assert_eq!(&expected[..], &output[..]);
468    }
469}
470
471#[cfg(all(test, feature = "with-bench"))]
472mod bench {
473    use rand::{SeedableRng, Rng};
474    use test::Bencher;
475
476    use super::Fortuna;
477
478    #[bench]
479    pub fn fortuna_new_32(bh: &mut Bencher) {
480        let mut f: Fortuna = SeedableRng::from_seed(&[100; 64][..]);
481        bh.iter( || {
482            f.next_u32();
483        });
484        bh.bytes = 4;
485    }
486
487    #[bench]
488    pub fn fortuna_new_64(bh: &mut Bencher) {
489        let mut f: Fortuna = SeedableRng::from_seed(&[100; 64][..]);
490        bh.iter( || {
491            f.next_u64();
492        });
493        bh.bytes = 8;
494    }
495
496    #[bench]
497    pub fn fortuna_new_1k(bh: &mut Bencher) {
498        let mut f: Fortuna = SeedableRng::from_seed(&[100; 64][..]);
499        let mut bytes = [0u8; 1024];
500        bh.iter( || {
501            f.fill_bytes(&mut bytes);
502        });
503        bh.bytes = bytes.len() as u64;
504    }
505
506    #[bench]
507    pub fn fortuna_new_64k(bh: &mut Bencher) {
508        let mut f: Fortuna = SeedableRng::from_seed(&[100; 64][..]);
509        let mut bytes = [0u8; 65536];
510        bh.iter( || {
511            f.fill_bytes(&mut bytes);
512        });
513        bh.bytes = bytes.len() as u64;
514    }
515}
crypto/fortuna.rs

crypto/
fortuna.rs
