In the Rust documentation here it says that the hashing function that a Rust HashMap uses is SipHash. It says SipHash can provide resistance to DoS attacks involving hash tables, not that it will, although it was created to counter the HashDoS attacks in 2011.
On Wikipedia here it says: "Functions in SipHash family are specified as SipHash-c-d, where c is the number of rounds per message block and d is the number of finalization rounds. The recommended parameters are SipHash-2-4 for best performance, and SipHash-4-8 for conservative security. A few languages use Siphash-1-3 for performance at the risk of yet-unknown DoS attacks".
The latest Rust codebase here, as at 10th April 2023, is currently using SipHash-1-3 as its default hashing function used by the Rust Standard Library.
Rust uses it by default in std::collections::HashMap.
It was merged in this historic pull request, where they mentioned that SipHash-1-3 hasher is faster than SipHash 2-4, but is believed to provide sufficient protection from collision attacks.
Rust community members mentioned that:
- SipHash-4-8 like all cryptographic primitives, is also used "at the risk of yet-unknown attacks", except those that already have "known" attacks.
- Recently the Rust compiler also switched to SipHash-1-3 for its own internal hashing (which backs up things like incremental compilation), since they believe it is still good enough and quite a bit faster than SipHash-2-4 and SipHash-4-8.
- If there was a security issue with SipHash-1-3,
rustccompiler updates should always be possible so the std could update to use a different hasher entirely. - The SipHash used in the Rust Standard Library implementation has been reviewed by many contributors and used by many projects.
This table from November 2015 compares the performance of different Rust hashing algorithms including SipHash-1-3 and SipHash-2-4.
In an older version of the Rust Standard Library it mentions in the SipHasher docs here that "Although the SipHash algorithm is considered to be generally strong, it is not intended for cryptographic purposes. As such, all cryptographic uses of this implementation are strongly discouraged."
It also mentions that it "lets you key your hash tables from a strong RNG, such as rand::os::OsRng"
The Substrate repository uses the Rust HashMap extensively, however it appears to use SipHash-1-3 (the Rust default hasher), since it does not use HashMap::with_hasher() to specify a non-default custom hasher.
Additionally the Substrate repository uses the Rust rand::rngs::OsRng, which uses the implementation of the getrandom crate to generate cryptographic PKI key pair types, but it doesn't implement the marker trait CryptoRng in its trait bounds, which is used to indicate that its implementation is supposed to be cryptographically secure, where Cryptographically Secure Pseudorandom Number Generators, also known as CSPRNGs, should satisfy additional properties over other generators like PRNGs.
For example, the following was created with support from the https://discord.gg/rust-lang-community Rust community to show how to use the CryptoRng marker trait:
use rand::prelude::*;
use rand_core::{CryptoRng, RngCore};
fn pick_usize<R: RngCore, C: CryptoRng + ?Sized>(rng: &mut R, max: usize) -> usize {
// use `Rng::gen_range` instead of `%` otherwise it generates biases in results
// since the modulo of a uniform distribution makes it not uniform anymore
rng.gen_range(0..=max)
}
fn main() {
let max = 100;
let mut rng = thread_rng();
let random_number = pick_usize::<ThreadRng, dyn CryptoRng>(&mut rng, max);
println!("{}", random_number);
}
In CryptoRng it states: "Note that this trait is provided for guidance only and cannot guarantee suitability for cryptographic applications. In general it should only be implemented for well-reviewed code implementing well-regarded algorithms. Note also that use of a CryptoRng does not protect against other weaknesses such as seeding from a weak entropy source or leaking state."
This pull request even questions the usefulness of CryptoRng.
In this blogpost A brief look at the Linux-kernel random generator interfaces it shows how on Linux it either reads a file /dev/random or /dev/urandom or it makes a syscall to getrandom() of the OS to provide random data from the kernel CPRNG. The getrandom crate shows what it uses to interface with each target OS here.
In the Zombienet repository that is a tool to easily spawn ephemeral Polkadot/Substrate networks and perform tests against them, there doesn't appear to be any issues or pull requests that mention they are related to DoS tests or comparisons in the performance and security of different hash functions.
In this Hacker News: A Brief History of Random Numbers post some users mention the following:
- developers "should just be using the default RNG provided by their language, which should be a CSPRNG"
- "Using a PRNG instead of a CSPRNG may lead to security vulnerabilities"
- "Using a CSPRNG instead of a PRNG may lead to performance degradation"
If Substrate is a "well-reviewed code implementing well-regarded algorithms" then why doesn't it implement a CSPRNG by using CryptoRng rather than just a PRNG?
