Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Hash function can't handle leading zeroes #6136

Closed
mjoud opened this issue Jul 23, 2017 · 18 comments
Closed

Hash function can't handle leading zeroes #6136

mjoud opened this issue Jul 23, 2017 · 18 comments
Labels
Standard Library

Comments

@mjoud
Copy link

mjoud commented Jul 23, 2017 •
edited
Loading 

import hashes

var
  a = @[42]
  b = @[0, 42]
  c = @[0, 0, 0, 0, 0, 0, 42]

echo a.hash == b.hash  # true
echo a.hash == c.hash  # true

I don't know the significance of this, the sets and tables modules also takes length into consideration, but still.
@Araq
Copy link
Member

Araq commented Jul 24, 2017

definitely weird but collisions can always happen.

@krux02
Copy link
Contributor

krux02 commented Jul 25, 2017

when you know the hash function you can always construct collisions. Collisions can't be prevented. I would close this issue until shown that it is relevant.

@andreaferretti
Copy link
Collaborator

I don't agree. While the default hash functions are not cryptographic hashes, it is bad to be able to construct collisions trivially. This can lead to impredictable slowdonws when using tables, or even denial of service. Moreover the solution is easy (just take length into account)

@bluenote10
Copy link
Contributor

Wouldn't it be as simple as adding result = result !& x.len here (and maybe something similar for the two functions below).

@mjoud
Copy link
Author

mjoud commented Jul 27, 2017

So I did some reading and it appears that this was a very hot topic a couple a years back, after this presentation showing vulnerabilities in hashing algorithms used in multiple languages and libraries.

Nim is currently using Jenkins's One-at-a-time-hash function which, AFAICT, does not have known vulnerabilities. There is a problem, however, that the implementation is not seeded and it is relatively easy to generate malicious json files, for example, to mount a hash DoS-attack. Moreover, the algorithm operates on one byte at a time which makes unnecessarily slow compared to other algorithms.

The Python, Rust, Ruby and Perl 5 languages all use the SipHash algorithm. g++ uses the vulnerable MurmurHash2 in std::hash (used in std::unordered_map), for some reason. Ruby and Rust have transitioned from SipHash-2-4 to the faster SipHash-1-3, and Python is in progress. Perl 5 is transitioning to other hash functions. Interestingly, Perl until now used a hardened variant of the Jenkins's hash function, created after this 2003 bug report, when Perl was in a similar state as Nim is in now: using Jenkins's without seeding.

If I understand correctly, all the mentioned languages (except g++) use a random seed (read from /dev/urandom or similar) for hashes, generated at process start. Rust additionally uses a second seed (or "salt"/"pepper") for every unique hash table.

SipHash operate on 64 bits at a time and the hash value is uint64. Jenkins's is 32 bit, so currently the upper 32 bits are unused on 64-bit platforms. There are other very fast hashes out there, such as xxHash which has 32 and 64-bit variants.

Maybe it's time to step up and be proactive in this issue. A reasonable strategy would be to

  • use a faster and more recent hash function (Siphash/xxHash? See links below)
  • create a seed at process start (module-level)
  • perhaps make it possible for the user to seed every new hash table (bool useSeed, or even user-provided value defaulting to 0, no seed?)

Just my 2 cents.

Some random links:

@Araq
Copy link
Member

Araq commented Jul 28, 2017

SipHash sounds fine but an initial seed means these cannot be .noSideEffect (well we can trick the type checker of course) which requires a careful tradeoff. Also the compiler uses the same algorithm for string case statement hashings. In order to generate deterministic C code we cannot use a seed there at all.

@demerphq
Copy link

demerphq commented Sep 22, 2017 •
edited
Loading

One-At-A-Time-Hashing is broken from a security perspective. Since it is 32 bit it is trivial to generate arbitrary sets of colliding keys by pure brute force. Even worse, the way you guys use it, with a 0 seed, is completely insecure, as constructing arbitrary sets of collisions is as trivial as prefixing any string with an arbitrary set of null bytes. Adding a seed does not save you, as the last byte of the string is not properly mixed by Jenkins OAAT, which allows a seed discovery attack in less 2^32 operations. (The Perl core development team has code that discovers the seed for a seed Jenkins OAAT in an eyeblink.)

Even the "hardened" version of Jenkins OAAT that Perl has used for some years now is obsolete. (Using a 32 bit seed mixed with the length, combined with an additional random suffix added to each key.) It is well within the capabilities of a logic solver to find collisions.

I don't fully understand your use-case, but there are definitely better options available depending on what you want to do. But I am quite confident that what you are doing now is about the worst thing you could do.

FWIW, Perl has switched to using either Stadtx Hash, or Zaphod32 Hash, optionally combined with tabular hashing for short strings. Either way we seed the hash function randomly at process start. This has provided both a securty AND performance boost. One-At-A-Time hashes are not very efficient.

Yves (aka demerphq).

@demerphq
Copy link

@bluenote10: mixing the length into the hash state before hashing will help a bit, as it will ensure that the state is non-zero when the mixing function starts. However it is basically polishing a turd, any unseeded hash with a 32 bit state can be brute forced for collisions on a modern CPU in seconds.

@mjoud mjoud mentioned this issue Oct 29, 2017
Closed
@data-man
Copy link
Contributor

@mjoud

var
  a = @[42]
  b = @[0, 42]
  c = @[0, 0, 0, 0, 0, 0, 42]

echo a.hash
echo b.hash
echo c.hash

echo a.metroHash64
echo b.metroHash64
echo c.metroHash64

echo a.metroHash128
echo b.metroHash128
echo c.metroHash128

Ouput:

12871827045
12871827045
12871827045
2C17D80E6D0C2C41
6C685027F3404212
2C74D09BA49AC6F5
9AED6F1544CAD0691A66717F491E0798
BBB8668BA727F00CCE8EF3F67E6AD372
3D4A94FE5FC44338D2C761B40CBCF7F4

Benchmarks for @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]:

Hash function relative time/iter iters/s
GlobalBenchmark 5.25ns 190.32M
defaultHash 521.14ns 1.92M
metrohash64Context 186.95% 278.76ns 3.59M
metrohash64 131.88% 395.16ns 2.53M
metrohash128Context 181.16% 287.67ns 3.48M
metrohash128 102.46% 508.62ns 1.97M

@ghost
Copy link

ghost commented Oct 29, 2017

@data-man yeah, I'll close this after your PR will be merged :)

@data-man
Copy link
Contributor

@Yardanico
Then metrohash.nim should be in lib/pure.

@data-man
Copy link
Contributor

And I did not try it for the JS backend. Maybe it will not work there.

@ghost
Copy link

ghost commented Oct 29, 2017

@data-man ah, yes, it would probably not work since you're using unsafe casts and pointers

@data-man
Copy link
Contributor

Hmm, Hash (== int) size on x32 systems also 32-bit.

@demerphq
Copy link

demerphq commented Oct 30, 2017 via email

@data-man
Copy link
Contributor

data-man commented Oct 30, 2017 •
edited
Loading

@demerphq

What criteria did you use for your selection

SMhasher results, speed, simplicity, MIT License.

which metrohash functions do these names map to?

See original C++ sources: MetroHash

Benchmarking C version xxHash and my metroHash on pure Nim : benchHashes.nim

@demerphq
Copy link

demerphq commented Oct 31, 2017 via email

@mjoud mjoud mentioned this issue Dec 26, 2018
Closed
@Araq
Copy link
Member

Araq commented Jul 27, 2020

The hash function was changed.

@Araq Araq closed this as completed Jul 27, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Standard Library
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
7 participants
@demerphq @Araq @krux02 @data-man @andreaferretti @bluenote10 @mjoud