yangl1996
commented
3 weeks ago Hi Doug,
Thanks for your interest and the comments!
Let me make sure that I understood the attack correctly. I guess what you did to generate the malicious workload is
- Pre-compute the SipHash for a bunch of numbers, say, 1 to 10000.
- Generate Alice's set arbitrarily. You used {1, 2, ..., 32}.
- Find Bob's set {x1, x2, ..., xn}, a subset of {1, 2, ..., 10000}, such that Hash(x1) ^ Hash(x2) ^ ... ^ Hash(xn) == Hash(1) ^ Hash(2) ^ ... ^ Hash(32). This is a linear system; each bit converts to a linear equation and the coefficients are 0 or 1.
I believe that the gist of the attack is still hash collision––finding a set of items such that the sum of their hashes collides with the hash of the victim. (In your attack the victim is the entire set of Alice.) Maybe I was misunderstanding but this is not fundamentally different from the attack we described in the paper, which is crafting hash collisions? I do understand that such a collision is easier to craft, since you can precompute the candidates and use Gaussian Elimination to find which ones to use.
You correctly pointed out that such attacks are mitigated using a keyed hash function. Indeed, if I change the key for SipHash (line 24) to something else, the malicious workload stops working.
In my opinion, your paper is not clear enough about this trade-off and a casual reader is likely to come away with the impression that RIBLT currently provides both universality and censorship-resistance, when it's actually one or the other.
That's a fair point! I will update the paper accordingly. Thanks for the suggestion!
Last thing: Is the code for your Ethereum synchronisation evaluation available anywhere? I didn't notice a link in the paper and couldn't find it on your github.
No I have not published the code.
hoytech
AljoschaMeyer
Hi Lei,
I just came across your RIBLT paper and for the most part I thought it was compelling and clear, and the scheme described has tremendous potential. However, I believe it contains a misunderstanding about the adversarial threat model:
If this was the threat in question then it would be trivially solvable by using a cryptographically secure hash function, or at least detectable via the corrupted sum field. Instead, the primary threat we are worried about is a malicious user selecting a set of non-colliding values chosen such that combined they cancel out one or more victim elements, silently censoring them by preventing their reconciliation. These malicious values can be selected at negligible cost using gaussian elimination.
In case it is useful to you, I made a test-case to demonstrate this. In
example_test.go, replace the sets to be reconciled with the following:None of these values result in a SipHash collision, and the sum field is never corrupted. Your algorithm incorrectly signals that these sets are equivalent and that no items need to be transferred. Note that this same attack would be possible even if you replaced SipHash with a secure 256-bit hash function.
Your suggestion to use a keyed hash function and for Alice and Bob to coordinate a session-specific secret-key is valid and does prevent this attack. However, this comes at the cost of breaking universality. As you mention several times, the universal applicability of coded symbols is highly desirable because for large data-sets, re-keying every session would have unacceptable CPU, memory, and I/O costs.
In my opinion, your paper is not clear enough about this trade-off and a casual reader is likely to come away with the impression that RIBLT currently provides both universality and censorship-resistance, when it's actually one or the other.
Last thing: Is the code for your Ethereum synchronisation evaluation available anywhere? I didn't notice a link in the paper and couldn't find it on your github.
Thank you!
Doug