4
$\begingroup$

I'm very new to cryptography, and I need help understanding the security claims made in Aumasson and Bernstein's paper on the SipHash. In particular, I'm trying to understand the following statement at the end of section 3 (p. 6):

We comment that SipHash is not meant to be, and (obviously) is not, collision-resistant.

I don't understand this statement as well as I wish. First, I do understand that collision resistance is, strictly speaking, a property of hash functions and that SipHash in spite of the name is a MAC, not a cryptographic hash, so its security requirements are different. The paper explicitly sets the security requirement out elsewhere:

A message-authentication code (MAC) produces a tag t from a message m and a secret key k. The security goal for a MAC is for an attacker, even after seeing tags for many messages (perhaps selected by the attacker), to be unable to guess tags for any other messages. [p. 1]

Where I'm confused now is: if collision resistance is strictly speaking a property of hash functions and not of MACs, what does it mean to say that "SipHash is not meant to be, and (obviously) is not, collision-resistant"? How do I evaluate the truth value of this statement? So far my best attempt at understanding this comes from the following statements in Menezes, Oorschot and Vanstone's Handbook of Applied Cryptography (Chapter 9):

9.8 Remark (MAC resistance when key known) Definition 9.7 does not dictate whether MACs need be preimage- and collision resistant for parties knowing the key k (as Fact 9.21 implies for parties without k). [p. 325]

9.21 Fact (implications of MAC properties) Let hk be a keyed hash function which is a MAC algorithm per Definition 9.7 (and thus has the property of computation-resistance). Then hk is, against chosen-text attack by an adversary without knowledge of the key k, (i) both 2nd-preimage resistant and collision resistant; and (ii) preimage resistant (with respect to the hash-input). [p. 330]

So, is Aumasson and Bernstein's statement that SipHash is "obviously" not collision-resistant implicitly assuming an adversary that knows the key? Because it seems clear to me that it needs to be collision-resistant to an attacker that doesn't know it—otherwise their proposal to use it as a defense against hash-flooding attacks doesn't work, right?


EDIT: My question has been flagged as a potential duplicate of "Is SipHash cryptographically secure?" I think my question differs from that one in that I'm trying to relate the security claims made in Aumasson and Bernstein's SipHash paper to the quotes that I cited in the Handbook of Applied Cryptography, but I'm uncertain whether I'm understanding these sources correctly.

So for example, here's another passage from Aumasson and Bernstein (p.2, my boldface):

In general, building a MAC from a general purpose cryptographic hash function appears to be a highly suboptimal approach: general-purpose cryptographic hash functions perform many extra computations for the goal of collision resistance on public inputs, while MACs have secret keys and do not need collision resistance.

I do not understand, for example, whether their later statement that "SipHash is not meant to be, and (obviously) is not, collision-resistant" refers to:

  1. The fact that the small output space allows an attacker to find two inputs that hash the same in 232 attempts, which is a very low number (as Demetri's answer remarks and poncho's comment to it reiterates);
  2. Their earlier statement that collision-resistance is not one of the properties required of a MAC;
  3. The Handbook of Applied Cryptography's passages that I consulted that say that:
    • A MAC need not be collision resistant to an attacker that knows the key;
    • A MAC must be computation-resistant ("given zero or more text-MAC pairs (xi, hk(xi)), it is computationally infeasible to compute any text-MAC pair (x, hk(x)) for any new input x ≠ xi (including possibly for hk(x) = hk(xi) for some i)");
    • Computation-resistance implies collision resistance "against chosen-text attack by an adversary without knowledge of the key" (Fact 9.21 that I cited).

From the last of these points it would follow that if SipHash is not collision resistant to such an adversary, then it cannot be computation-resistant either. But Aumasson and Bernstein say that "SipHash-c-d with c ≥ 2 and d ≥ 4 is expected to provide the maximum PRF security possible (and therefore also the maximum MAC security possible) for any function with the same key size and output size," which to me reads like they are conjecturing that it is computation-resistant.

At this point however I'm starting to worry that perhaps my question risks turning into a conversation, something that doesn't fit the question/answer format of this site. So I won't object if somebody chooses to close this question.

$\endgroup$
3
$\begingroup$

It is not collision-resistant because the tag is only 64 bits, so on average only $2^{32}$ inputs are needed to find a collision. This is the classic birthday bound. This is completely insecure, so SipHash is not collision resistant.

This is not a problem for hash tables because hash tables have collision-resolution mechanisms and because the odds of a $n$-way collision fall exponentially with $n$, and because the collisions depend on the (secret) key.

$\endgroup$
  • $\begingroup$ I know that 2^32 is the birthday bound, but so far I understand that the term "collision-resistant" in this context means that an adversary cannot find two messages with the same tag any sooner than implied by the birthday bound. I mean, exploiting the birthday bound is a generic attack, isn't it? $\endgroup$ – Luis Casillas May 5 '16 at 7:05
  • 3
    $\begingroup$ @LuisCasillas: doesn't matter; it means that an attacker can find a collision in a reasonable amount of time ($2^{32}$ oracle requires if he doesn't know the key; $2^{32}$ hash evaluations if he does). If you can find a collision, you're not collision-resistant (just as a cipher with an 8 bit key is insecure, even if there was no attack better than brute force) $\endgroup$ – poncho May 5 '16 at 18:08
  • $\begingroup$ @poncho but how then SIPHASH is secure since it is not collision resistance. Where from security stems? $\endgroup$ – curious Oct 25 '17 at 9:23
  • 1
    $\begingroup$ @curious: SIPHASH is not collision resistant, hence it is not a secure hash; however, it was never claimed to be a secure hash; it was claimed to be a message authentication code, and those have different security assumptions $\endgroup$ – poncho Oct 25 '17 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.