I saw the difference between the proof and the statement of "proposition 2" in the paper "MDx-MAC and building fast MACs from hash functions" by Bart Preneel & Paul C. van Oorschot. Is there anyone understanding the term $2^m / (2^m - 1)$ in its proof?

This is their proposition:

Let $h$ be an iterated MAC with $n$-bit chaining variable and $m$-bit result. An internal collision for $h$ can be found using u known text-MAC pairs and v chosen texts. The expected values for u and v are as follows: $u = \sqrt{2} \cdot 2^{n / 2}$ and $v = 0$ if the output transformation $g$ is a permutation; otherwise, $v$ is approximately $2 \cdot 2^{n-m} + 2 \lceil{n/m}\rceil$.

And this is their proof:

If the number of known texts is $r = \sqrt{2} \cdot 2^{n/2}$, a single internal collision is expected by the birthday paradox (note $\begin{pmatrix} {r \\ 2}\end{pmatrix} / 2^n \approx 1$). If $g$ is a permutation (e.g. the identity mapping), all collisions are internal and the results follows by Lemma 1. If $g$ behaves as a random function, $\begin{pmatrix} {r \\ 2}\end{pmatrix} / 2^m \approx r ^2/2^{m+1} = 2^{n−m}$ external collisions are expected and additional work is required – for a verifiable forgery – to distinguish the internal collision from the external collisions. (Note Lemma 1 requires internal collisions.) This may be done by appending a string y to both elements of each collision pair and checking whether the corresponding MACs are equal. This requires $2(1 + 2^{n−m})$ chosen text-MAC requests. For an internal collision both results will always be equal, while for an external collision this will be so with probability $1/{2^m}$. Discard collision pairs corresponding to unequal MACs. The expected number of remaining collision pairs after this stage is $2^{n−2m}$ external plus one internal (but these cannot yet be distinguished). If the (total) number of remaining collision pairs is 2 or more (e.g. $n − 2m > 0$), further external collisions must be discarded by appending a different $y$, and continuing in this manner until only a single collision remains; with high probability this is an internal collision. This may require a small number of additional chosen texts and a total number $2 \cdot 2^{n−m} \cdot 2^m/(2^m − 1) + 2 \lceil{n/m}\rceil$

I really do not understand their conclusion because of the term $2^m/(2^m - 1)$.



Your Answer

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