deterministic.rs

use super::{Random, RandomSource};
use crate::fmt::{self, Debug};

/// A seeded, insecure random number generator.
///
/// **DO NOT USE THIS FOR CRYPTOGRAPHY PURPOSES! EVER! NO, YOUR USECASE IS NOT
/// SPECIAL! IF YOU USE THIS IN SECURITY-SENSITIVE CONTEXTS, FERRIS WILL BE
/// ZOMBIFIED AND EAT YOU ALIVE!**
///
/// If you require secure randomness, use `DefaultRandomSource` instead. In
/// particular, this source:
/// * Does *not* provide forward secrecy, so key compromise will result in *all*
///   output being predictable.
/// * Is *vulnerable* to side-channel attacks such as timing based attacks.
/// * Does *not* reseed on `fork`, VM fork, or in similar scenarios, meaning the
///   generated bytes will be the same.
///
/// That said, if you do *not* need security, this ChaCha8-based [`RandomSource`]
/// can be used to quickly generate good-quality, deterministic random data
/// usable for purposes such as Monte-Carlo integration, video game RNG, etc.
///
/// # Stability
///
/// This random source is guaranteed to always produce the same bytes from a
/// given seed, irrespective of the platform or Rust version.
///
/// # Examples
///
/// Test if a coin flip is fair by simulating it 100 times:
/// ```rust
/// #![feature(random, deterministic_random_chacha8)]
///
/// use std::random::{DeterministicRandomSource, Random};
///
/// // Seed chosen by fair dice roll. Guaranteed to be random.
/// let mut rng = DeterministicRandomSource::from_seed([4; 32]);
///
/// let mut heads = 0usize;
/// for _ in 0..100 {
///     if bool::random(&mut rng) {
///         heads += 1;
///     }
/// }
///
/// // With a confidence of one standard deviation, the number of heads of
/// // will be within this range:
/// assert!(heads.abs_diff(50) < 20);
/// ```
///
/// A Monty-Hall-problem-inspired game:
/// ```rust,no_run
/// #![feature(random, deterministic_random_chacha8)]
///
/// use std::io::stdin;
/// use std::random::{DefaultRandomSource, DeterministicRandomSource, Random};
///
/// // Use a random seed so that the generated numbers will be different every
/// // time the program is run.
/// let mut rng = DeterministicRandomSource::random(&mut DefaultRandomSource);
///
/// // Pick a random door, avoiding bias.
/// let door = loop {
///     let num = u8::random(&mut rng);
///     if num < 255 {
///         break num % 3;
///     }
/// };
///
/// let mut input = stdin().lines().map(Result::unwrap);
/// let guess = loop {
///     println!("Pick a door from 1, 2 or 3:");
///     match input.next().as_deref() {
///         Some("1") => break 0,
///         Some("2") => break 1,
///         Some("3") => break 2,
///         _ => println!("That's not a valid door"),
///     }
/// };
///
/// let reveal = match (guess, door) {
///     // Choose which door the moderator must open.
///     // Since both unpicked doors contain a goat, we decide by fair coin flip.
///     (0, 0) | (1, 1) | (2, 2) => {
///         let diceroll = bool::random(&mut rng) as u8;
///         (door + diceroll) % 3
///     }
///     (0, 1) | (1, 0) => 2,
///     (0, 2) | (2, 0) => 1,
///     (1, 2) | (2, 1) => 0,
///     _ => unreachable!(),
/// };
/// println!("Door {} contains a goat. Do you want to change your guess (y/n)?", reveal + 1);
///
/// let guess = loop {
///     match input.next().as_deref() {
///         Some("y") => break match (guess, reveal) {
///             (0, 1) | (1, 0) => 2,
///             (0, 2) | (2, 0) => 1,
///             (1, 2) | (2, 1) => 0,
///             _ => unreachable!(),
///         },
///         Some("n") => break guess,
///         _ => println!("Well, what? Answer with either yes (y) or no (n)."),
///     }
/// };
///
/// if guess == door {
///     println!("Congratulations, you won a bike for Ferris (also known as a Ferris-wheel)!");
/// } else {
///     println!("Congratulations, you won a goat! You did not want a goat? Well, better luck next time ;-).");
/// }
/// ```
#[unstable(feature = "deterministic_random_chacha8", issue = "131606")]
pub struct DeterministicRandomSource {
    seed: [u8; 32],
    // We use both the 32-bit counter and the 96-bit nonce from the RFC as
    // block counter, resulting in a 128-bit counter that will realistically
    // never roll over.
    counter_nonce: u128,
    block: [u8; chacha::BLOCK_SIZE],
    // The amount of bytes in block that were already used.
    used: usize,
}

/// Implements the ChaCha block function as defined by
/// [RFC 8439](https://datatracker.ietf.org/doc/html/rfc8439).
#[doc(hidden)]
#[unstable(feature = "deterministic_random_internals", issue = "none")] // Used for testing only.
pub mod chacha {
    pub const BLOCK_SIZE: usize = 64;

    pub const fn quarter_round(
        mut a: u32,
        mut b: u32,
        mut c: u32,
        mut d: u32,
    ) -> (u32, u32, u32, u32) {
        a = a.wrapping_add(b);
        d ^= a;
        d = d.rotate_left(16);

        c = c.wrapping_add(d);
        b ^= c;
        b = b.rotate_left(12);

        a = a.wrapping_add(b);
        d ^= a;
        d = d.rotate_left(8);

        c = c.wrapping_add(d);
        b ^= c;
        b = b.rotate_left(7);

        (a, b, c, d)
    }

    pub fn block(key: &[u8; 32], counter_nonce: u128, rounds: u32) -> [u8; BLOCK_SIZE] {
        assert!(rounds % 2 == 0);

        let mut state = [0; 16];
        state[0] = 0x61707865;
        state[1] = 0x3320646e;
        state[2] = 0x79622d32;
        state[3] = 0x6b206574;

        for (i, word) in key.array_chunks().enumerate() {
            state[4 + i] = u32::from_le_bytes(*word);
        }

        state[12] = (counter_nonce >> 0) as u32;
        state[13] = (counter_nonce >> 32) as u32;
        state[14] = (counter_nonce >> 64) as u32;
        state[15] = (counter_nonce >> 96) as u32;

        let mut block = state;
        let mut qr = |a, b, c, d| {
            let res = quarter_round(block[a], block[b], block[c], block[d]);
            block[a] = res.0;
            block[b] = res.1;
            block[c] = res.2;
            block[d] = res.3;
        };

        for _ in 0..rounds / 2 {
            qr(0, 4, 8, 12);
            qr(1, 5, 9, 13);
            qr(2, 6, 10, 14);
            qr(3, 7, 11, 15);

            qr(0, 5, 10, 15);
            qr(1, 6, 11, 12);
            qr(2, 7, 8, 13);
            qr(3, 4, 9, 14);
        }

        let mut out = [0; BLOCK_SIZE];
        for i in 0..16 {
            out[4 * i..][..4].copy_from_slice(&block[i].wrapping_add(state[i]).to_le_bytes());
        }

        out
    }
}

impl DeterministicRandomSource {
    const ROUNDS: u32 = 8;

    /// Creates a new random source with the given seed.
    ///
    /// # Example
    ///
    /// ```rust
    /// #![feature(deterministic_random_chacha8, random)]
    ///
    /// use std::random::{DeterministicRandomSource, Random};
    ///
    /// let mut rng = DeterministicRandomSource::from_seed([42; 32]);
    /// let num = i32::random(&mut rng);
    /// assert_eq!(num, 1325358262);
    /// ```
    #[unstable(feature = "deterministic_random_chacha8", issue = "131606")]
    pub const fn from_seed(seed: [u8; 32]) -> DeterministicRandomSource {
        DeterministicRandomSource {
            seed,
            counter_nonce: 0,
            block: [0; chacha::BLOCK_SIZE],
            used: chacha::BLOCK_SIZE,
        }
    }

    /// Returns the seed this random source was initialized with.
    ///
    /// # Example
    ///
    /// ```rust
    /// #![feature(deterministic_random_chacha8)]
    ///
    /// use std::random::DeterministicRandomSource;
    ///
    /// let rng = DeterministicRandomSource::from_seed([4; 32]);
    /// assert_eq!(rng.seed(), &[4; 32]);
    /// ```
    #[unstable(feature = "deterministic_random_chacha8", issue = "131606")]
    pub const fn seed(&self) -> &[u8; 32] {
        &self.seed
    }

    fn next_block(&mut self) -> [u8; chacha::BLOCK_SIZE] {
        let block = chacha::block(&self.seed, self.counter_nonce, Self::ROUNDS);
        self.counter_nonce = self.counter_nonce.wrapping_add(1);
        block
    }
}

#[unstable(feature = "deterministic_random_chacha8", issue = "131606")]
impl RandomSource for DeterministicRandomSource {
    fn fill_bytes(&mut self, mut bytes: &mut [u8]) {
        if self.used != self.block.len() {
            let len = usize::min(self.block.len() - self.used, bytes.len());
            bytes[..len].copy_from_slice(&self.block[self.used..][..len]);
            bytes = &mut bytes[len..];
            self.used += len;
        }

        let mut blocks = bytes.array_chunks_mut::<{ chacha::BLOCK_SIZE }>();
        for block in &mut blocks {
            block.copy_from_slice(&self.next_block());
        }

        let bytes = blocks.into_remainder();
        if !bytes.is_empty() {
            self.block = self.next_block();
            bytes.copy_from_slice(&self.block[..bytes.len()]);
            self.used = bytes.len();
        }
    }
}

#[unstable(feature = "deterministic_random_chacha8", issue = "131606")]
impl Random for DeterministicRandomSource {
    fn random(source: &mut (impl RandomSource + ?Sized)) -> DeterministicRandomSource {
        let mut seed = [0; 32];
        source.fill_bytes(&mut seed);
        DeterministicRandomSource::from_seed(seed)
    }
}

#[unstable(feature = "deterministic_random_chacha8", issue = "131606")]
impl Debug for DeterministicRandomSource {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("DeterministcRandomSource").finish_non_exhaustive()
    }
}