* [Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash
2012-12-26 21:39 [Bug libstdc++/55815] New: switch hash function of libstdc++ hash tables to siphash felix-gcc at fefe dot de
@ 2013-01-05 13:29 ` redi at gcc dot gnu.org
2013-01-05 14:35 ` redi at gcc dot gnu.org
` (5 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: redi at gcc dot gnu.org @ 2013-01-05 13:29 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash
2012-12-26 21:39 [Bug libstdc++/55815] New: switch hash function of libstdc++ hash tables to siphash felix-gcc at fefe dot de
2013-01-05 13:29 ` [Bug libstdc++/55815] " redi at gcc dot gnu.org
@ 2013-01-05 14:35 ` redi at gcc dot gnu.org
2013-01-05 14:48 ` paolo.carlini at oracle dot com
` (4 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: redi at gcc dot gnu.org @ 2013-01-05 14:35 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash
2012-12-26 21:39 [Bug libstdc++/55815] New: switch hash function of libstdc++ hash tables to siphash felix-gcc at fefe dot de
2013-01-05 13:29 ` [Bug libstdc++/55815] " redi at gcc dot gnu.org
2013-01-05 14:35 ` redi at gcc dot gnu.org
@ 2013-01-05 14:48 ` paolo.carlini at oracle dot com
2015-09-22 22:11 ` gpike at google dot com
` (3 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: paolo.carlini at oracle dot com @ 2013-01-05 14:48 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash
2012-12-26 21:39 [Bug libstdc++/55815] New: switch hash function of libstdc++ hash tables to siphash felix-gcc at fefe dot de
` (2 preceding siblings ...)
2013-01-05 14:48 ` paolo.carlini at oracle dot com
@ 2015-09-22 22:11 ` gpike at google dot com
2015-09-23 2:08 ` felix-glibc at fefe dot de
` (2 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: gpike at google dot com @ 2015-09-22 22:11 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash
2012-12-26 21:39 [Bug libstdc++/55815] New: switch hash function of libstdc++ hash tables to siphash felix-gcc at fefe dot de
` (3 preceding siblings ...)
2015-09-22 22:11 ` gpike at google dot com
@ 2015-09-23 2:08 ` felix-glibc at fefe dot de
2015-09-23 3:29 ` miyuki at gcc dot gnu.org
2015-09-23 9:56 ` redi at gcc dot gnu.org
6 siblings, 0 replies; 8+ messages in thread
From: felix-glibc at fefe dot de @ 2015-09-23 2:08 UTC (permalink / raw)
To: gcc-bugs
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?
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash
2012-12-26 21:39 [Bug libstdc++/55815] New: switch hash function of libstdc++ hash tables to siphash felix-gcc at fefe dot de
` (4 preceding siblings ...)
2015-09-23 2:08 ` felix-glibc at fefe dot de
@ 2015-09-23 3:29 ` miyuki at gcc dot gnu.org
2015-09-23 9:56 ` redi at gcc dot gnu.org
6 siblings, 0 replies; 8+ messages in thread
From: miyuki at gcc dot gnu.org @ 2015-09-23 3:29 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/55815] switch hash function of libstdc++ hash tables to siphash
2012-12-26 21:39 [Bug libstdc++/55815] New: switch hash function of libstdc++ hash tables to siphash felix-gcc at fefe dot de
` (5 preceding siblings ...)
2015-09-23 3:29 ` miyuki at gcc dot gnu.org
@ 2015-09-23 9:56 ` redi at gcc dot gnu.org
6 siblings, 0 replies; 8+ messages in thread
From: redi at gcc dot gnu.org @ 2015-09-23 9:56 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread