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

[Johan Tibell]

On Wed, Mar 20, 2013 at 6:42 AM, Jan-Willem Maessen
<jmaessen at alum.mit.edu>wrote:

> On Wed, Mar 20, 2013 at 6:02 AM, Gábor Lehel <illissius at gmail.com> wrote:
>
>> Compatibility issues aside, is there any reason newtypes aren't a good
>> solution here?
>>
>
> Well, the tricky bit is that there are really two distinct uses of hashing
> in the field in general and under discussion here in particular.  The first
> (which is the one that's important for unordered-containers and almost all
> practical uses of hashing *within* a program) is to provide fast keys for
> hash tables, where the hash function is backed by equality checks and the
> like and is thus a question of performance rather than correctness.  For
> this a reasonably good, but not necessarily cryptographically secure,
> hashing method is more than sufficient.
>

hashable is definitely defined for this use case. Unfortunately there's a
class of DsS attacks (hash flooding) that work like this:

1. The application (e.g. a webserver) stores some user input in a hash
table (e.g. the HTTP headers received in the request).
2. The application uses a weak hash function (i.e. a non-cryptographic hash
function) in the hash table.
3. The user feeds the application a set of keys that all collide, making
the hash table behave as O(n) or even O(n^2), thereby DoS:ing the server.

SipHash is one way to address these kinds of attacks. There are other means
as well. For example, many general DoS protection mechanisms (timeouts, IP
banning, etc) also work on these kind of attacks.

-- Johan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130320/f29b04e1/attachment.htm>