vendor/rand_chacha/src/chacha.rs

   1 // Copyright 2018 Developers of the Rand project.
   2 //
   3 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   4 // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   5 // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
   6 // option. This file may not be copied, modified, or distributed
   7 // except according to those terms.
   8
   9 //! The ChaCha random number generator.
  10
  11 #[cfg(not(feature = "std"))] use core;
  12 #[cfg(feature = "std")] use std as core;
  13
  14 use self::core::fmt;
  15 use crate::guts::ChaCha;
  16 use rand_core::block::{BlockRng, BlockRngCore};
  17 use rand_core::{CryptoRng, Error, RngCore, SeedableRng};
  18
  19 const STREAM_PARAM_NONCE: u32 = 1;
  20 const STREAM_PARAM_BLOCK: u32 = 0;
  21
  22 pub struct Array64<T>([T; 64]);
  23 impl<T> Default for Array64<T>
  24 where T: Default
  25 {
  26     #[rustfmt::skip]
  27     fn default() -> Self {
  28         Self([
  29             T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(),
  30             T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(),
  31             T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(),
  32             T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(),
  33             T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(),
  34             T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(),
  35             T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(),
  36             T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(),
  37         ])
  38     }
  39 }
  40 impl<T> AsRef<[T]> for Array64<T> {
  41     fn as_ref(&self) -> &[T] {
  42         &self.0
  43     }
  44 }
  45 impl<T> AsMut<[T]> for Array64<T> {
  46     fn as_mut(&mut self) -> &mut [T] {
  47         &mut self.0
  48     }
  49 }
  50 impl<T> Clone for Array64<T>
  51 where T: Copy + Default
  52 {
  53     fn clone(&self) -> Self {
  54         let mut new = Self::default();
  55         new.0.copy_from_slice(&self.0);
  56         new
  57     }
  58 }
  59 impl<T> fmt::Debug for Array64<T> {
  60     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  61         write!(f, "Array64 {{}}")
  62     }
  63 }
  64
  65 macro_rules! chacha_impl {
  66     ($ChaChaXCore:ident, $ChaChaXRng:ident, $rounds:expr, $doc:expr) => {
  67         #[doc=$doc]
  68         #[derive(Clone)]
  69         pub struct $ChaChaXCore {
  70             state: ChaCha,
  71         }
  72
  73         // Custom Debug implementation that does not expose the internal state
  74         impl fmt::Debug for $ChaChaXCore {
  75             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  76                 write!(f, "ChaChaXCore {{}}")
  77             }
  78         }
  79
  80         impl BlockRngCore for $ChaChaXCore {
  81             type Item = u32;
  82             type Results = Array64<u32>;
  83             #[inline]
  84             fn generate(&mut self, r: &mut Self::Results) {
  85                 // Fill slice of words by writing to equivalent slice of bytes, then fixing endianness.
  86                 self.state.refill4($rounds, unsafe {
  87                     &mut *(&mut *r as *mut Array64<u32> as *mut [u8; 256])
  88                 });
  89                 for x in r.as_mut() {
  90                     *x = x.to_le();
  91                 }
  92             }
  93         }
  94
  95         impl SeedableRng for $ChaChaXCore {
  96             type Seed = [u8; 32];
  97             #[inline]
  98             fn from_seed(seed: Self::Seed) -> Self {
  99                 $ChaChaXCore { state: ChaCha::new(&seed, &[0u8; 8]) }
 100             }
 101         }
 102
 103         impl CryptoRng for $ChaChaXCore {}
 104
 105         /// A cryptographically secure random number generator that uses the ChaCha algorithm.
 106         ///
 107         /// ChaCha is a stream cipher designed by Daniel J. Bernstein[^1], that we use as an RNG. It is
 108         /// an improved variant of the Salsa20 cipher family, which was selected as one of the "stream
 109         /// ciphers suitable for widespread adoption" by eSTREAM[^2].
 110         ///
 111         /// ChaCha uses add-rotate-xor (ARX) operations as its basis. These are safe against timing
 112         /// attacks, although that is mostly a concern for ciphers and not for RNGs. We provide a SIMD
 113         /// implementation to support high throughput on a variety of common hardware platforms.
 114         ///
 115         /// With the ChaCha algorithm it is possible to choose the number of rounds the core algorithm
 116         /// should run. The number of rounds is a tradeoff between performance and security, where 8
 117         /// rounds is the minimum potentially secure configuration, and 20 rounds is widely used as a
 118         /// conservative choice.
 119         ///
 120         /// We use a 64-bit counter and 64-bit stream identifier as in Bernstein's implementation[^1]
 121         /// except that we use a stream identifier in place of a nonce. A 64-bit counter over 64-byte
 122         /// (16 word) blocks allows 1 ZiB of output before cycling, and the stream identifier allows
 123         /// 2<sup>64</sup> unique streams of output per seed. Both counter and stream are initialized
 124         /// to zero but may be set via the `set_word_pos` and `set_stream` methods.
 125         ///
 126         /// The word layout is:
 127         ///
 128         /// ```text
 129         /// constant  constant  constant  constant
 130         /// seed      seed      seed      seed
 131         /// seed      seed      seed      seed
 132         /// counter   counter   stream_id stream_id
 133         /// ```
 134         ///
 135         /// This implementation uses an output buffer of sixteen `u32` words, and uses
 136         /// [`BlockRng`] to implement the [`RngCore`] methods.
 137         ///
 138         /// [^1]: D. J. Bernstein, [*ChaCha, a variant of Salsa20*](
 139         ///       https://cr.yp.to/chacha.html)
 140         ///
 141         /// [^2]: [eSTREAM: the ECRYPT Stream Cipher Project](
 142         ///       http://www.ecrypt.eu.org/stream/)
 143         #[derive(Clone, Debug)]
 144         pub struct $ChaChaXRng {
 145             rng: BlockRng<$ChaChaXCore>,
 146         }
 147
 148         impl SeedableRng for $ChaChaXRng {
 149             type Seed = [u8; 32];
 150             #[inline]
 151             fn from_seed(seed: Self::Seed) -> Self {
 152                 let core = $ChaChaXCore::from_seed(seed);
 153                 Self {
 154                     rng: BlockRng::new(core),
 155                 }
 156             }
 157         }
 158
 159         impl RngCore for $ChaChaXRng {
 160             #[inline]
 161             fn next_u32(&mut self) -> u32 {
 162                 self.rng.next_u32()
 163             }
 164             #[inline]
 165             fn next_u64(&mut self) -> u64 {
 166                 self.rng.next_u64()
 167             }
 168             #[inline]
 169             fn fill_bytes(&mut self, bytes: &mut [u8]) {
 170                 self.rng.fill_bytes(bytes)
 171             }
 172             #[inline]
 173             fn try_fill_bytes(&mut self, bytes: &mut [u8]) -> Result<(), Error> {
 174                 self.rng.try_fill_bytes(bytes)
 175             }
 176         }
 177
 178         impl $ChaChaXRng {
 179             // The buffer is a 4-block window, i.e. it is always at a block-aligned position in the
 180             // stream but if the stream has been seeked it may not be self-aligned.
 181
 182             /// Get the offset from the start of the stream, in 32-bit words.
 183             ///
 184             /// Since the generated blocks are 16 words (2<sup>4</sup>) long and the
 185             /// counter is 64-bits, the offset is a 68-bit number. Sub-word offsets are
 186             /// not supported, hence the result can simply be multiplied by 4 to get a
 187             /// byte-offset.
 188             #[inline]
 189             pub fn get_word_pos(&self) -> u128 {
 190                 let mut block = u128::from(self.rng.core.state.get_stream_param(STREAM_PARAM_BLOCK));
 191                 // counter is incremented *after* filling buffer
 192                 block -= 4;
 193                 (block << 4) + self.rng.index() as u128
 194             }
 195
 196             /// Set the offset from the start of the stream, in 32-bit words.
 197             ///
 198             /// As with `get_word_pos`, we use a 68-bit number. Since the generator
 199             /// simply cycles at the end of its period (1 ZiB), we ignore the upper
 200             /// 60 bits.
 201             #[inline]
 202             pub fn set_word_pos(&mut self, word_offset: u128) {
 203                 let block = (word_offset >> 4) as u64;
 204                 self.rng
 205                     .core
 206                     .state
 207                     .set_stream_param(STREAM_PARAM_BLOCK, block);
 208                 self.rng.generate_and_set((word_offset & 15) as usize);
 209             }
 210
 211             /// Set the stream number.
 212             ///
 213             /// This is initialized to zero; 2<sup>64</sup> unique streams of output
 214             /// are available per seed/key.
 215             ///
 216             /// Note that in order to reproduce ChaCha output with a specific 64-bit
 217             /// nonce, one can convert that nonce to a `u64` in little-endian fashion
 218             /// and pass to this function. In theory a 96-bit nonce can be used by
 219             /// passing the last 64-bits to this function and using the first 32-bits as
 220             /// the most significant half of the 64-bit counter (which may be set
 221             /// indirectly via `set_word_pos`), but this is not directly supported.
 222             #[inline]
 223             pub fn set_stream(&mut self, stream: u64) {
 224                 self.rng
 225                     .core
 226                     .state
 227                     .set_stream_param(STREAM_PARAM_NONCE, stream);
 228                 if self.rng.index() != 64 {
 229                     let wp = self.get_word_pos();
 230                     self.set_word_pos(wp);
 231                 }
 232             }
 233         }
 234
 235         impl CryptoRng for $ChaChaXRng {}
 236
 237         impl From<$ChaChaXCore> for $ChaChaXRng {
 238             fn from(core: $ChaChaXCore) -> Self {
 239                 $ChaChaXRng {
 240                     rng: BlockRng::new(core),
 241                 }
 242             }
 243         }
 244     }
 245 }
 246
 247 chacha_impl!(ChaCha20Core, ChaCha20Rng, 10, "ChaCha with 20 rounds");
 248 chacha_impl!(ChaCha12Core, ChaCha12Rng, 6, "ChaCha with 12 rounds");
 249 chacha_impl!(ChaCha8Core, ChaCha8Rng, 4, "ChaCha with 8 rounds");
 250
 251 #[cfg(test)]
 252 mod test {
 253     use rand_core::{RngCore, SeedableRng};
 254
 255     type ChaChaRng = super::ChaCha20Rng;
 256
 257     #[test]
 258     fn test_chacha_construction() {
 259         let seed = [
 260             0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0,
 261             0, 0, 0,
 262         ];
 263         let mut rng1 = ChaChaRng::from_seed(seed);
 264         assert_eq!(rng1.next_u32(), 137206642);
 265
 266         let mut rng2 = ChaChaRng::from_rng(rng1).unwrap();
 267         assert_eq!(rng2.next_u32(), 1325750369);
 268     }
 269
 270     #[test]
 271     fn test_chacha_true_values_a() {
 272         // Test vectors 1 and 2 from
 273         // https://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-04
 274         let seed = [0u8; 32];
 275         let mut rng = ChaChaRng::from_seed(seed);
 276
 277         let mut results = [0u32; 16];
 278         for i in results.iter_mut() {
 279             *i = rng.next_u32();
 280         }
 281         let expected = [
 282             0xade0b876, 0x903df1a0, 0xe56a5d40, 0x28bd8653, 0xb819d2bd, 0x1aed8da0, 0xccef36a8,
 283             0xc70d778b, 0x7c5941da, 0x8d485751, 0x3fe02477, 0x374ad8b8, 0xf4b8436a, 0x1ca11815,
 284             0x69b687c3, 0x8665eeb2,
 285         ];
 286         assert_eq!(results, expected);
 287
 288         for i in results.iter_mut() {
 289             *i = rng.next_u32();
 290         }
 291         let expected = [
 292             0xbee7079f, 0x7a385155, 0x7c97ba98, 0x0d082d73, 0xa0290fcb, 0x6965e348, 0x3e53c612,
 293             0xed7aee32, 0x7621b729, 0x434ee69c, 0xb03371d5, 0xd539d874, 0x281fed31, 0x45fb0a51,
 294             0x1f0ae1ac, 0x6f4d794b,
 295         ];
 296         assert_eq!(results, expected);
 297     }
 298
 299     #[test]
 300     fn test_chacha_true_values_b() {
 301         // Test vector 3 from
 302         // https://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-04
 303         let seed = [
 304             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,
 305             0, 0, 1,
 306         ];
 307         let mut rng = ChaChaRng::from_seed(seed);
 308
 309         // Skip block 0
 310         for _ in 0..16 {
 311             rng.next_u32();
 312         }
 313
 314         let mut results = [0u32; 16];
 315         for i in results.iter_mut() {
 316             *i = rng.next_u32();
 317         }
 318         let expected = [
 319             0x2452eb3a, 0x9249f8ec, 0x8d829d9b, 0xddd4ceb1, 0xe8252083, 0x60818b01, 0xf38422b8,
 320             0x5aaa49c9, 0xbb00ca8e, 0xda3ba7b4, 0xc4b592d1, 0xfdf2732f, 0x4436274e, 0x2561b3c8,
 321             0xebdd4aa6, 0xa0136c00,
 322         ];
 323         assert_eq!(results, expected);
 324     }
 325
 326     #[test]
 327     fn test_chacha_true_values_c() {
 328         // Test vector 4 from
 329         // https://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-04
 330         let seed = [
 331             0, 0xff, 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,
 332             0, 0, 0, 0,
 333         ];
 334         let expected = [
 335             0xfb4dd572, 0x4bc42ef1, 0xdf922636, 0x327f1394, 0xa78dea8f, 0x5e269039, 0xa1bebbc1,
 336             0xcaf09aae, 0xa25ab213, 0x48a6b46c, 0x1b9d9bcb, 0x092c5be6, 0x546ca624, 0x1bec45d5,
 337             0x87f47473, 0x96f0992e,
 338         ];
 339         let expected_end = 3 * 16;
 340         let mut results = [0u32; 16];
 341
 342         // Test block 2 by skipping block 0 and 1
 343         let mut rng1 = ChaChaRng::from_seed(seed);
 344         for _ in 0..32 {
 345             rng1.next_u32();
 346         }
 347         for i in results.iter_mut() {
 348             *i = rng1.next_u32();
 349         }
 350         assert_eq!(results, expected);
 351         assert_eq!(rng1.get_word_pos(), expected_end);
 352
 353         // Test block 2 by using `set_word_pos`
 354         let mut rng2 = ChaChaRng::from_seed(seed);
 355         rng2.set_word_pos(2 * 16);
 356         for i in results.iter_mut() {
 357             *i = rng2.next_u32();
 358         }
 359         assert_eq!(results, expected);
 360         assert_eq!(rng2.get_word_pos(), expected_end);
 361
 362         // Test skipping behaviour with other types
 363         let mut buf = [0u8; 32];
 364         rng2.fill_bytes(&mut buf[..]);
 365         assert_eq!(rng2.get_word_pos(), expected_end + 8);
 366         rng2.fill_bytes(&mut buf[0..25]);
 367         assert_eq!(rng2.get_word_pos(), expected_end + 15);
 368         rng2.next_u64();
 369         assert_eq!(rng2.get_word_pos(), expected_end + 17);
 370         rng2.next_u32();
 371         rng2.next_u64();
 372         assert_eq!(rng2.get_word_pos(), expected_end + 20);
 373         rng2.fill_bytes(&mut buf[0..1]);
 374         assert_eq!(rng2.get_word_pos(), expected_end + 21);
 375     }
 376
 377     #[test]
 378     fn test_chacha_multiple_blocks() {
 379         let seed = [
 380             0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 4, 0, 0, 0, 5, 0, 0, 0, 6, 0, 0, 0, 7,
 381             0, 0, 0,
 382         ];
 383         let mut rng = ChaChaRng::from_seed(seed);
 384
 385         // Store the 17*i-th 32-bit word,
 386         // i.e., the i-th word of the i-th 16-word block
 387         let mut results = [0u32; 16];
 388         for i in results.iter_mut() {
 389             *i = rng.next_u32();
 390             for _ in 0..16 {
 391                 rng.next_u32();
 392             }
 393         }
 394         let expected = [
 395             0xf225c81a, 0x6ab1be57, 0x04d42951, 0x70858036, 0x49884684, 0x64efec72, 0x4be2d186,
 396             0x3615b384, 0x11cfa18e, 0xd3c50049, 0x75c775f6, 0x434c6530, 0x2c5bad8f, 0x898881dc,
 397             0x5f1c86d9, 0xc1f8e7f4,
 398         ];
 399         assert_eq!(results, expected);
 400     }
 401
 402     #[test]
 403     fn test_chacha_true_bytes() {
 404         let seed = [0u8; 32];
 405         let mut rng = ChaChaRng::from_seed(seed);
 406         let mut results = [0u8; 32];
 407         rng.fill_bytes(&mut results);
 408         let expected = [
 409             118, 184, 224, 173, 160, 241, 61, 144, 64, 93, 106, 229, 83, 134, 189, 40, 189, 210,
 410             25, 184, 160, 141, 237, 26, 168, 54, 239, 204, 139, 119, 13, 199,
 411         ];
 412         assert_eq!(results, expected);
 413     }
 414
 415     #[test]
 416     fn test_chacha_nonce() {
 417         // Test vector 5 from
 418         // https://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-04
 419         // Although we do not support setting a nonce, we try it here anyway so
 420         // we can use this test vector.
 421         let seed = [0u8; 32];
 422         let mut rng = ChaChaRng::from_seed(seed);
 423         // 96-bit nonce in LE order is: 0,0,0,0, 0,0,0,0, 0,0,0,2
 424         rng.set_stream(2u64 << (24 + 32));
 425
 426         let mut results = [0u32; 16];
 427         for i in results.iter_mut() {
 428             *i = rng.next_u32();
 429         }
 430         let expected = [
 431             0x374dc6c2, 0x3736d58c, 0xb904e24a, 0xcd3f93ef, 0x88228b1a, 0x96a4dfb3, 0x5b76ab72,
 432             0xc727ee54, 0x0e0e978a, 0xf3145c95, 0x1b748ea8, 0xf786c297, 0x99c28f5f, 0x628314e8,
 433             0x398a19fa, 0x6ded1b53,
 434         ];
 435         assert_eq!(results, expected);
 436     }
 437
 438     #[test]
 439     fn test_chacha_clone_streams() {
 440         let seed = [
 441             0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 4, 0, 0, 0, 5, 0, 0, 0, 6, 0, 0, 0, 7,
 442             0, 0, 0,
 443         ];
 444         let mut rng = ChaChaRng::from_seed(seed);
 445         let mut clone = rng.clone();
 446         for _ in 0..16 {
 447             assert_eq!(rng.next_u64(), clone.next_u64());
 448         }
 449
 450         rng.set_stream(51);
 451         for _ in 0..7 {
 452             assert!(rng.next_u32() != clone.next_u32());
 453         }
 454         clone.set_stream(51); // switch part way through block
 455         for _ in 7..16 {
 456             assert_eq!(rng.next_u32(), clone.next_u32());
 457         }
 458     }
 459 }