code review 7051043: runtime: always incorporate hash seed at start of hash ...

runtime: always incorporate hash seed at start of hash computation

Otherwise we can get predictable collisions.

[iant, 2013-01-03 21:45:38]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://code.google.com/p/go

[dave_cheney.net, 2013-01-04 04:55:40]

On 2013/01/03 21:45:38, iant wrote:
> Hello mailto:golang-dev@googlegroups.com,
> 
> I'd like you to review this change to
> https://code.google.com/p/go

Playing the devils advocate here -- can hash collisions be exploited in the way
that perl and php maps are affected? What is the worst case behaviour of the Go
map implementation when presented with the same data that huts Perl/PHP ?

[iant, 2013-01-04 05:53:42]

On 2013/01/04 04:55:40, dfc wrote:
> 
> Playing the devils advocate here -- can hash collisions be exploited in the
way
> that perl and php maps are affected? What is the worst case behaviour of the
Go
> map implementation when presented with the same data that huts Perl/PHP ?

Whether they can be exploited depends on how the program uses them.  If a
program simply reads strings from a network connection and stores them in a map,
then currently an attacker can construct a single set of strings that will
always cause a runtime error "map hash collision overflow".  This change would
make that harder--there would still be a set of strings that will cause a hash
overflow, but for each run of the program it would be a different set of
strings.

Based on that, the worst case, for some programs, is that there is a reliable
way to crash the program.  I don't know if anything worse is possible.

[pmylund, 2013-01-04 06:00:36]

> Playing the devils advocate here -- can hash collisions be
> exploited in the way that perl and php maps are affected?

Yes.

> What is the worst case behaviour of the Go
> map implementation when presented with the same data that
> huts Perl/PHP ?

A very inexpensive (bandwidth-wise) DoS. Offline or online compilation of
colliding entries, causing neighboring linked lists/subtables with thousands of
entries to make e.g. a single http.Request with a relatively small payload, e.g.
a ~1MB body to incur an enormous amount of overhead. (Thousands of hours of CPU
time on modern CPUs.) In Go you could cause the allocation of and iteration
through a large number of subtables.

PHP "solved" it by limiting the number of headers/queryparams to something like
1000, and Oracle claimed it wasn't a language problem. IMO, any hashmap being
DoS-able without explicit custom protection is very much a language problem.

Some implementations mitigate by using a BST instead of a linked list for
buckets, but the best solution is to simply use a hash function where it is
harder to find collisions, or alternatively to use an IV like this, so it's at
least harder to find colliding entries for a given Go instance.

Paper here: http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/

Recent talk that brought the topic back up after several years:
http://www.youtube.com/watch?v=R2Cq3CLI6H8 (Perl were the only ones who had
implemented protection against this prior to this, AFAIK. That protection was
equivalent to this.) Unfortunately, this vulnerability is not so obscure
anymore.

[pmylund, 2013-01-04 06:05:02]

On 2013/01/04 05:53:42, iant wrote:
> On 2013/01/04 04:55:40, dfc wrote:
> > 
> > Playing the devils advocate here -- can hash collisions be exploited in the
> way
> > that perl and php maps are affected? What is the worst case behaviour of the
> Go
> > map implementation when presented with the same data that huts Perl/PHP ?
> 
> Whether they can be exploited depends on how the program uses them.  If a
> program simply reads strings from a network connection and stores them in a
map,
> then currently an attacker can construct a single set of strings that will
> always cause a runtime error "map hash collision overflow".  This change would
> make that harder--there would still be a set of strings that will cause a hash
> overflow, but for each run of the program it would be a different set of
> strings.
> 
> Based on that, the worst case, for some programs, is that there is a reliable
> way to crash the program.  I don't know if anything worse is possible.

Yeah--or to make it simply unresponsive--a DoS. The scary thing about this
attack is that it requires very, very little bandwidth from the attacker(s)
compared to traditional DoS attacks. Most of the implementations (using linked
lists--I admit I haven't seen this against, or benchmarked against Go) were
subjected to <2MB payloads that caused the program to just burn a core for many
hours.

I don't know if you could perform any other attack. You could cause the
allocation of a lot of memory, potentially causing problems for other programs,
but nothing more serious...

[dave_cheney.net, 2013-01-04 06:06:17]

> Some implementations mitigate by using a BST instead of a linked list
> for buckets, but the best solution is to simply use a hash function
> where it is harder to find collisions, or alternatively to use an IV
> like this, so it's at least harder to find colliding entries for a given
> Go instance.

So, what if we just stopped storing headers in a map ?

[pmylund, 2013-01-04 06:21:08]

On 2013/01/04 06:06:17, dfc wrote:
> > Some implementations mitigate by using a BST instead of a linked list
> > for buckets, but the best solution is to simply use a hash function
> > where it is harder to find collisions, or alternatively to use an IV
> > like this, so it's at least harder to find colliding entries for a given
> > Go instance.
> 
> So, what if we just stopped storing headers in a map ?

Technically, if we wanted to follow the RFCs, this is what we're supposed to do.
HTTP headers must retain their original ordering, which of course is no longer
true after they're put in a map. OTOH, few apps do this as it makes everything
more impractical. We could probably encapsulate most of it in url.Values, but
there are probably many people out there using the req.Header field as a
map[string][]string already...

An argument against lists is that a simple association list would have O(n)
complexity, but I suspect that might actually be faster in many cases since most
HTTP requests have few headers and the hash function is (probably) costlier than
a few more comparisons. (Of course that property, too, would be exploitable.)

The Go 1 contract makes any change tricky, and the attack would be against
ParseForm/ParsePostForm, so we can't really just change the implementation of
FormValue/PostFormValue.

In any case, we can assume that many other protocol implementations than HTTP in
net/http will use maps constructed from user input. Even if we did impose some
kind of limit or alternate implementation in net/http, that would do nothing to
help them.

[pmylund, 2013-01-04 06:51:02]

I had forgotten about the subtable limit, sorry Ian. But yeah, somebody could
DoS almost as effectively through crashing the application.

[iant, 2013-01-04 14:07:53]

On 2013/01/04 06:06:17, dfc wrote:
> 
> So, what if we just stopped storing headers in a map ?

This is a potential issue for any network connected application that stores user
input in a map.  The HTTP headers are just an obvious case.

Anyhow we've already decided to use random seeds to reduce the risk of
precomputed attacks on maps.  This CL just makes that decision work better.

[rsc, 2013-01-04 15:16:40]

LGTM

[iant, 2013-01-04 15:53:50]

*** Submitted as https://code.google.com/p/go/source/detail?r=26a32c1225bf ***

runtime: always incorporate hash seed at start of hash computation

Otherwise we can get predictable collisions.

R=golang-dev, dave, patrick, rsc
CC=golang-dev
https://codereview.appspot.com/7051043