cloudflare / cloudflare/quiche

Use of identity hash function may lead to suboptimal performance

Open
#1,239 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
11.8k
Forks
1.1k
Avg merge
21h 9m
Merged PRs (30d)
6

Description

Looking at the code, I noticed that stream IDs are hashed using the identity hash function (added in #1149).

Stream IDs are unique u64s, but I believe they are not necessarily evenly distributed across the space of possible values. This makes the identity hash function a suboptimal hash function for this case; if the hash values are not evenly distributed, the rate of hash collisions will be higher than necessary.

I'm not sure the decision to use the identity hash function in this case was well considered. I would consider using a different hash function.

In #996, it is also claimed that using the default hasher is not necessary because stream IDs are just numbers. But the key factor in choosing a hasher like FxHash instead of the standard hasher is that the standard hasher performs worse because it is DDoS resistant. The problem is that if the key value is chosen by the adversary, they can choose keys that increase the probably of a collision, resulting in degraded service. My understanding of QUIC is that stream IDs **can be** chosen by the other party in the connection, and therefore an adversary that has connected to you could choose stream IDs that cause collisions, increasing the CPU time serving their connection takes by creating collisions in these tables. Note this is also true for non-DDoS resistant hashers that are not the identity function, because if the adversary knows the hash function used they can still choose stream IDs which collide.

I could be missing something, but I would encourage going back to a DDoS resistant hash function for stream tables.

Contributor guide

Open the contributing guide

Research direction

The issue names no files or tests; start by locating the stream tables and their identity-hash construction. Review QUIC stream-ID selection assumptions and measure collision behavior under uneven or adversarial IDs. Done means selecting and validating a hashing approach that addresses the stated performance and collision concerns.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
networking, performance, security
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.