src/librand/chacha.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! The ChaCha random number generator.
  12
  13 use {Rng, SeedableRng, Rand};
  14
  15 const KEY_WORDS    : usize =  8; // 8 words for the 256-bit key
  16 const STATE_WORDS  : usize = 16;
  17 const CHACHA_ROUNDS: usize = 20; // Cryptographically secure from 8 upwards as of this writing
  18
  19 /// A random number generator that uses the ChaCha20 algorithm [1].
  20 ///
  21 /// The ChaCha algorithm is widely accepted as suitable for
  22 /// cryptographic purposes, but this implementation has not been
  23 /// verified as such. Prefer a generator like `OsRng` that defers to
  24 /// the operating system for cases that need high security.
  25 ///
  26 /// [1]: D. J. Bernstein, [*ChaCha, a variant of
  27 /// Salsa20*](http://cr.yp.to/chacha.html)
  28 #[derive(Copy, Clone)]
  29 pub struct ChaChaRng {
  30     buffer: [u32; STATE_WORDS], // Internal buffer of output
  31     state: [u32; STATE_WORDS], // Initial state
  32     index: usize, // Index into state
  33 }
  34
  35 static EMPTY: ChaChaRng = ChaChaRng {
  36     buffer: [0; STATE_WORDS],
  37     state: [0; STATE_WORDS],
  38     index: STATE_WORDS,
  39 };
  40
  41
  42 macro_rules! quarter_round{
  43     ($a: expr, $b: expr, $c: expr, $d: expr) => {{
  44         $a = $a.wrapping_add($b); $d = $d ^ $a; $d = $d.rotate_left(16);
  45         $c = $c.wrapping_add($d); $b = $b ^ $c; $b = $b.rotate_left(12);
  46         $a = $a.wrapping_add($b); $d = $d ^ $a; $d = $d.rotate_left( 8);
  47         $c = $c.wrapping_add($d); $b = $b ^ $c; $b = $b.rotate_left( 7);
  48     }}
  49 }
  50
  51 macro_rules! double_round{
  52     ($x: expr) => {{
  53         // Column round
  54         quarter_round!($x[ 0], $x[ 4], $x[ 8], $x[12]);
  55         quarter_round!($x[ 1], $x[ 5], $x[ 9], $x[13]);
  56         quarter_round!($x[ 2], $x[ 6], $x[10], $x[14]);
  57         quarter_round!($x[ 3], $x[ 7], $x[11], $x[15]);
  58         // Diagonal round
  59         quarter_round!($x[ 0], $x[ 5], $x[10], $x[15]);
  60         quarter_round!($x[ 1], $x[ 6], $x[11], $x[12]);
  61         quarter_round!($x[ 2], $x[ 7], $x[ 8], $x[13]);
  62         quarter_round!($x[ 3], $x[ 4], $x[ 9], $x[14]);
  63     }}
  64 }
  65
  66 #[inline]
  67 fn core(output: &mut [u32; STATE_WORDS], input: &[u32; STATE_WORDS]) {
  68     *output = *input;
  69
  70     for _ in 0..CHACHA_ROUNDS / 2 {
  71         double_round!(output);
  72     }
  73
  74     for i in 0..STATE_WORDS {
  75         output[i] = output[i].wrapping_add(input[i]);
  76     }
  77 }
  78
  79 impl ChaChaRng {
  80
  81     /// Create an ChaCha random number generator using the default
  82     /// fixed key of 8 zero words.
  83     pub fn new_unseeded() -> ChaChaRng {
  84         let mut rng = EMPTY;
  85         rng.init(&[0; KEY_WORDS]);
  86         rng
  87     }
  88
  89     /// Sets the internal 128-bit ChaCha counter to
  90     /// a user-provided value. This permits jumping
  91     /// arbitrarily ahead (or backwards) in the pseudorandom stream.
  92     ///
  93     /// Since the nonce words are used to extend the counter to 128 bits,
  94     /// users wishing to obtain the conventional ChaCha pseudorandom stream
  95     /// associated with a particular nonce can call this function with
  96     /// arguments `0, desired_nonce`.
  97     pub fn set_counter(&mut self, counter_low: u64, counter_high: u64) {
  98         self.state[12] = (counter_low >> 0) as u32;
  99         self.state[13] = (counter_low >> 32) as u32;
 100         self.state[14] = (counter_high >> 0) as u32;
 101         self.state[15] = (counter_high >> 32) as u32;
 102         self.index = STATE_WORDS; // force recomputation
 103     }
 104
 105     /// Initializes `self.state` with the appropriate key and constants
 106     ///
 107     /// We deviate slightly from the ChaCha specification regarding
 108     /// the nonce, which is used to extend the counter to 128 bits.
 109     /// This is provably as strong as the original cipher, though,
 110     /// since any distinguishing attack on our variant also works
 111     /// against ChaCha with a chosen-nonce. See the XSalsa20 [1]
 112     /// security proof for a more involved example of this.
 113     ///
 114     /// The modified word layout is:
 115     /// ```text
 116     /// constant constant constant constant
 117     /// key      key      key      key
 118     /// key      key      key      key
 119     /// counter  counter  counter  counter
 120     /// ```
 121     /// [1]: Daniel J. Bernstein. [*Extending the Salsa20
 122     /// nonce.*](http://cr.yp.to/papers.html#xsalsa)
 123     fn init(&mut self, key: &[u32; KEY_WORDS]) {
 124         self.state[0] = 0x61707865;
 125         self.state[1] = 0x3320646E;
 126         self.state[2] = 0x79622D32;
 127         self.state[3] = 0x6B206574;
 128
 129         for i in 0..KEY_WORDS {
 130             self.state[4 + i] = key[i];
 131         }
 132
 133         self.state[12] = 0;
 134         self.state[13] = 0;
 135         self.state[14] = 0;
 136         self.state[15] = 0;
 137
 138         self.index = STATE_WORDS;
 139     }
 140
 141     /// Refill the internal output buffer (`self.buffer`)
 142     fn update(&mut self) {
 143         core(&mut self.buffer, &self.state);
 144         self.index = 0;
 145         // update 128-bit counter
 146         self.state[12] += 1;
 147         if self.state[12] != 0 {
 148             return;
 149         }
 150         self.state[13] += 1;
 151         if self.state[13] != 0 {
 152             return;
 153         }
 154         self.state[14] += 1;
 155         if self.state[14] != 0 {
 156             return;
 157         }
 158         self.state[15] += 1;
 159     }
 160 }
 161
 162 impl Rng for ChaChaRng {
 163     #[inline]
 164     fn next_u32(&mut self) -> u32 {
 165         if self.index == STATE_WORDS {
 166             self.update();
 167         }
 168
 169         let value = self.buffer[self.index % STATE_WORDS];
 170         self.index += 1;
 171         value
 172     }
 173 }
 174
 175 impl<'a> SeedableRng<&'a [u32]> for ChaChaRng {
 176
 177     fn reseed(&mut self, seed: &'a [u32]) {
 178         // reset state
 179         self.init(&[0; KEY_WORDS]);
 180         // set key in place
 181         let key = &mut self.state[4..4 + KEY_WORDS];
 182         for (k, s) in key.iter_mut().zip(seed) {
 183             *k = *s;
 184         }
 185     }
 186
 187     /// Create a ChaCha generator from a seed,
 188     /// obtained from a variable-length u32 array.
 189     /// Only up to 8 words are used; if less than 8
 190     /// words are used, the remaining are set to zero.
 191     fn from_seed(seed: &'a [u32]) -> ChaChaRng {
 192         let mut rng = EMPTY;
 193         rng.reseed(seed);
 194         rng
 195     }
 196 }
 197
 198 impl Rand for ChaChaRng {
 199     fn rand<R: Rng>(other: &mut R) -> ChaChaRng {
 200         let mut key: [u32; KEY_WORDS] = [0; KEY_WORDS];
 201         for word in &mut key {
 202             *word = other.gen();
 203         }
 204         SeedableRng::from_seed(&key[..])
 205     }
 206 }
 207
 208
 209 #[cfg(test)]
 210 mod tests {
 211     use std::prelude::v1::*;
 212
 213     use core::iter::order;
 214     use {Rng, SeedableRng};
 215     use super::ChaChaRng;
 216
 217     #[test]
 218     fn test_rng_rand_seeded() {
 219         let s = ::test::rng().gen_iter::<u32>().take(8).collect::<Vec<u32>>();
 220         let mut ra: ChaChaRng = SeedableRng::from_seed(&*s);
 221         let mut rb: ChaChaRng = SeedableRng::from_seed(&*s);
 222         assert!(order::equals(ra.gen_ascii_chars().take(100),
 223                               rb.gen_ascii_chars().take(100)));
 224     }
 225
 226     #[test]
 227     fn test_rng_seeded() {
 228         let seed: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7];
 229         let mut ra: ChaChaRng = SeedableRng::from_seed(seed);
 230         let mut rb: ChaChaRng = SeedableRng::from_seed(seed);
 231         assert!(order::equals(ra.gen_ascii_chars().take(100),
 232                               rb.gen_ascii_chars().take(100)));
 233     }
 234
 235     #[test]
 236     fn test_rng_reseed() {
 237         let s = ::test::rng().gen_iter::<u32>().take(8).collect::<Vec<u32>>();
 238         let mut r: ChaChaRng = SeedableRng::from_seed(&*s);
 239         let string1: String = r.gen_ascii_chars().take(100).collect();
 240
 241         r.reseed(&s);
 242
 243         let string2: String = r.gen_ascii_chars().take(100).collect();
 244         assert_eq!(string1, string2);
 245     }
 246
 247     #[test]
 248     fn test_rng_true_values() {
 249         // Test vectors 1 and 2 from
 250         // http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-04
 251         let seed: &[_] = &[0; 8];
 252         let mut ra: ChaChaRng = SeedableRng::from_seed(seed);
 253
 254         let v = (0..16).map(|_| ra.next_u32()).collect::<Vec<_>>();
 255         assert_eq!(v,
 256                    vec!(0xade0b876,
 257                         0x903df1a0,
 258                         0xe56a5d40,
 259                         0x28bd8653,
 260                         0xb819d2bd,
 261                         0x1aed8da0,
 262                         0xccef36a8,
 263                         0xc70d778b,
 264                         0x7c5941da,
 265                         0x8d485751,
 266                         0x3fe02477,
 267                         0x374ad8b8,
 268                         0xf4b8436a,
 269                         0x1ca11815,
 270                         0x69b687c3,
 271                         0x8665eeb2));
 272
 273         let v = (0..16).map(|_| ra.next_u32()).collect::<Vec<_>>();
 274         assert_eq!(v,
 275                    vec!(0xbee7079f,
 276                         0x7a385155,
 277                         0x7c97ba98,
 278                         0x0d082d73,
 279                         0xa0290fcb,
 280                         0x6965e348,
 281                         0x3e53c612,
 282                         0xed7aee32,
 283                         0x7621b729,
 284                         0x434ee69c,
 285                         0xb03371d5,
 286                         0xd539d874,
 287                         0x281fed31,
 288                         0x45fb0a51,
 289                         0x1f0ae1ac,
 290                         0x6f4d794b));
 291
 292
 293         let seed: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7];
 294         let mut ra: ChaChaRng = SeedableRng::from_seed(seed);
 295
 296         // Store the 17*i-th 32-bit word,
 297         // i.e., the i-th word of the i-th 16-word block
 298         let mut v: Vec<u32> = Vec::new();
 299         for _ in 0..16 {
 300             v.push(ra.next_u32());
 301             for _ in 0..16 {
 302                 ra.next_u32();
 303             }
 304         }
 305
 306         assert_eq!(v,
 307                    vec!(0xf225c81a,
 308                         0x6ab1be57,
 309                         0x04d42951,
 310                         0x70858036,
 311                         0x49884684,
 312                         0x64efec72,
 313                         0x4be2d186,
 314                         0x3615b384,
 315                         0x11cfa18e,
 316                         0xd3c50049,
 317                         0x75c775f6,
 318                         0x434c6530,
 319                         0x2c5bad8f,
 320                         0x898881dc,
 321                         0x5f1c86d9,
 322                         0xc1f8e7f4));
 323     }
 324
 325     #[test]
 326     fn test_rng_clone() {
 327         let seed: &[_] = &[0; 8];
 328         let mut rng: ChaChaRng = SeedableRng::from_seed(seed);
 329         let mut clone = rng.clone();
 330         for _ in 0..16 {
 331             assert_eq!(rng.next_u64(), clone.next_u64());
 332         }
 333     }
 334 }