# HMAC collision probability bounds

Could someone point to results or proofs about the probability of HMAC(k, m1) = HMAC (k, m2), assuming the underlying hash function is SHA-256? Would those probabilities be higher/lower if m1 and m2 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

$\Downarrow \;\;$ (that's me pointing)

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

generate m1 and m2 in whatever way
set $\:$tag = $\mathcal{O}$(m1)
output $\:$[m2,tag]

Observe that $\mathcal{A}^{\mathcal{O}}$ has trivial runtime and makes only one query to the oracle. $\:$ Furthermore,

Prob$\hspace{.01 in}$(m1 ≠ m2 $\;$and$\;$ HMAC(k,m1) = HMAC(k,m2)) $\;\;\; = \;\;\; \operatorname{Prob}\left(\mathcal{A}^{\text{HMAC}(k,\cdot)} \: \text{succeeds}\right)$

-
I am not sure whether I don't understand your answer or whether you didn't understand my question. What is Ao, O(m1) ? –  Eugen May 30 '13 at 22:11
–  Ricky Demer May 30 '13 at 22:12
I am interested in actual numbers or pointers to papers with actual probability estimation, not in the notation itself ;) –  Eugen May 30 '13 at 22:20
In other words, you are interested in being handed fish, but not in learning how to catch them? –  Stephen Touset May 30 '13 at 23:01
Pointers to actual papers is not that much to ask. If you don't want to answer the original question why bother writing answers or comments that are not helpful? –  Eugen May 31 '13 at 11:40
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).