Feature #13017: Switch SipHash from SipHash24 to SipHash13

• Status: Closed
• Assignee: -
• Target version: -

[funny_falcon (Yura Sokolov)]

SipHash13 is secure enough to be used in hash-tables, and SipHash's author confirms that.
Rust already considered switch to SipHash13:
https://github.com/rust-lang/rust/issues/29754#issue-116174313
Jean-Philippe Aumasson confirmation:
https://github.com/rust-lang/rust/issues/29754#issuecomment-156073946
Merged pull request:
https://github.com/rust-lang/rust/pull/33940

Github pull request https://github.com/ruby/ruby/pull/1501

[normalperson (Eric Wong)]

[e-mail] wrote:

Feature #13017: Switch SipHash from SipHash24 to SipHash13
https://bugs.ruby-lang.org/issues/13017

I think the wrong patch was uploaded to redmine:

---Files--------------------------------
0001-load.c-reduce-memory-usage-of-loaded_features_index.patch (5.87 KB)

[funny_falcon (Yura Sokolov)]

• File deleted (0001-load.c-reduce-memory-usage-of-loaded_features_index.patch)

[funny_falcon (Yura Sokolov)]

• File 0001-switch-SipHash-from-SipHash24-to-SipHash13-variant.patch 0001-switch-SipHash-from-SipHash24-to-SipHash13-variant.patch added

[funny_falcon (Yura Sokolov)]

Eric, you are right. Excuse me for that.
Just uploaded right version.

[vmakarov (Vladimir Makarov)]

Since we removed recently the code switching weak/strong hashes, the speed of the strong hash (siphash24) became important.

According to my measurements on i7-4790K, Switching from siphash24 to siphash13 improves MRI hash table benchmarks by about 2.4% (siphash14 results in 0.7% increase). So I am in favor of this patch.

As for the security, it is more important to keep the seed secret and to change it for each MRI run. Best crypto-analisys for the final round of siphash consisting of 4 compressing steps is a distinguisher of complexity 2^35 to differ the final round function from a pseudo-random function. Siphash-13 has at least 4 compressing steps. IMHO such complexity makes no sense for a collision attack for one instance of running MRI.

[ko1 (Koichi Sasada)]

Who has a ball?

[funny_falcon (Yura Sokolov)]

@ko1 (Koichi Sasada) , I think, a ball is yours.

[ko1 (Koichi Sasada)]

Sorry I can't get a ball because

• I can't evaluate security strength.
• I have no time to do that.

Could someone take over this issue?

I'm not sure it should be in 2.4 or 2.5. If only a few impact, I suggest to introduce this feature for ruby 2.5.

Thanks,
Koichi

[funny_falcon (Yura Sokolov)]

But you can read what SipHash author (Jean-Philippe Aumasson) said about this in Rust discussion (link in issue text).

And Vladimir cites the best known attack is just "distinguisher" ie "attacker may differentiate output of SipHash13 from pure random". Given it is already known that ruby uses SipHash, attacker will not know anything new.

[funny_falcon (Yura Sokolov)]

Correction: not 'best' but single known attack is distinguisher.

[shyouhei (Shyouhei Urabe)]

We looked at this issue at today's developer meeting. However there were no cryptological experts. We could not be sure about the safety of this change.

SipHash24 is slower, but it seems stronger than SipHash13 to me. So I think it is at least safe to remain in current implementation. Why not consider merging this in 2.5?

[mame (Yusuke Endoh)]

Indeed we are not cryptological experts, then how did we determine to introduce SipHash24? I couldn't find any discussion. I think Yura will want to know the condition.

[shyouhei (Shyouhei Urabe)]

You can't find the discussion about SipHash24 because (1) it was security-related, and (2) there was no other choice than SipHash24 when we did.

I remember SipHash24 was introduced to fix CVE-2012-5371. I read the SipHash paper back then https://131002.net/siphash/siphash.pdf . At that time, 24 was almost the only variant of SipHash series that experienced in-detail analysis. The paper focuses on "SipHash-2-4" (what we call SipHash24) but doesn't even mention 13 variant. So 24 was the only choice we could use.

Now. Time passed, we face another possible variant SipHash13. As far as I understand 13 is weaker than 24. But no idea how weak. It might just be okay. But as I don't understand the advantage / disadvantage tradeoff well, I'm afraid to rush commit this.

[shyouhei (Shyouhei Urabe)]

I was learning about SipHash13 this holiday season.

I understand that the whole concept of using SipHash as hash function of hash tables is to resist hashDoS-analogous attacks. If hashDoS aws not a problem then we could use more fast-but-insecure hash function at will. Then how about SipHash13? The SipHash author says SipHash13 is fast and safe, but so far I have not been successful to find any reason why. To be fair I also have not found any evidence that it is insufficient. Instead, I found that HighwayHash author published a paper very recently https://arxiv.org/pdf/1612.06257.pdf which includes some empirical experiments against SipHash13 (seems no problem to me).

At this point I think we have 2 options (1) trust the author anyways, or (2) ask him to disclose the reason behind his opinion. My private feeling is that "it's fine because someone says it's fine" does not sound like a security decision. But if we decide to give it a try, it is also OK to me because SipHash13 does seem safe to me (from an amateur point of view).

[funny_falcon (Yura Sokolov)]

Crypto-analyse of SipHash (and best result for SipHash13)
https://eprint.iacr.org/2014/722.pdf

[shyouhei (Shyouhei Urabe)]

Yura Sokolov wrote:

Crypto-analyse of SipHash (and best result for SipHash13)
https://eprint.iacr.org/2014/722.pdf

Thank you for the info. From what I read the "best result" the paper says for SipHash13 is collision probability of 2^-167. Because SipHash's internal state has 256 bits length, birthday attack against it finds collision in 2^-128 probability.

In short the paper says SipHash13 has no efficient way to attack (yet). To me it's now OK to say SipHash13 has enough evidence to be safe. Let me +1.

[shyouhei (Shyouhei Urabe)]

• Status changed from Open to Assigned
• Assignee set to shyouhei (Shyouhei Urabe)

[matz (Yukihiro Matsumoto)]

• Status changed from Assigned to Open
• Assignee deleted (shyouhei (Shyouhei Urabe))

We are sure now by information provided by @funny_falcon (Yura Sokolov). Thank you.
Go ahead and merge the patch.

Matz.

[shyouhei (Shyouhei Urabe)]

• Status changed from Open to Closed

Applied in changeset r57382.

---

switch SipHash from SipHash24 to SipHash13 variant

SipHash13 is secure enough to be used in hash-tables,
and SipHash's author confirms that.
Rust already considered switch to SipHash13:
https://github.com/rust-lang/rust/issues/29754#issue-116174313
Jean-Philippe Aumasson confirmation:
https://github.com/rust-lang/rust/issues/29754#issuecomment-156073946
Merged pull request:
https://github.com/rust-lang/rust/pull/33940

From: Sokolov Yura aka funny_falcon [e-mail]
Date: Thu, 8 Dec 2016 20:31:29 +0300
Signed-off-by: Urabe, Shyouhei [e-mail]
Fixes: [Feature #13017]

[byroot (Jean Boussier)]

• Related to Misc #21833: Switch default hash from SipHash13 to XXH3? added