[cfe-dev] [libc++] Initial attempt to make a salted hash

[Howard Hinnant]

On Aug 30, 2013, at 1:58 PM, Zhihao Yuan <zy at miator.net> wrote:

> Hi,
> 
> Modern programming languages with built-in hash table
> support usually has some mechanism to fight against
> hash collision attack (DoS, use massive prepared input
> with same hash code to slow down the service; the
> problem is more severe in C++ since the unordered
> containers use seperate chaining instead of open
> addressing).  For example, Perl uses universal hashing,
> Python3 uses salted hash.
> 
> Here is an initial attempt to implement a salted hash in
> libc++, by using an unpredictable seed in
> __murmur2_or_cityhash across the lifetime of a program,
> and an simple demonstration -- if you run it multiple
> times, the order of the elements within an unordered
> container may change.

I think we need to be cautious here.

[hash.requirements]/ Table 26 says:

> 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 ]

Now it isn't clear, at least to me, that if this is talking about all evaluation within the process, or across different invocations of the same process, or even across invocations of different processes.  Without guidance from the LWG, I think we need to assume the most conservative answer.

I faintly recall this subject was brought up at the Portland meeting, Fall 2012.  I do not believe anything was definitively resolved at that time.  I do not know if this issue was discussed this Spring in Bristol.  I do not see an LWG issue on this subject.

Howard