# Proving HMAC collision probability bounds?

Could someone point to results or proofs about the probability of $$HMAC(k, m_1) = HMAC (k, m_2)$$ assuming the underlying hash function is SHA-256? Would those probabilities be higher/lower if $m_1$ and $m_2$ are not independent?

Please don't point to birthday attack results. I am only interested in the probability that the tags are equal given two messages (random or not) and a single key.

-
Can m2 depend on HMAC(k,m1) in a way that is infeasible to compute? $\;$ –  Ricky Demer May 30 '13 at 20:58
No. Messages m1 and m2 are both known and might even be very similar (e.g. two consecutive timestamps). –  Eugen May 30 '13 at 21:09

Under plausible assumptions, the probability of this happening (for a given pre-specified pair $m_1,m_2$) is $1/2^n$, where $n$ is the number of bits of output of the HMAC. For instance, if it produces 160-bit output, then the probability of this happening is $1/2^{160}$ (again, assuming certain unproven assumptions that are probably reasonable to work with in practice).

-
I understand you assume that HMAC output is totally random. However as far as I know this is not proved. –  Eugen Jun 2 '13 at 9:01
@Eugen, Yes, absolutely. That's why I mentioned that the need for assumptions -- I even mentioned this twice, in case you missed them the first time. The entire point of making assumptions is that they have not been proven. If they'd been proven, we wouldn't need to list them as an assumption. Would you like to clarify what you're getting at? If you are only interested in answers that can be formally proven with no unproven assumptions whatsoever, then I suggest you edit your question to make this a lot clearer, as this significantly changes the question. –  D.W. Jun 2 '13 at 18:03
I didn't miss the assumptions. You just didn't make them explicit (i.e. that output is random). What makes you think it is random? I don't think the question needs editing. I clearly ask about result or (references to) proofs where the asked probability is analyzed somewhat more rigorously. I haven't asked about making additional assumptions. Don't take it personally, but if you criticize my question do it right. However it may be, thank you for participating in this (and other) discussion(s). –  Eugen Jun 2 '13 at 18:47

The following is a method of calculating the probability using the random Oracle model, where the random Oracle is substituted for the HMAC function:

$\mathcal{A}^{\mathcal{O}}$ works as follows:

Generate $m_1$ and $m_2$ in whatever way
set: $tag = \mathcal{O}(m_1)$
output: $[m_2,tag]$
and observe that $\mathcal{A}^{\mathcal{O}}$ has trivial runtime and makes only one query to the oracle. $\:$

$\operatorname{Prob}(m_1 ≠ m_2 \text{ and } \operatorname{HMAC}(k,m_1) = \operatorname{HMAC}(k,m_2))= \operatorname{Prob}(\mathcal{A}^{\text{HMAC}(k,\cdot)} \: \text{succeeds})$