Alternative hash function #5146

funny-falcon · 2017-10-19T19:30:32Z

This is multiplicative function resilent to HashDos attack.
(Claim is bounded with restrictions that neither seed nor hash-value is exposed to attacker).

It provides good performance, and at least certainly not slower than current unsafe hasher's hash function.

This PR is alternative to #5104
(though I don't claim this function is alternative to SipHash in all possible SipHash's applications).

it is multiplicative function resilent to HashDos given following restriction is satisfied: - neither seed nor hash-value is exposed to atacker.

akzhan · 2017-10-20T03:14:28Z

src/crystal/hasher.cr

+  end
+
+  @[NoInline]
+  def string(value : Bytes)


it should be named def slice(value : Bytes)

It is for the case, when slice of bytes is a string.
Ok, maybe it could be def bytes(value : Bytes) ?

Yes, def bytes(value : Bytes) or just def bytes(value) since other methods don't specify a type either.

@ysbaddaden , should I make Slice(UInt8)#hash to use hasher.bytes(self) as you did in 7733d3e ?

asterite · 2017-10-20T10:31:09Z

Can we include a reference or link to somewhere that explains the algorithm?

funny-falcon · 2017-10-20T10:55:47Z

There is derived from my https://github.com/funny-falcon/funny_hash/blob/master/README.md

There is no formal description, though.

It is two multiplicative hash combined that uses different multiplicative constants, and ensures that every block bit affects at least 20 state bits. Guarantee cames from fact both 32bit halves of 64bit block affects are mixed into low 32bits of state halves before multiplication.
Resistance to HashDos came from mixing other half of block into high 32bit of state halves before multiplication, and state halves are rotated between blocks. And from unknown secure random initial state.

Looking at https://en.m.wikipedia.org/wiki/Universal_hashing I see some similarity with hashing vectors.

Lets be clear. I will not spend my time in debates again. I have no formal verification, I never wrote and published any paper on this.
If you are not going to accept the algorithm, please, close this PR now.

akzhan · 2017-10-20T10:57:51Z

Looks like https://github.com/funny-falcon/funny_hash -

Simple multiplicative hash function like Murmur3 but a bit safer.

It is safer cause it uses state twice larger than block size, feeds block twice at time and every bit affects at least 10/20 bits of a state. So it is impossible to revert change without introducing other change, and I think it is hardly possible to make seed independent collisions (which is the main defect of Murmur2/Murmur3).

So it is safe for use in a internal hash table implementations when nor seed nor hashsum is known to attacker.

(but it is certainly not cryptographic: I think attack with choosen plaintext and known hashsum will succeed with little effort)

Because it like Murmur3 I provide some implementations that use MurMur3 (but Murmur3 has some known defects while Funny hash - not yet): It has been adopted into a number of open-source projects, most notably libstdc++ (ver 4.6), nginx (ver 1.0.1), Rubinius, libmemcached (the C driver for Memcached), npm (nodejs package manager), maatkit, Hadoop, Kyoto Cabinet, RaptorDB, OlegDB, Cassandra, Solr, vowpal wabbit, Elasticsearch, and Guava.

akzhan · 2017-10-20T11:40:43Z

I vote for this hashing function just because it makes us faster than Go, Rust etc. :)

funny-falcon · 2017-10-20T12:17:23Z

it makes us faster than Go, Rust etc. :)

Not faster than Go, actually. Their aes-ni function is super fast on long strings, and probably doesn't suck on short.
Their non-aes-ni based function has quite close performance to mine for short strings, and faster on long strings (cause they hashes 4 blocks at once).

https://github.com/golang/go/blob/master/src/runtime/hash64.go

But their function is longer to code, uses larger state for long strings, and I don't think non-aes variant is safer than my function.

Note, they have specialization for hashing single Int32 and single Int64 (memhash32, memhash64).

They are more free in choosing functions, and their specializations, cause Go doesn't give any ability to provide custom hash functions. All hash calculation is controlled by runtime, and could not be overriden.

ysbaddaden · 2017-10-20T15:32:21Z

I hashed a dictionary of 216 555 English words:

crystal 0.23.1 (UInt64): 5 collisions (1:1)
crystal master (UInt64): 0 collisions (!!!)
siphash-1-3 (UInt64): 0 collisions
halfsiphash-1-3 (UInt64): 0 collisions
halfsiphash-1-3 (UInt32): 4 collisions (1:1)
~~this branch (Int32): 9216 collisions (1:455)~~
this branch (Int32): 0 collisions

~~What!?~~

EDIT I got the list of english words from this outstanding answer: https://softwareengineering.stackexchange.com/a/145633

EDIT 2: that's better :)

funny-falcon · 2017-10-20T16:42:07Z

@ysbaddaden , thank you. I've pushed fix.
Checked with https://gist.github.com/funny-falcon/0f61703123f56e35b8f4c9a66c8f13cc

funny-falcon · 2017-10-20T17:00:48Z

@ysbaddaden , and I've pushed your commit with specialization for Slice(UInt8)

ysbaddaden · 2017-10-20T17:02:42Z

Down to zero collisions, that's better!

I'm trying to check distribution, now :)

ysbaddaden · 2017-10-20T19:04:11Z

Distribution results for English dictionary of 216 555 words (see a previous comment) :

0.23.1	master	siphash	funny

I can't notice differences between siphash-1-3 and funny_hash 👍

akzhan · 2017-10-20T19:57:54Z

LGTM and I want it in master branch.

It is prerequisite for fast hashes.

ysbaddaden · 2017-10-20T20:09:20Z

I miss specs for the funny hash algorithm against static vectors, just to make sure we don't reintroduce a bug later (such as the collisions above).

asterite · 2017-10-20T20:13:39Z

Also, a link to https://github.com/funny-falcon/funny_hash inside the implementation (not in public docs)

asterite · 2017-10-20T21:23:20Z

@ysbaddaden By the way, really cool graphs! How did you generate them? (and what code did you use?)

akzhan · 2017-10-21T09:31:56Z

src/crystal/hasher.cr

+  # and then combines them with addition. It greatly reduce
+  # possibility of state deduction.
+  #
+  # Note, it provides good protection from HashDos iif:


No. iif -> iff
https://en.m.wikipedia.org/wiki/If_and_only_if

Or write it without abbreviations?

ysbaddaden · 2017-10-21T13:06:18Z

For fun, I checked distribution a little more, with 200 000 random UUIDs and 42 614 numbers (american zip codes). I got 8 collisions for UUIDs on Crystal 0.23.1, no collisions otherwise.

SipHash and FunnyHash feel similar in their distribution.

UUIDs (overall distribution is good because /dev/urandom has good distribution, I guess):

0.23.1	master	siphash	funny

Numbers (the result is so biased on master hashes end up at two x,y spots):

0.23.1	master	siphash	funny

Conclusion: switching to funny hash or siphash will really help avoid concentration in real world scenarios, when keys are poorly distributed, not just mitigating hash flooding attacks.

@asterite I used SDL, see https://gist.github.com/ysbaddaden/fccf87d4ca22082c7d645b9f547a9713

funny-falcon · 2017-10-27T11:42:14Z

Changed tests.

Sija · 2017-10-27T11:43:03Z

spec/std/crystal/hasher_spec.cr

+      [hasher, hasher1, hasher2, hasher12]
+        .map(&.result)
+        .combinations(2)
+        .each do |(a, b)|


Wrong indentation here, and in other cases below. Also, I think it'd look better as:

[hasher, hasher1, hasher2, hasher12] .map(&.result) .combinations(2) .each { |(a, b)| a.should_not eq(b) }

You you sure, @Sija?

➜ crystal git:(althasher) ✗ bin/crystal tool format src spec Using compiled compiler at `.build/crystal' ➜ crystal git:(althasher) ✗ gd ➜ crystal git:(althasher) ✗

@akzhan yes I am, block body SHOULD be indented, yet it's not. Perhaps it's a formatter bug?

But idea with {} blocks on (should) looks better.

crystal tool format made this indentation.

Using curly braces here is semantically wrong: assertion is an action, not computation or transformation.

But if you insist, I will change to curly braces. Should I?

@funny-falcon lets stay things as is. they automatically fixed with fixes on the formatter.

/cc @makenowjust

block body SHOULD be indented, yet it's not. Perhaps it's a formatter bug?

It is indented relative to statement level. It is not a bug, just current rules. May be rule should be changed, but which way?

May be, method calls should be indented by 4 spaces?

[hasher, hasher1, hasher2, hasher12] .map(&.result) .combinations(2) .each do |(a, b)| a.should_not eq(b) end

@luislavena IMO there are 2 separate issues here: formatter bug and bad readability of do ... end version of block bodies - first one should be handled in separate PR, yet the second one results in badly readable code and could be fixed, so why not do it?

is matter of multi-line vs one-line block bodies, not the "actionable" intent,

There are different points of view on this question. I prefer curly braces only for "one-line non-actionable".

But, ok, I've changed to curly braces.

PLEASE, let's not discuss such small syntax details. If the specs pass it's OK. This only makes the contributor feel tired and annoyed about stuff that doesn't really matter.

There's no formatter bug, the expression starts at indent 0 and the block is at indent 2.

RX14 · 2017-10-27T13:46:58Z

I'm not sure why we've suddenly abstracted the implementation from Crystal::Hasher. Did anyone ask for this? What's the point when the implementation isn't replacable? It just seems that now Crystal::Hasher is a pointless class which does nothing but forward stuff to the hasher?

asterite · 2017-10-27T13:49:43Z

@RX14 You are right, just now I see that change. There should just be Crystal::Hasher, wth :nodoc: so it's hidden from users, but still testable, and that type should have the @a and @b instance vars. The hasher is not meant to be specified or overriden by the user. It's the only hasher that we'll ever use.

luislavena · 2017-10-27T13:51:15Z

@RX14, @asterite perhaps the wording of this comment was the issue?

RX14 · 2017-10-27T13:55:23Z

It's fine to leave just Crystal::Hasher with the implementation, and have 2 "parts" to the test suite - ones which test the hash properties, and ones which use test vectors.

asterite · 2017-10-27T13:55:24Z

@luislavena Probably.

I think we have an issue where someone sends a PR and gets many comments saying "Please do this, please do that" and the sender just says "OK, OK" and does it, without first having a good discussion about whether that should be done or not. Who decides it? It's pretty hard. I see this happen in many PRs already.

I don't know what the solution is. Maybe not rush doing changes before we finish agreeing on them.

akzhan · 2017-10-27T14:11:57Z

Next step is near - FAST hashes :)

funny-falcon · 2017-10-27T14:22:58Z

Lets border line:

tests are ok?
should I change back to monolit Crystal::Hasher (ie without separate Crystal::Hasher::FunnyHash64) ?
is there anything else to do with this PR?

I rush cause I'm not always understand clearly what is asked to do, but I agree with some part of.
So, I try to shorten iteration to get reaction, and fix it later.

Another reason, why I rush, is cause discussion could last forever. I also like to discuss a lot.
With actual changes it is better seen, which version looks better. Therefore, it is easier to come to agreeingment.

asterite · 2017-10-27T14:53:36Z

My opinion:

tests looks very good now
we should change Crystal::Hasher to be a monolith, no need for a separate Crystal::Hasher::FunnyHash64

Once that's done I think we can merge this. If others agree please 👍 on this comment. Once we have enough 👍 here I guess you can do that and then we can merge 😄 🎉

Just to prevent occasional disclosure of state, hide it in `def inspect`. It will not prevent intentional disclosure, though, because state can be easily inspected, and `to_s` could be redefined.

funny-falcon · 2017-10-27T16:13:23Z

Ok, returned to monolith.

I've added another one small change, excuse me for that:

I've hidden internal state in inspect function to prevent occasional state disclosure.

Sija · 2017-10-27T16:30:41Z

spec/std/crystal/hasher_spec.cr

+  B
+end
+
+alias THasher = Crystal::Hasher


TestHasher plz :)

akzhan · 2017-10-30T01:18:01Z

src/crystal/hasher.cr


  def nil
+    @a += @b
+    @b += 1


Earlier you use LFSR here, it is not wanted anymore?

Both state variable should change in some way.

Combination of addition on @A and lsfr on @b gives period almost 2**128. That is great, but unnecessary.

Current version is "quadrating probing", and gives period 2**64. I think, it is just enough.

Even 2**32 could be enough for intended use case, because if someone triggers 2**32 calls to nil.hash(hasher),

if some triggers 2**32 calls to nil.hash(hasher), they are already successful at DoS-ing.

RX14 · 2017-10-30T18:30:22Z

🎉 🎉 🎉

add specialization for string(Bytes)

e491d64

funny-falcon mentioned this pull request Oct 19, 2017

Add (Half)SipHash PRF and integrate it into Crystal::Hasher #5104

Closed

use multiplicative HashDos proof function

49dd92e

it is multiplicative function resilent to HashDos given following restriction is satisfied: - neither seed nor hash-value is exposed to atacker.

funny-falcon force-pushed the althasher branch from db221fb to 49dd92e Compare October 19, 2017 20:42

akzhan reviewed Oct 20, 2017

View reviewed changes

akzhan mentioned this pull request Oct 20, 2017

Reimplementation a Hash using open addressing #4557

Closed

hasher: fix for tail reading

5ca5f2a

funny-falcon and others added 2 commits October 20, 2017 19:56

hasher: rename string(value: Bytes) to bytes(value)

ec5859a

Optimize Bytes#hash and keep slow Slice(T)#hash

782a4ee

hasher: lets crystal+llvm decide about inlining.

981f1d4

funny-falcon added 2 commits October 21, 2017 03:08

hasher: description of algorithm

98e6696

hasher: add primitive sanity spec for hasher

78fc3e9

funny-falcon force-pushed the althasher branch from b8a4bc3 to 78fc3e9 Compare October 21, 2017 00:49

akzhan reviewed Oct 21, 2017

View reviewed changes

hasher: fix a bit algorithm notes

3e2f0bf

hasher: change test to deterministic. Separate algorithm implementaton.

d1c9e45

Sija reviewed Oct 27, 2017

View reviewed changes

akzhan approved these changes Oct 27, 2017

View reviewed changes

some formatting

79fb9c7

Sija mentioned this pull request Oct 27, 2017

Formatter indentation bug #5193

Closed

funny-falcon added 2 commits October 27, 2017 19:03

hasher: revert to monolith Crystal::Hasher

fa7f34f

hasher: hide internal state.

c709970

Just to prevent occasional disclosure of state, hide it in `def inspect`. It will not prevent intentional disclosure, though, because state can be easily inspected, and `to_s` could be redefined.

funny-falcon force-pushed the althasher branch from 3711529 to c709970 Compare October 27, 2017 16:13

Sija reviewed Oct 27, 2017

View reviewed changes

hasher: s/THasher/TestHasher/

aacea85

RX14 approved these changes Oct 27, 2017

View reviewed changes

akzhan reviewed Oct 30, 2017

View reviewed changes

asterite approved these changes Oct 30, 2017

View reviewed changes

RX14 approved these changes Oct 30, 2017

View reviewed changes

RX14 added kind:feature topic:stdlib labels Oct 30, 2017

RX14 added this to the Next milestone Oct 30, 2017

RX14 merged commit fbab3a3 into crystal-lang:master Oct 30, 2017

hugoabonizio mentioned this pull request Nov 24, 2017

Disallows while true crystal-ameba/ameba#22

Merged

Alternative hash function #5146

Alternative hash function #5146

Conversation

funny-falcon commented Oct 19, 2017

akzhan Oct 20, 2017 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

funny-falcon Oct 20, 2017 • edited

Choose a reason for hiding this comment

asterite commented Oct 20, 2017

funny-falcon commented Oct 20, 2017

akzhan commented Oct 20, 2017 • edited

akzhan commented Oct 20, 2017

funny-falcon commented Oct 20, 2017

ysbaddaden commented Oct 20, 2017 • edited

funny-falcon commented Oct 20, 2017

funny-falcon commented Oct 20, 2017

ysbaddaden commented Oct 20, 2017

ysbaddaden commented Oct 20, 2017 • edited

akzhan commented Oct 20, 2017 • edited

ysbaddaden commented Oct 20, 2017

asterite commented Oct 20, 2017

asterite commented Oct 20, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ysbaddaden commented Oct 21, 2017

funny-falcon commented Oct 27, 2017

Sija Oct 27, 2017 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Sija Oct 27, 2017 • edited

Choose a reason for hiding this comment

akzhan Oct 27, 2017 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

akzhan Oct 27, 2017 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

asterite Oct 27, 2017 • edited

Choose a reason for hiding this comment

RX14 commented Oct 27, 2017

asterite commented Oct 27, 2017

luislavena commented Oct 27, 2017

RX14 commented Oct 27, 2017 • edited

asterite commented Oct 27, 2017

akzhan commented Oct 27, 2017 • edited

funny-falcon commented Oct 27, 2017

asterite commented Oct 27, 2017

funny-falcon commented Oct 27, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Sija Oct 27, 2017 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

RX14 commented Oct 30, 2017

akzhan Oct 20, 2017 •

edited

funny-falcon Oct 20, 2017 •

edited

akzhan commented Oct 20, 2017 •

edited

ysbaddaden commented Oct 20, 2017 •

edited

ysbaddaden commented Oct 20, 2017 •

edited

akzhan commented Oct 20, 2017 •

edited

Sija Oct 27, 2017 •

edited

Sija Oct 27, 2017 •

edited

akzhan Oct 27, 2017 •

edited

akzhan Oct 27, 2017 •

edited

asterite Oct 27, 2017 •

edited

RX14 commented Oct 27, 2017 •

edited

akzhan commented Oct 27, 2017 •

edited

Sija Oct 27, 2017 •

edited