Movatterモバイル変換

This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofC++14 status.

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

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

Priority:Not Prioritized

View all otherissues in [hash.requirements].

View all issues withC++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 fixedthis 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 argumentk.[Note: Thus all evaluations of the expressionh(k) with thesame value fork yield the same result. —end note]

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

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 ofsecure hashing, is a feature that deserves attention in LEWG

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

Move to Ready, rather than Immediate, as even the permission has been contentious in reflectordiscussion, although the consensus in Chicago is to accept as written unless we hear a furtherstrong 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. UnlikeN3333, 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 toshare 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 argumentk for the duration of the program. [Note: Thus all evaluations of the expressionh(k) with the same value fork yield the same resultfor a given execution of the program. —end note]
   …