What hash functions should be included in a hypothetical Boost hash-v2 library?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

What hash functions should be included in a hypothetical Boost hash-v2 library?

Boost - Dev mailing list
What (non-cryptographic) hash functions should a hypothetical future Boost
hash library contain? Have clear winners emerged by now? Which ones do
people prefer?

SipHash is basically a given, but it's not optimized for speed.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: What hash functions should be included in a hypothetical Boost hash-v2 library?

Boost - Dev mailing list
I use personally MurmurHash3 because I found open implementations both at
compile-time and runtime.

Le 31 déc. 2017 01:29, "Peter Dimov via Boost" <[hidden email]> a
écrit :

> What (non-cryptographic) hash functions should a hypothetical future Boost
> hash library contain? Have clear winners emerged by now? Which ones do
> people prefer?
>
> SipHash is basically a given, but it's not optimized for speed.
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman
> /listinfo.cgi/boost
>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: What hash functions should be included in a hypothetical Boost hash-v2 library?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 12/31/17 01:28, Peter Dimov via Boost wrote:
> What (non-cryptographic) hash functions should a hypothetical future
> Boost hash library contain? Have clear winners emerged by now? Which
> ones do people prefer?

I vote for FNV hashes:

 
https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: What hash functions should be included in a hypothetical Boost hash-v2 library?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On December 31, 2017 3:29:07 AM Peter Dimov via Boost
<[hidden email]> wrote:

> What (non-cryptographic) hash functions should a hypothetical future Boost
> hash library contain? Have clear winners emerged by now? Which ones do
> people prefer?
>
> SipHash is basically a given, but it's not optimized for speed.

There are a number of widely used hash functions. I often use MurmurHash or
one-at-a-time for their speed and simplicity. CityHash is also known and
I've just discovered its successor, FarmHash.




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: What hash functions should be included in a hypothetical Boost hash-v2 library?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Sat, Dec 30, 2017 at 7:28 PM, Peter Dimov via Boost <
[hidden email]> wrote:

> What (non-cryptographic) hash functions should a hypothetical future Boost
> hash library contain? Have clear winners emerged by now? Which ones do
> people prefer?
>
> SipHash is basically a given, but it's not optimized for speed.
>
>
I would assume that as many hash algorithms as possible would be added
eventually.  We already have MD5 and SHA1 in Boost.Uuid.
More important to me is the concept definition so that all the hash
algorithms can be used easily in a variety of ways.

- Jim

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: What hash functions should be included in a hypothetical Boost hash-v2 library?

Boost - Dev mailing list
On Sun, Dec 31, 2017 at 7:22 AM, James E. King, III via Boost
<[hidden email]> wrote:
> On Sat, Dec 30, 2017 at 7:28 PM, Peter Dimov via Boost <
>> What (non-cryptographic) hash functions should a hypothetical future Boost
>> hash library contain? Have clear winners emerged by now? Which ones do
>> people prefer?

Each hash function has its own strengths and weaknesses. Some are
optimized for 64-bit or have specific 64-bit implementations. Others
work well for small keys. Some work well for fixed size keys, or work
better with aligned data. These are popular:

* xxhash
* spooky
* fnv

The design of xxhash allows cost-free initialization of the hash
function with a random salt to prevent algorithmic complexity attacks.
Whether or not a hash function can be hardened in this fashion is also
a distinguishing characteristic that should be documented and provided
as an option.

For hash functions which don't support a built-in salt it is trivial
to write a wrapper which first hashes a generated value and then
hashes the rest of the user defined data, this wrapper would work with
any Hasher at the expense of some performance.

> We already have MD5 and SHA1 in Boost.Uuid.

Those are cryptographic hash functions. We need to be careful with
exposing interfaces which claim to do cryptographic hashing, because
the results of cryptographic hashing are usually desired to be
portable (same on all machines) and use a particular serialization
method. A hashing framework for use with unordered containers usually
does not allow the user to define the format of serialized objects
(nor should it).

On Sun, Dec 31, 2017 at 7:21 AM, Andrey Semashev via Boost
<[hidden email]> wrote:
> I often use MurmurHash

Murmur is vulnerable to algorithmic complexity attacks:

http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/

Thanks

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: What hash functions should be included in a hypothetical Boost hash-v2 library?

Boost - Dev mailing list
On December 31, 2017 7:06:08 PM Vinnie Falco via Boost
<[hidden email]> wrote:
>
> On Sun, Dec 31, 2017 at 7:21 AM, Andrey Semashev via Boost
> <[hidden email]> wrote:
>> I often use MurmurHash
>
> Murmur is vulnerable to algorithmic complexity attacks:
>
> http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/

MurmurHash is not intended to be cryptographically secure. Where the hash
can be applied to external data you probably want a more secure function.





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: What hash functions should be included in a hypothetical Boost hash-v2 library?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Vinnie Falco wrote:

> Murmur is vulnerable to algorithmic complexity attacks:
>
> http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/

I don't think that xxHash is any stronger; they just didn't analyze it. They
broke Murmur and CityHash not because these two are weaker than xxHash, but
because they looked at Murmur and CityHash and didn't look at xxHash.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost