# 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).

-
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