2291. std::hash is vulnerable to collision DoS attack

Section: 16.4.4.5 [hash.requirements] Status: C++14 Submitter: Zhihao Yuan Opened: 2013-09-02 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [hash.requirements].

View all issues with C++14 status.

Discussion:

For a non-cryptographic hash function, it's possible to pre-calculate massive inputs with the same hashed value to algorithmically slow down the unordered containers, and results in a denial-of-service attack. Many languages with built-in hash table support have fixed this issue. For example, Perl has universal hashing, Python 3 uses salted hashes.

However, for C++, in 16.4.4.5 [hash.requirements] p2, Table 26:

The value returned shall depend only on the argument k. [Note: Thus all evaluations of the expression h(k) with the same value for k yield the same result. — end note]

The wording is not clear here: does that mean all the standard library implementations must use the same hash function for a same type? Or it is not allowed for an implementation to change its hash function?

I suggest to explicitly allow the salted hash functions.

[2013-09 Chicago]

Moved to Ready.

There is some concern that the issue of better hashing, especially standardizing any kind of secure hashing, is a feature that deserves attention in LEWG

The proposed resolution is much simpler than the larger issue though, merely clarifying a permission that many implementers believe they already have, without mandating a change to more straight forward implementations.

Move to Ready, rather than Immediate, as even the permission has been contentious in reflector discussion, although the consensus in Chicago is to accept as written unless we hear a further strong objection.

Proposed resolution:

This wording is relative to N3691.

1. Edit 16.4.4.5 [hash.requirements] p2, Table 26, as indicated: [Editorial note: We can consider adding some additional guideline here. Unlike N3333, this proposed change makes the hashing per-execution instead of per-process. The standard does not discuss OS processes. And, practically, a per-process hashing makes a program unable to share an unordered container to a child process. — end note ]

   Table 26 — Hash requirements [hash]

   Expression	Return type	Requirement
   h(k)	size_t	The value returned shall depend only on the argument k for the duration of the program. [Note: Thus all evaluations of the expression h(k) with the same value for k yield the same result for a given execution of the program. — end note]
   …