SipHash's (non-)collision resistance

Question

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 h_k be a keyed hash function which is a MAC algorithm per Definition 9.7 (and thus has the property of computation-resistance). Then h_k 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 2³² 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 (x_i, h_k(x_i)), it is computationally infeasible to compute any text-MAC pair (x, h_k(x)) for any new input x ≠ x_i (including possibly for h_k(x) = h_k(x_i) 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.

Answer 1

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.