[Bug libstdc++/55815] New: switch hash function of libstdc++ hash tables to siphash

[Bug libstdc++/55815] New: switch hash function of libstdc++ hash tables to siphash

[felix-gcc at fefe dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55815

             Bug #: 55815
           Summary: switch hash function of libstdc++ hash tables to
                    siphash
    Classification: Unclassified
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: felix-gcc@fefe.de


Hash functions traditionally used by language runtimes for hash tables do not
assume that input values will be chosen maliciously to cause collisions and
degrade performance.  This has become a published attack vector on internet
facing hash tables as used in, for example, web services or even memory cache
code in front of a database or so.

libsupc++ implements the Murmur hash, which was specifically targeted in a
recent paper attacking hash functions.  See https://131002.net/siphash/ for the
attack code that produces collisions in Murmur2 and Murmur3.

libsupc++ should switch the hash function to siphash, the function proposed by
the authors of this attack.

The same bug should be filed against other user facing hash table
implementations in gcc.  I can think of Java and Go, but there might be others.

It may even make sense to replace the hash code gcc itself uses, as there are
now web pages where you can paste code and see which code gcc generates for it,
turning this problem into a security issue if someone pastes code with
colliding symbols to exploit this problem.

[Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55815

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-01-05
     Ever Confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-01-05 13:29:19 UTC ---
Even if we don't change the default we could provide a SipHash implementation
to make it easier for users to use it in unordered containers.

[Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55815

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-01-05 14:34:53 UTC ---
N.B. I think the only use of _Hash_bytes which users can't already replace is
in type_info::hash_code(), which must give a consistent result across
ABI-compatible releases.

Also worth noting is that neither the murmur2collisions nor murmur3collisions
code from https://131002.net/siphash/ produces more than 0.5% collisions for
our _Hash_bytes function.

[Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55815

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-01-05 14:48:22 UTC ---
Whatever we do here I suppose we should involve Matt.

[Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash

[gpike at google dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55815

Geoff Pike <gpike at google dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gpike at google dot com

--- Comment #4 from Geoff Pike <gpike at google dot com> ---
I'm working on a higher-difficulty-higher-payoff approach to hash-flood
mitigation. It admittedly has a long way to go, but for those interested, an
early draft is https://gcc.gnu.org/ml/gcc-patches/2015-09/txtLiT8K2xyw4.txt

With chaining hashtables (and perhaps others), there continues to be a hash
flooding problem no matter how good the hash function: there's a timing attack
that can force the attackee to do some constant times n^1.5 computational steps
for n steps by the attacker.  Whether this attack matters in real life is
unclear to me, but I believe it is a realistic threat. By using a smarter data
structure one can avoid the n^1.5 worst case, and also use a fast hash function
when, happily, no hash flooding attack is in progress.

Meanwhile, is SipHash useful? Maybe. It is slow, so perhaps a more modern
competitor could be constructed, if one doesn't exist. On machines with fast
multiplication (and/or CRC, pshufb, SIMD, ...), one is likely better off using
those features, and SipHash does not get enough out of those features to be
speedy.

[Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash

[felix-glibc at fefe dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55815

--- Comment #5 from felix-glibc at fefe dot de ---
How about you add SipHash and make it selectable at runtime.
Then I can file security bugs against all relevant programs not
selecting it for being vulnerable and glibc has their ass covered
regarding performance.

I mean seriously, you argue performance for a security measure?
Does Google turn off stack cookies in production? ACL checks?
All this password checking is making our code slow?
I sure hope not.

Also: Do you have any actual benchmarks proving siphash would make a
noticeable impact?

[Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash

[miyuki at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55815

Mikhail Maltsev <miyuki at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |miyuki at gcc dot gnu.org

--- Comment #6 from Mikhail Maltsev <miyuki at gcc dot gnu.org> ---
SipHash is not very slow, BTW. I remember doing some benchmarks (there was some
discussion about changing the hash function used for incremental hash in GCC),
https://gcc.gnu.org/ml/gcc-patches/2015-03/msg00179.html

Result for small strings (1-20 bytes) on x86_64, elapsed time (i.e. less is
better):

function  | gcc -O3 | clang -O3
----------|---------|----------
murmur32  |   0.91  |   0.95 
murmur128 |   1.33  |   1.24 
sip24     |   1.88  |   1.45 
sip13     |   1.66  |   1.22 
lookup3   |   1.18  |   0.90 
spooky    |   1.24  |   0.90 

I don't remember all the details about the workload used and which
implementation of SipHash I used (but most likely my own one).

(In reply to felix-gcc from comment #0)
> It may even make sense to replace the hash code gcc itself uses, as there
> are now web pages where you can paste code and see which code gcc generates
> for it, turning this problem into a security issue if someone pastes code
> with colliding symbols to exploit this problem.

There is a much more efficient way to attack them: search GCC bugzilla for open
bugs of type "compile time hog" or "memory hog" and simply use the code
provided there.

[Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55815

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to felix-glibc from comment #5)
> I mean seriously, you argue performance for a security measure?
> Does Google turn off stack cookies in production? ACL checks?
> All this password checking is making our code slow?
> I sure hope not.

I asked Geoff to comment here, there's no need to attack strawmen.