1 // Copyright 2018 Developers of the Rand project. 2 // Copyright 2017-2018 The Rust Project Developers. 3 // 4 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or 5 // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license 6 // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your 7 // option. This file may not be copied, modified, or distributed 8 // except according to those terms. 9 10 //! Random number generation traits 11 //! 12 //! This crate is mainly of interest to crates publishing implementations of 13 //! [`RngCore`]. Other users are encouraged to use the [`rand`] crate instead 14 //! which re-exports the main traits and error types. 15 //! 16 //! [`RngCore`] is the core trait implemented by algorithmic pseudo-random number 17 //! generators and external random-number sources. 18 //! 19 //! [`SeedableRng`] is an extension trait for construction from fixed seeds and 20 //! other random number generators. 21 //! 22 //! [`Error`] is provided for error-handling. It is safe to use in `no_std` 23 //! environments. 24 //! 25 //! The [`impls`] and [`le`] sub-modules include a few small functions to assist 26 //! implementation of [`RngCore`]. 27 //! 28 //! [`rand`]: https://docs.rs/rand 29 30 #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk.png", 31 html_favicon_url = "https://www.rust-lang.org/favicon.ico", 32 html_root_url = "https://rust-random.github.io/rand/")] 33 34 #![deny(missing_docs)] 35 #![deny(missing_debug_implementations)] 36 #![doc(test(attr(allow(unused_variables), deny(warnings))))] 37 38 #![allow(clippy::unreadable_literal)] 39 40 #![cfg_attr(not(feature="std"), no_std)] 41 42 43 use core::default::Default; 44 use core::convert::AsMut; 45 use core::ptr::copy_nonoverlapping; 46 47 #[cfg(all(feature="alloc", not(feature="std")))] extern crate alloc; 48 #[cfg(all(feature="alloc", not(feature="std")))] use alloc::boxed::Box; 49 50 pub use error::Error; 51 #[cfg(feature="getrandom")] pub use os::OsRng; 52 53 54 mod error; 55 pub mod block; 56 pub mod impls; 57 pub mod le; 58 #[cfg(feature="getrandom")] mod os; 59 60 61 /// The core of a random number generator. 62 /// 63 /// This trait encapsulates the low-level functionality common to all 64 /// generators, and is the "back end", to be implemented by generators. 65 /// End users should normally use the `Rng` trait from the [`rand`] crate, 66 /// which is automatically implemented for every type implementing `RngCore`. 67 /// 68 /// Three different methods for generating random data are provided since the 69 /// optimal implementation of each is dependent on the type of generator. There 70 /// is no required relationship between the output of each; e.g. many 71 /// implementations of [`fill_bytes`] consume a whole number of `u32` or `u64` 72 /// values and drop any remaining unused bytes. 73 /// 74 /// The [`try_fill_bytes`] method is a variant of [`fill_bytes`] allowing error 75 /// handling; it is not deemed sufficiently useful to add equivalents for 76 /// [`next_u32`] or [`next_u64`] since the latter methods are almost always used 77 /// with algorithmic generators (PRNGs), which are normally infallible. 78 /// 79 /// Algorithmic generators implementing [`SeedableRng`] should normally have 80 /// *portable, reproducible* output, i.e. fix Endianness when converting values 81 /// to avoid platform differences, and avoid making any changes which affect 82 /// output (except by communicating that the release has breaking changes). 83 /// 84 /// Typically implementators will implement only one of the methods available 85 /// in this trait directly, then use the helper functions from the 86 /// [`impls`] module to implement the other methods. 87 /// 88 /// It is recommended that implementations also implement: 89 /// 90 /// - `Debug` with a custom implementation which *does not* print any internal 91 /// state (at least, [`CryptoRng`]s should not risk leaking state through 92 /// `Debug`). 93 /// - `Serialize` and `Deserialize` (from Serde), preferably making Serde 94 /// support optional at the crate level in PRNG libs. 95 /// - `Clone`, if possible. 96 /// - *never* implement `Copy` (accidental copies may cause repeated values). 97 /// - *do not* implement `Default` for pseudorandom generators, but instead 98 /// implement [`SeedableRng`], to guide users towards proper seeding. 99 /// External / hardware RNGs can choose to implement `Default`. 100 /// - `Eq` and `PartialEq` could be implemented, but are probably not useful. 101 /// 102 /// # Example 103 /// 104 /// A simple example, obviously not generating very *random* output: 105 /// 106 /// ``` 107 /// #![allow(dead_code)] 108 /// use rand_core::{RngCore, Error, impls}; 109 /// 110 /// struct CountingRng(u64); 111 /// 112 /// impl RngCore for CountingRng { 113 /// fn next_u32(&mut self) -> u32 { 114 /// self.next_u64() as u32 115 /// } 116 /// 117 /// fn next_u64(&mut self) -> u64 { 118 /// self.0 += 1; 119 /// self.0 120 /// } 121 /// 122 /// fn fill_bytes(&mut self, dest: &mut [u8]) { 123 /// impls::fill_bytes_via_next(self, dest) 124 /// } 125 /// 126 /// fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> { 127 /// Ok(self.fill_bytes(dest)) 128 /// } 129 /// } 130 /// ``` 131 /// 132 /// [`rand`]: https://docs.rs/rand 133 /// [`try_fill_bytes`]: RngCore::try_fill_bytes 134 /// [`fill_bytes`]: RngCore::fill_bytes 135 /// [`next_u32`]: RngCore::next_u32 136 /// [`next_u64`]: RngCore::next_u64 137 pub trait RngCore { 138 /// Return the next random `u32`. 139 /// 140 /// RNGs must implement at least one method from this trait directly. In 141 /// the case this method is not implemented directly, it can be implemented 142 /// using `self.next_u64() as u32` or via 143 /// [`fill_bytes`](impls::next_u32_via_fill). next_u32(&mut self) -> u32144 fn next_u32(&mut self) -> u32; 145 146 /// Return the next random `u64`. 147 /// 148 /// RNGs must implement at least one method from this trait directly. In 149 /// the case this method is not implemented directly, it can be implemented 150 /// via [`next_u32`](impls::next_u64_via_u32) or via 151 /// [`fill_bytes`](impls::next_u64_via_fill). next_u64(&mut self) -> u64152 fn next_u64(&mut self) -> u64; 153 154 /// Fill `dest` with random data. 155 /// 156 /// RNGs must implement at least one method from this trait directly. In 157 /// the case this method is not implemented directly, it can be implemented 158 /// via [`next_u*`](impls::fill_bytes_via_next) or 159 /// via [`try_fill_bytes`](RngCore::try_fill_bytes); if this generator can 160 /// fail the implementation must choose how best to handle errors here 161 /// (e.g. panic with a descriptive message or log a warning and retry a few 162 /// times). 163 /// 164 /// This method should guarantee that `dest` is entirely filled 165 /// with new data, and may panic if this is impossible 166 /// (e.g. reading past the end of a file that is being used as the 167 /// source of randomness). fill_bytes(&mut self, dest: &mut [u8])168 fn fill_bytes(&mut self, dest: &mut [u8]); 169 170 /// Fill `dest` entirely with random data. 171 /// 172 /// This is the only method which allows an RNG to report errors while 173 /// generating random data thus making this the primary method implemented 174 /// by external (true) RNGs (e.g. `OsRng`) which can fail. It may be used 175 /// directly to generate keys and to seed (infallible) PRNGs. 176 /// 177 /// Other than error handling, this method is identical to [`fill_bytes`]; 178 /// thus this may be implemented using `Ok(self.fill_bytes(dest))` or 179 /// `fill_bytes` may be implemented with 180 /// `self.try_fill_bytes(dest).unwrap()` or more specific error handling. 181 /// 182 /// [`fill_bytes`]: RngCore::fill_bytes try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error>183 fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error>; 184 } 185 186 /// A marker trait used to indicate that an [`RngCore`] or [`BlockRngCore`] 187 /// implementation is supposed to be cryptographically secure. 188 /// 189 /// *Cryptographically secure generators*, also known as *CSPRNGs*, should 190 /// satisfy an additional properties over other generators: given the first 191 /// *k* bits of an algorithm's output 192 /// sequence, it should not be possible using polynomial-time algorithms to 193 /// predict the next bit with probability significantly greater than 50%. 194 /// 195 /// Some generators may satisfy an additional property, however this is not 196 /// required by this trait: if the CSPRNG's state is revealed, it should not be 197 /// computationally-feasible to reconstruct output prior to this. Some other 198 /// generators allow backwards-computation and are consided *reversible*. 199 /// 200 /// Note that this trait is provided for guidance only and cannot guarantee 201 /// suitability for cryptographic applications. In general it should only be 202 /// implemented for well-reviewed code implementing well-regarded algorithms. 203 /// 204 /// Note also that use of a `CryptoRng` does not protect against other 205 /// weaknesses such as seeding from a weak entropy source or leaking state. 206 /// 207 /// [`BlockRngCore`]: block::BlockRngCore 208 pub trait CryptoRng {} 209 210 /// A random number generator that can be explicitly seeded. 211 /// 212 /// This trait encapsulates the low-level functionality common to all 213 /// pseudo-random number generators (PRNGs, or algorithmic generators). 214 /// 215 /// [`rand`]: https://docs.rs/rand 216 pub trait SeedableRng: Sized { 217 /// Seed type, which is restricted to types mutably-dereferencable as `u8` 218 /// arrays (we recommend `[u8; N]` for some `N`). 219 /// 220 /// It is recommended to seed PRNGs with a seed of at least circa 100 bits, 221 /// which means an array of `[u8; 12]` or greater to avoid picking RNGs with 222 /// partially overlapping periods. 223 /// 224 /// For cryptographic RNG's a seed of 256 bits is recommended, `[u8; 32]`. 225 /// 226 /// 227 /// # Implementing `SeedableRng` for RNGs with large seeds 228 /// 229 /// Note that the required traits `core::default::Default` and 230 /// `core::convert::AsMut<u8>` are not implemented for large arrays 231 /// `[u8; N]` with `N` > 32. To be able to implement the traits required by 232 /// `SeedableRng` for RNGs with such large seeds, the newtype pattern can be 233 /// used: 234 /// 235 /// ``` 236 /// use rand_core::SeedableRng; 237 /// 238 /// const N: usize = 64; 239 /// pub struct MyRngSeed(pub [u8; N]); 240 /// pub struct MyRng(MyRngSeed); 241 /// 242 /// impl Default for MyRngSeed { 243 /// fn default() -> MyRngSeed { 244 /// MyRngSeed([0; N]) 245 /// } 246 /// } 247 /// 248 /// impl AsMut<[u8]> for MyRngSeed { 249 /// fn as_mut(&mut self) -> &mut [u8] { 250 /// &mut self.0 251 /// } 252 /// } 253 /// 254 /// impl SeedableRng for MyRng { 255 /// type Seed = MyRngSeed; 256 /// 257 /// fn from_seed(seed: MyRngSeed) -> MyRng { 258 /// MyRng(seed) 259 /// } 260 /// } 261 /// ``` 262 type Seed: Sized + Default + AsMut<[u8]>; 263 264 /// Create a new PRNG using the given seed. 265 /// 266 /// PRNG implementations are allowed to assume that bits in the seed are 267 /// well distributed. That means usually that the number of one and zero 268 /// bits are roughly equal, and values like 0, 1 and (size - 1) are unlikely. 269 /// Note that many non-cryptographic PRNGs will show poor quality output 270 /// if this is not adhered to. If you wish to seed from simple numbers, use 271 /// `seed_from_u64` instead. 272 /// 273 /// All PRNG implementations should be reproducible unless otherwise noted: 274 /// given a fixed `seed`, the same sequence of output should be produced 275 /// on all runs, library versions and architectures (e.g. check endianness). 276 /// Any "value-breaking" changes to the generator should require bumping at 277 /// least the minor version and documentation of the change. 278 /// 279 /// It is not required that this function yield the same state as a 280 /// reference implementation of the PRNG given equivalent seed; if necessary 281 /// another constructor replicating behaviour from a reference 282 /// implementation can be added. 283 /// 284 /// PRNG implementations should make sure `from_seed` never panics. In the 285 /// case that some special values (like an all zero seed) are not viable 286 /// seeds it is preferable to map these to alternative constant value(s), 287 /// for example `0xBAD5EEDu32` or `0x0DDB1A5E5BAD5EEDu64` ("odd biases? bad 288 /// seed"). This is assuming only a small number of values must be rejected. from_seed(seed: Self::Seed) -> Self289 fn from_seed(seed: Self::Seed) -> Self; 290 291 /// Create a new PRNG using a `u64` seed. 292 /// 293 /// This is a convenience-wrapper around `from_seed` to allow construction 294 /// of any `SeedableRng` from a simple `u64` value. It is designed such that 295 /// low Hamming Weight numbers like 0 and 1 can be used and should still 296 /// result in good, independent seeds to the PRNG which is returned. 297 /// 298 /// This **is not suitable for cryptography**, as should be clear given that 299 /// the input size is only 64 bits. 300 /// 301 /// Implementations for PRNGs *may* provide their own implementations of 302 /// this function, but the default implementation should be good enough for 303 /// all purposes. *Changing* the implementation of this function should be 304 /// considered a value-breaking change. seed_from_u64(mut state: u64) -> Self305 fn seed_from_u64(mut state: u64) -> Self { 306 // We use PCG32 to generate a u32 sequence, and copy to the seed 307 const MUL: u64 = 6364136223846793005; 308 const INC: u64 = 11634580027462260723; 309 310 let mut seed = Self::Seed::default(); 311 for chunk in seed.as_mut().chunks_mut(4) { 312 // We advance the state first (to get away from the input value, 313 // in case it has low Hamming Weight). 314 state = state.wrapping_mul(MUL).wrapping_add(INC); 315 316 // Use PCG output function with to_le to generate x: 317 let xorshifted = (((state >> 18) ^ state) >> 27) as u32; 318 let rot = (state >> 59) as u32; 319 let x = xorshifted.rotate_right(rot).to_le(); 320 321 unsafe { 322 let p = &x as *const u32 as *const u8; 323 copy_nonoverlapping(p, chunk.as_mut_ptr(), chunk.len()); 324 } 325 } 326 327 Self::from_seed(seed) 328 } 329 330 /// Create a new PRNG seeded from another `Rng`. 331 /// 332 /// This may be useful when needing to rapidly seed many PRNGs from a master 333 /// PRNG, and to allow forking of PRNGs. It may be considered deterministic. 334 /// 335 /// The master PRNG should be at least as high quality as the child PRNGs. 336 /// When seeding non-cryptographic child PRNGs, we recommend using a 337 /// different algorithm for the master PRNG (ideally a CSPRNG) to avoid 338 /// correlations between the child PRNGs. If this is not possible (e.g. 339 /// forking using small non-crypto PRNGs) ensure that your PRNG has a good 340 /// mixing function on the output or consider use of a hash function with 341 /// `from_seed`. 342 /// 343 /// Note that seeding `XorShiftRng` from another `XorShiftRng` provides an 344 /// extreme example of what can go wrong: the new PRNG will be a clone 345 /// of the parent. 346 /// 347 /// PRNG implementations are allowed to assume that a good RNG is provided 348 /// for seeding, and that it is cryptographically secure when appropriate. 349 /// As of `rand` 0.7 / `rand_core` 0.5, implementations overriding this 350 /// method should ensure the implementation satisfies reproducibility 351 /// (in prior versions this was not required). 352 /// 353 /// [`rand`]: https://docs.rs/rand 354 /// [`rand_os`]: https://docs.rs/rand_os from_rng<R: RngCore>(mut rng: R) -> Result<Self, Error>355 fn from_rng<R: RngCore>(mut rng: R) -> Result<Self, Error> { 356 let mut seed = Self::Seed::default(); 357 rng.try_fill_bytes(seed.as_mut())?; 358 Ok(Self::from_seed(seed)) 359 } 360 361 /// Creates a new instance of the RNG seeded via [`getrandom`]. 362 /// 363 /// This method is the recommended way to construct non-deterministic PRNGs 364 /// since it is convenient and secure. 365 /// 366 /// In case the overhead of using [`getrandom`] to seed *many* PRNGs is an 367 /// issue, one may prefer to seed from a local PRNG, e.g. 368 /// `from_rng(thread_rng()).unwrap()`. 369 /// 370 /// # Panics 371 /// 372 /// If [`getrandom`] is unable to provide secure entropy this method will panic. 373 /// 374 /// [`getrandom`]: https://docs.rs/getrandom 375 #[cfg(feature="getrandom")] from_entropy() -> Self376 fn from_entropy() -> Self { 377 let mut seed = Self::Seed::default(); 378 if let Err(err) = getrandom::getrandom(seed.as_mut()) { 379 panic!("from_entropy failed: {}", err); 380 } 381 Self::from_seed(seed) 382 } 383 } 384 385 // Implement `RngCore` for references to an `RngCore`. 386 // Force inlining all functions, so that it is up to the `RngCore` 387 // implementation and the optimizer to decide on inlining. 388 impl<'a, R: RngCore + ?Sized> RngCore for &'a mut R { 389 #[inline(always)] next_u32(&mut self) -> u32390 fn next_u32(&mut self) -> u32 { 391 (**self).next_u32() 392 } 393 394 #[inline(always)] next_u64(&mut self) -> u64395 fn next_u64(&mut self) -> u64 { 396 (**self).next_u64() 397 } 398 399 #[inline(always)] fill_bytes(&mut self, dest: &mut [u8])400 fn fill_bytes(&mut self, dest: &mut [u8]) { 401 (**self).fill_bytes(dest) 402 } 403 404 #[inline(always)] try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error>405 fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> { 406 (**self).try_fill_bytes(dest) 407 } 408 } 409 410 // Implement `RngCore` for boxed references to an `RngCore`. 411 // Force inlining all functions, so that it is up to the `RngCore` 412 // implementation and the optimizer to decide on inlining. 413 #[cfg(feature="alloc")] 414 impl<R: RngCore + ?Sized> RngCore for Box<R> { 415 #[inline(always)] next_u32(&mut self) -> u32416 fn next_u32(&mut self) -> u32 { 417 (**self).next_u32() 418 } 419 420 #[inline(always)] next_u64(&mut self) -> u64421 fn next_u64(&mut self) -> u64 { 422 (**self).next_u64() 423 } 424 425 #[inline(always)] fill_bytes(&mut self, dest: &mut [u8])426 fn fill_bytes(&mut self, dest: &mut [u8]) { 427 (**self).fill_bytes(dest) 428 } 429 430 #[inline(always)] try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error>431 fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> { 432 (**self).try_fill_bytes(dest) 433 } 434 } 435 436 #[cfg(feature="std")] 437 impl std::io::Read for dyn RngCore { read(&mut self, buf: &mut [u8]) -> Result<usize, std::io::Error>438 fn read(&mut self, buf: &mut [u8]) -> Result<usize, std::io::Error> { 439 self.try_fill_bytes(buf)?; 440 Ok(buf.len()) 441 } 442 } 443 444 // Implement `CryptoRng` for references to an `CryptoRng`. 445 impl<'a, R: CryptoRng + ?Sized> CryptoRng for &'a mut R {} 446 447 // Implement `CryptoRng` for boxed references to an `CryptoRng`. 448 #[cfg(feature="alloc")] 449 impl<R: CryptoRng + ?Sized> CryptoRng for Box<R> {} 450 451 #[cfg(test)] 452 mod test { 453 use super::*; 454 455 #[test] test_seed_from_u64()456 fn test_seed_from_u64() { 457 struct SeedableNum(u64); 458 impl SeedableRng for SeedableNum { 459 type Seed = [u8; 8]; 460 fn from_seed(seed: Self::Seed) -> Self { 461 let mut x = [0u64; 1]; 462 le::read_u64_into(&seed, &mut x); 463 SeedableNum(x[0]) 464 } 465 } 466 467 const N: usize = 8; 468 const SEEDS: [u64; N] = [0u64, 1, 2, 3, 4, 8, 16, -1i64 as u64]; 469 let mut results = [0u64; N]; 470 for (i, seed) in SEEDS.iter().enumerate() { 471 let SeedableNum(x) = SeedableNum::seed_from_u64(*seed); 472 results[i] = x; 473 } 474 475 for (i1, r1) in results.iter().enumerate() { 476 let weight = r1.count_ones(); 477 // This is the binomial distribution B(64, 0.5), so chance of 478 // weight < 20 is binocdf(19, 64, 0.5) = 7.8e-4, and same for 479 // weight > 44. 480 assert!(weight >= 20 && weight <= 44); 481 482 for (i2, r2) in results.iter().enumerate() { 483 if i1 == i2 { continue; } 484 let diff_weight = (r1 ^ r2).count_ones(); 485 assert!(diff_weight >= 20); 486 } 487 } 488 489 // value-breakage test: 490 assert_eq!(results[0], 5029875928683246316); 491 } 492 } 493