May 12, 2022

The Random Number Generator Hidden In Rust's Standard Library

Hidden inside std::collections::hash_map is a struct called RandomState. It's job is to initialize a DefaultHasher with a random seed for use in a HashMap. It turns out that if you create a random DefaultHasher and extract the final hash without actually hashing anything, you can get the seed value:

fn rand() -> u64 {
    RandomState::new().build_hasher().finish()
}

fn main() {
    for _ in 0..5 {
        println!("{}", rand());
    }
}
13850751674286760248
45510352149189357
6403375774259711286
1678796842412519869
12232603414372688969

Rust actually does have a random number generator in it's standard library :)


Under the hood RandomState doesn't actually generate a random number every time. It instead cache one per thread and increments it:

impl RandomState {
    /// Constructs a new `RandomState` that is initialized with random keys.
    pub fn new() -> RandomState {
        thread_local!(static KEYS: Cell<(u64, u64)> = {
            Cell::new(sys::hashmap_random_keys())
        });

        KEYS.with(|keys| {
            let (k0, k1) = keys.get();
            keys.set((k0.wrapping_add(1), k1));
            RandomState { k0, k1 }
        })
    }
}

The seed is fetched from the operating system's source of entropy. On Linux this is done through the getrandom function:

pub fn hashmap_random_keys() -> (u64, u64) {
    let mut v = (0, 0);
    unsafe {
        let view = slice::from_raw_parts_mut(&mut v as *mut _ as *mut u8, mem::size_of_val(&v));

        let mut read = 0;
        while read < view.len() {
            let result = libc::getrandom(view[read..].as_mut_ptr().cast(), view.len());
            read += result;
        }
    }
    v
}

This seed is then hashed with SipHasher13, HashMaps default hasher, making it a nice psuedo random number generator:

impl hash::Hasher for SipHasher {
    // ...
    fn finish(&self) -> u64 {
        let mut state = self.state;

        let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;

        state.v3 ^= b;
        Sip13Rounds::c_rounds(&mut state);
        state.v0 ^= b;

        state.v2 ^= 0xff;
        Sip13Rounds::d_rounds(&mut state);

        state.v0 ^ state.v1 ^ state.v2 ^ state.v3
    }
}