commit 49639b282602c5389e30f906f535c29ddaa62308 Author: Isis Lovecruft <isis@torproject.org> Date: Tue Apr 10 19:05:42 2018 +0000 rust: Expose our (P)RNGs in Rust and provide safe wrappers. * FIXES #24660: https://bugs.torproject.org/24660 --- src/rust/Cargo.lock | 18 ++++ src/rust/Cargo.toml | 4 +- src/rust/external/crypto_rand.rs | 95 ++++++++++++++++++++ src/rust/external/lib.rs | 4 +- src/rust/rand/Cargo.toml | 24 +++++ src/rust/rand/lib.rs | 15 ++++ src/rust/rand/prng.rs | 184 +++++++++++++++++++++++++++++++++++++++ src/rust/rand/rng.rs | 94 ++++++++++++++++++++ 8 files changed, 436 insertions(+), 2 deletions(-) diff --git a/src/rust/Cargo.lock b/src/rust/Cargo.lock index 91c0502c6..714e29edc 100644 --- a/src/rust/Cargo.lock +++ b/src/rust/Cargo.lock @@ -23,6 +23,23 @@ dependencies = [ ] [[package]] +name = "rand" +version = "0.0.1" +dependencies = [ + "external 0.0.1", + "libc 0.2.39 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_core 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", + "tor_allocate 0.0.1", + "tor_log 0.1.0", + "tor_util 0.0.1", +] + +[[package]] +name = "rand_core" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] name = "smartlist" version = "0.0.1" dependencies = [ @@ -63,3 +80,4 @@ dependencies = [ [metadata] "checksum libc 0.2.39 (registry+https://github.com/rust-lang/crates.io-index)" = "f54263ad99207254cf58b5f701ecb432c717445ea2ee8af387334bdd1a03fdff" +"checksum rand_core 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "0224284424a4b818387b58d59336c288f99b48f69681aa60cc681fe038bbca5d" diff --git a/src/rust/Cargo.toml b/src/rust/Cargo.toml index 4ae8033eb..d47cd6422 100644 --- a/src/rust/Cargo.toml +++ b/src/rust/Cargo.toml @@ -1,6 +1,8 @@ [workspace] members = ["tor_util", "protover", "smartlist", "external", "tor_allocate", -"tor_rust", "tor_log"] +"tor_rust", "tor_log", + "rand", +] [profile.release] debug = true diff --git a/src/rust/external/crypto_rand.rs b/src/rust/external/crypto_rand.rs new file mode 100644 index 000000000..19b9ab281 --- /dev/null +++ b/src/rust/external/crypto_rand.rs @@ -0,0 +1,95 @@ +// Copyright (c) 2018, The Tor Project, Inc. +// Copyright (c) 2018, isis agora lovecruft +// See LICENSE for licensing information + +//! Bindings to external (P)RNG interfaces and utilities in +//! src/common/crypto_rand.[ch]. +//! +//! We wrap our C implementations in src/common/crypto_rand.[ch] here in order +//! to provide wrappers with native Rust types, and then provide more Rusty +//! types and and trait implementations in src/rust/crypto/rand/. + +use std::time::Duration; + +use libc::c_char; +use libc::c_double; +use libc::c_int; +use libc::c_uint; +use libc::c_void; +use libc::size_t; +use libc::time_t; +use libc::uint8_t; +use libc::uint64_t; + +extern "C" { + fn crypto_seed_rng() -> c_int; + fn crypto_strongest_rand(out: *mut uint8_t, out_len: size_t); + fn crypto_rand_time_range(min: time_t, max: time_t) -> time_t; + fn crypto_rand_double() -> c_double; + // fn crypto_random_hostname(min_rand_len: c_int, max_rand_len: c_int, + // prefix: *const c_char, suffix: *const c_char) -> *mut c_char; +} + +/// Seed OpenSSL's random number generator with bytes from the operating +/// system. +/// +/// # Returns +/// +/// `true` on success; `false` on failure. +pub fn c_tor_crypto_seed_rng() -> bool { + let ret: c_int; + + unsafe { + ret = crypto_seed_rng(); + } + match ret { + 0 => return true, + _ => return false, + } +} + +/// Fill the bytes of `dest` with strong random data. +pub fn c_tor_crypto_strongest_rand(dest: &mut [u8]) { + // We'll let the C side panic if the len is larger than + // MAX_STRONGEST_RAND_SIZE, rather than potentially panicking here. A + // paranoid caller should assert on the length of dest *before* calling this + // function. + unsafe { + crypto_strongest_rand(dest.as_mut_ptr(), dest.len() as size_t); + } +} + +/// Get a random time, in seconds since the Unix Epoch. +/// +/// # Returns +/// +/// A `std::time::Duration` of seconds since the Unix Epoch. +pub fn c_tor_crypto_rand_time_range(min: &Duration, max: &Duration) -> Duration { + let ret: time_t; + + unsafe { + ret = crypto_rand_time_range(min.as_secs() as time_t, max.as_secs() as time_t); + } + + Duration::from_secs(ret as u64) +} + +/// Return a pseudorandom 64-bit float, chosen uniformly from the range [0.0, 1.0). +pub fn c_tor_crypto_rand_double() -> f64 { + unsafe { + crypto_rand_double() + } +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn test_layout_tor_weak_rng_t() { + assert_eq!(::std::mem::size_of::<tor_weak_rng_t>(), 0usize, + concat!("Size of: ", stringify!(tor_weak_rng_t))); + assert_eq!(::std::mem::align_of::<tor_weak_rng_t>(), 1usize, + concat!("Alignment of ", stringify!(tor_weak_rng_t))); + } +} diff --git a/src/rust/external/lib.rs b/src/rust/external/lib.rs index 0af0d6452..5fd74cf4c 100644 --- a/src/rust/external/lib.rs +++ b/src/rust/external/lib.rs @@ -1,4 +1,4 @@ -//! Copyright (c) 2016-2017, The Tor Project, Inc. */ +//! Copyright (c) 2016-2018, The Tor Project, Inc. */ //! See LICENSE for licensing information */ //! Interface for external calls to tor C ABI @@ -9,6 +9,8 @@ extern crate libc; +mod crypto_rand; mod external; +pub use crypto_rand::*; pub use external::*; diff --git a/src/rust/rand/Cargo.toml b/src/rust/rand/Cargo.toml new file mode 100644 index 000000000..cab71afa7 --- /dev/null +++ b/src/rust/rand/Cargo.toml @@ -0,0 +1,24 @@ +# TODO: Note that this package should be merged into the "crypto" crate after #24659 is merged. + +[package] +authors = ["The Tor Project"] +version = "0.0.1" +name = "rand" +publish = false + +[features] +testing = ["tor_log/testing"] + +[dependencies] +libc = "=0.2.39" +rand_core = "=0.1.0" + +external = { path = "../external" } +tor_allocate = { path = "../tor_allocate" } +tor_log = { path = "../tor_log" } +tor_util = { path = "../tor_util" } + +[lib] +name = "rand" +path = "lib.rs" +crate_type = ["rlib", "staticlib"] diff --git a/src/rust/rand/lib.rs b/src/rust/rand/lib.rs new file mode 100644 index 000000000..ee034cf1f --- /dev/null +++ b/src/rust/rand/lib.rs @@ -0,0 +1,15 @@ +// Copyright (c) 2018, The Tor Project, Inc. +// Copyright (c) 2018, isis agora lovecruft +// See LICENSE for licensing information + +// External dependencies +extern crate rand_core; + +// Internal dependencies +extern crate external; +#[cfg(not(test))] +#[macro_use] +extern crate tor_log; + +pub mod rng; +pub mod prng; diff --git a/src/rust/rand/prng.rs b/src/rust/rand/prng.rs new file mode 100644 index 000000000..ed3f5161e --- /dev/null +++ b/src/rust/rand/prng.rs @@ -0,0 +1,184 @@ +// Copyright (c) 2018, The Tor Project, Inc. +// Copyright (c) 2018, isis agora lovecruft +// See LICENSE for licensing information + +//! Wrappers for Tor's pseudo-random number generator to provide implementations +//! of `rand_core` traits. + +use rand_core::impls; +#[cfg(test)] use rand_core::CryptoRng; +use rand_core::Error; +use rand_core::RngCore; +use rand_core::SeedableRng; + +/// A cryptographically-/insecure/ psuedo-random number generator based +/// on a mixed congruential generator. +/// +/// Specifically the PRNG state, `X`, is mutated by the following +/// discontinuous linear equation: +/// +/// ```text +/// X_{i} = (a X_{i-1} + b) mod n +/// ``` +/// +/// where, in our case, we reuse the same parameters as OpenBSD and glibc, +/// `a=1103515245`, `b=12345`, and `n=2147483647`, which should produce a +/// maximal period over the range `0..u32::MAX`. +/// +/// # Note +/// +/// We reimplement the C here, rather than wrapping it, as it's one line of +/// pure-Rust code (meaning it can also trivially be used in Rust tests without +/// running into potential linker issues), as opposed to a few lines of `unsafe` +/// calls to C. +/// +/// # Warning +/// +/// This should hopefully go without saying, but this PRNG is completely +/// insecure and should never be used for anything an adversary should be unable +/// to predict. +// +// C_RUST_COUPLED: `tor_weak_rng_t` /src/common/util.c +pub struct TorInsecurePrng { + state: u32, +} + +impl SeedableRng for TorInsecurePrng { + type Seed = [u8; 4]; + + /// Create a new PRNG from a random 32-bit seed. + // + // C_RUST_COUPLED: `tor_init_weak_random()` /src/common/util.c + fn from_seed(seed: Self::Seed) -> Self { + let mut combined: u32 = seed[0].to_le() as u32; + + // Rather than using std::mem::transmute, we'll just bitwise-OR them + // into each other. + combined = (seed[1].to_le() as u32) << 8 | combined; + combined = (seed[2].to_le() as u32) << 16 | combined; + combined = (seed[2].to_le() as u32) << 24 | combined; + + TorInsecurePrng{ state: (combined & 0x7fffffff).to_le() } + } +} + +impl TorInsecurePrng { + /// This is the equivalent function to `tor_weak_random()`. + // + // C_RUST_COUPLED: `tor_weak_random()` /src/common/util.c + pub fn next_i32(&mut self) -> i32 { + // The C code appears to purposefully overflow the 32-bit state integer. + self.state = (self.state.wrapping_mul(1103515245).wrapping_add(12345) & 0x7fffffff).to_le(); + self.state as i32 + } +} + + +impl RngCore for TorInsecurePrng { + // C_RUST_COUPLED: `tor_weak_random()` /src/common/util.c + fn next_u32(&mut self) -> u32 { + let x: u32 = self.next_i32() as u32; + let y: u32 = self.next_i32() as u32; + + // We have to add two samples together due to modding 0x7fffffff + x + y + } + + fn next_u64(&mut self) -> u64 { + impls::next_u64_via_u32(self) + } + + fn fill_bytes(&mut self, dest: &mut [u8]) { + impls::fill_bytes_via_u32(self, dest); + } + + fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> { + Ok(self.fill_bytes(dest)) + } +} + +/// If we're running tests, it's fine to pretend this PRNG is cryptographically +/// secure. (This allows us to test which require an implementation of +/// `CryptoRng` without actually initialising all the OpenSSL C code.) +#[cfg(test)] +impl CryptoRng for TorInsecurePrng {} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn next_u32_shouldnt_return_same_number_twice_in_a_row() { + // This test will fail 1 out of 2^{64} times (5.42 e-20), but the + // probability of a particle radiating off a star and hitting your RAM + // is roughly 1.4 e-15 per byte of RAM per second, so if this fails, + // blame ~~Cosmic Rays~~ and not anyone named isis. + let mut prng: TorInsecurePrng = TorInsecurePrng::from_seed([0xDE, 0xAD, 0x15, 0x15]); + + let one: u32 = prng.next_u32(); + let two: u32 = prng.next_u32(); + + assert!(one != two); + } + + #[test] + fn next_u32_should_have_uniform_distribution_average() { + let mut prng: TorInsecurePrng = TorInsecurePrng::from_seed([0xDE, 0xAD, 0x15, 0x15]); + let mut accumulator: Vec<u32> = Vec::new(); + let n: u64 = 10_000; + + for _ in 0 .. n as usize { + accumulator.push(prng.next_u32()); + } + let total: u64 = accumulator.iter().fold(0, |acc,&x| acc + (x as u64)); + let average = total / n; + println!("average is {:?}", average); + + assert!(average <= 0x7fffffff + 0xf00000); + assert!(average >= 0x7fffffff - 0xf00000); + } + + #[test] + fn next_u32_shouldnt_have_bit_bias() { + // Since the modulus in the mixed congruential generator isn't a power + // of two, the bits should not have any statistical bias. + let mut prng: TorInsecurePrng = TorInsecurePrng::from_seed([0xDE, 0xAD, 0x15, 0x15]); + let mut accumulator: Vec<u32> = Vec::new(); + let n: u64 = 10_000; + + for _ in 0 .. n as usize { + accumulator.push(prng.next_u32().count_ones()); + } + let total: u64 = accumulator.iter().fold(0, |acc,&x| acc + (x as u64)); + let average = total / n; + println!("average is {:?}", average); + + assert!(average == 16); + } + + #[test] + fn next_u64_shouldnt_return_same_number_twice_in_a_row() { + // This test will fail 1 out of 2^{128} times (2.94 e-39), but the + // probability of a particle radiating off a star and hitting your RAM + // is roughly 1.4 e-15 per byte of RAM per second, so if this fails, + // blame ~~Cosmic Rays~~ and not anyone named isis. + let mut prng: TorInsecurePrng = TorInsecurePrng::from_seed([0xDE, 0xAD, 0x15, 0x15]); + + let one: u64 = prng.next_u64(); + let two: u64 = prng.next_u64(); + + assert!(one != two); + } + + #[test] + fn fill_bytes_shouldnt_leave_all_zeroes() { + // Again, 1 in 256^8 (5.42 e-20) chances this fails. + // ~~Cosmic Rays~~, I tell you. + let mut prng: TorInsecurePrng = TorInsecurePrng::from_seed([0xDE, 0xAD, 0x15, 0x15]); + let mut bytes: [u8; 8] = [0u8; 8]; + + prng.fill_bytes(&mut bytes); + + assert!(bytes != [0u8; 8]); + } +} diff --git a/src/rust/rand/rng.rs b/src/rust/rand/rng.rs new file mode 100644 index 000000000..a334f5f09 --- /dev/null +++ b/src/rust/rand/rng.rs @@ -0,0 +1,94 @@ +// Copyright (c) 2018, The Tor Project, Inc. +// Copyright (c) 2018, isis agora lovecruft +// See LICENSE for licensing information + +//! Wrappers for Tor's random number generator to provide implementations of +//! `rand_core` traits. + +// This is the real implementation, in use in production, which calls into our C +// wrappers in /src/common/crypto_rand.c, which call into OpenSSL, system +// libraries, and make syscalls. +#[cfg(not(test))] +mod internal { + use std::u64; + + use rand_core::CryptoRng; + use rand_core::Error; + use rand_core::RngCore; + use rand_core::impls::next_u32_via_fill; + use rand_core::impls::next_u64_via_fill; + + use external::c_tor_crypto_strongest_rand; + use external::c_tor_crypto_seed_rng; + + use tor_log::LogDomain; + use tor_log::LogSeverity; + + /// Largest strong entropy request permitted. + // + // C_RUST_COUPLED: `MAX_STRONGEST_RAND_SIZE` /src/common/crypto_rand.c + const MAX_STRONGEST_RAND_SIZE: usize = 256; + + /// A wrapper around OpenSSL's RNG. + pub struct TorRng { + // This private, zero-length field forces the struct to be treated the + // same as its opaque C couterpart. + _unused: [u8; 0], + } + + /// Mark `TorRng` as being suitable for cryptographic purposes. + impl CryptoRng for TorRng {} + + impl TorRng { + // C_RUST_COUPLED: `crypto_seed_rng()` /src/common/crypto_rand.c + #[allow(dead_code)] + fn new() -> Self { + if !c_tor_crypto_seed_rng() { + tor_log_msg!(LogSeverity::Warn, LogDomain::General, + "TorRng::from_seed()", + "The RNG could not be seeded!"); + } + // XXX also log success at info level —isis + TorRng{ _unused: [0u8; 0] } + } + } + + impl RngCore for TorRng { + // C_RUST_COUPLED: `crypto_strongest_rand()` /src/common/crypto_rand.c + fn next_u32(&mut self) -> u32 { + next_u32_via_fill(self) + } + + // C_RUST_COUPLED: `crypto_strongest_rand()` /src/common/crypto_rand.c + fn next_u64(&mut self) -> u64 { + next_u64_via_fill(self) + } + + // C_RUST_COUPLED: `crypto_strongest_rand()` /src/common/crypto_rand.c + fn fill_bytes(&mut self, dest: &mut [u8]) { + debug_assert!(dest.len() <= MAX_STRONGEST_RAND_SIZE); + + c_tor_crypto_strongest_rand(dest); + } + + // C_RUST_COUPLED: `crypto_strongest_rand()` /src/common/crypto_rand.c + fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Error> { + Ok(self.fill_bytes(dest)) + } + } +} + +// For testing, we expose the pure-Rust implementation of a +// cryptographically-insecure PRNG which mirrors the implementation of +// `tor_weak_rng_t` in C. +#[cfg(test)] +mod internal { + use prng::TorInsecurePrng; + + pub type TorRng = TorInsecurePrng; +} + +// Finally, expose the public functionality of whichever appropriate internal +// module. +pub use self::internal::*; +