Feature #13017
closed
- File deleted (
0001-load.c-reduce-memory-usage-of-loaded_features_index.patch)
Eric, you are right. Excuse me for that.
Just uploaded right version.
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.
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
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.
Correction: not 'best' but single known attack is distinguisher.
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?
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.
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.
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).
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.
- Status changed from Open to Assigned
- Assignee set to shyouhei (Shyouhei Urabe)
- Status changed from Assigned to Open
- Assignee deleted (
shyouhei (Shyouhei Urabe))
- Status changed from Open to Closed
Also available in: Atom
PDF