0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Can m2 depend on HMAC(k,m1) in a way that is infeasible to compute? $\;$ $\endgroup$
    – user991
    May 30, 2013 at 20:58
  • $\begingroup$ No. Messages m1 and m2 are both known and might even be very similar (e.g. two consecutive timestamps). $\endgroup$
    – Eugen
    May 30, 2013 at 21:09

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ I understand you assume that HMAC output is totally random. However as far as I know this is not proved. $\endgroup$
    – Eugen
    Jun 2, 2013 at 9:01
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Jun 2, 2013 at 18:03
  • $\begingroup$ 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). $\endgroup$
    – Eugen
    Jun 2, 2013 at 18:47
2
$\begingroup$

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. $\:$

This leads to:

$\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})$

Improve this answer
$\endgroup$
5
  • $\begingroup$ I am not sure whether I don't understand your answer or whether you didn't understand my question. What is Ao, O(m1) ? $\endgroup$
    – Eugen
    May 30, 2013 at 22:11
  • $\begingroup$ en.wikipedia.org/wiki/Oracle_machine $\;$ $\endgroup$
    – user991
    May 30, 2013 at 22:12
  • $\begingroup$ I am interested in actual numbers or pointers to papers with actual probability estimation, not in the notation itself ;) $\endgroup$
    – Eugen
    May 30, 2013 at 22:20
  • 3
    $\begingroup$ In other words, you are interested in being handed fish, but not in learning how to catch them? $\endgroup$
    – Stephen Touset
    May 30, 2013 at 23:01
  • $\begingroup$ 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? $\endgroup$
    – Eugen
    May 31, 2013 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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