Proposal: Add the unordered-containers package and the hashable package to the Haskell Platform

Vincent Hanquez tab at snarc.org
Fri Mar 22 07:47:58 CET 2013


On 03/20/2013 06:14 PM, Johan Tibell wrote:
> On Wed, Mar 20, 2013 at 11:00 AM, Bardur Arantsson <spam at scientician.net>wrote:
>
>> AFAICT, the hash function needn't be cryptographically secure (though
>> that obviously avoids the issue altogether) -- if there is some
>> determined-at-startup "salt" that's added in to all hashed values then
>> that should provide good enough protection. Obviously this will mean
>> that the hashes won't be repeatable across runs of the same program, but
>> that's usually acceptable for a hash function which isn't used for
>> content identification(*).
>>
>> (*) For which you should use a cryptographically secure hash anyway.
>>
> This is what Python did and unfortunately it's not enough as the salt can
> easily be recovered if you use a weak hash function. See the SipHash paper.

The property behind siphash it is that you won't be able to forge a 
specific hash (in this instance to put stuff in the same bucket in a 
hashtable).

If you can recover the salt, then you can forge anything you want.

Technically any traditional crypto hash would solve the problem too 
(without salt), as one property is that given a hash it's hard to 
generate a message, but would kill performance massively of the hashing 
step, as they are not meant to hash small input.

> Not at all. $BIG_WEB_COMPANIES do it on the fly using $SECRET_SMART_SAUCE.
>
> Hash flooding is only one of many ways to DoS a server. You can try other
> things, like building a bot net and trying to flood the connection. Just as
> sandboxing is a better way to run untrusted software than trying to plug
> every whole in your code/RTS, generic anti-DoS techniques are usually
> better than trying to figure out every possible way someone can DoS you.
This is quite untrue that it would solve this problem though, as you can 
hash flood with perfectly legal network connection, you don't 
necessarily need to go fast or generate ton of datas or keep a 
connection open, depending on what your web stuff do.

Also this specific issue is not related to only web framework, it's a 
generic algorithmic "problem" of hashtables with weak hashing method, as 
a malicious user can transform a hashtables into a linked list. 
Potentially if you have anything that is user generated that the code 
uses as keys (it could be filenames on disk), you could be in this position.

-- 
Vincent



More information about the Libraries mailing list