4

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, rustc compiler 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?

1 Answer 1

4

Your question rambles around, so you should maybe clarify the actual question. If you're asking the standard "Why is SipHash good enough?" then..

As a rule, probabilistic data structures like rust's HashMap need a secret seed to prevent DoS attacks. SipHash was designed as a "keyed hash function" which "maintains" this security property, but you obtain the underlying secret seed from getrandom or similar via std::collections::hash_map::RandomState.

We do not worry about the OS kernel having backdoored randomness, so some flavor of SipHash and RandomState suffice. One could discuss SipHash parameters or the counter in RandomState of course, but then Jean-Philippe Aumasson's opinion matters, like if he said anything about SipHash around https://eprint.iacr.org/2019/1492

If otoh you envision a maliciously keyed HashMap then the birthday bound says no hash function could prevent collisions in a 64 bit key space. This is just silly.

2
  • thank you Jeff. apologies for rambling a bit, i was providing context for others and my future self in the lead up to the question that was asked at the end. i'm not fluent on the topic and had to learn about it to try to ask the question. the question was specifically concerning whether or not there was an opportunity to add more marker traits like CryptoRng in trait bounds in Substrate, on the assumption that'd be necessary to indicate its implementation should be cryptographically secure, satisfying the additional properties of a CSPRNG. i gather your answer is that it is not necessary? May 4, 2023 at 0:09
  • 1
    CryptoRng is not part of rust's core/std so it's irrelevant here. Also it's meaning is contextual, which is confusing, and prevents it being relevant for hashmaps anyways May 4, 2023 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.