$H(m\mathbin\Vert k)$ as an authentication algorithm, where $H: \{0, 1\}^* \rightarrow \{0, 1\}^{n}$, has at most a strength equivalent to $\frac{n}{2}$ bits. $H((k^\prime \oplus \mathrm{opad})\mathbin\Vert H((k^\prime \oplus \mathrm{ipad})\mathbin\Vert m))$, the definition of HMAC, has an upper strength of $n$. The security of block cipher modes and block ciphers providing authentication is less clear to me. What parts of a MAC algorithm construction determine if it has a strength of $n$ bits as opposed to half that number?


2 Answers 2


It turns out that the birthday paradox figures into both the suffix-MAC $H(m \mathbin\Vert k)$ and the HMAC $H((k \oplus \mathrm{opad}) \mathbin\Vert H((k \oplus \mathrm{ipad}) \mathbin\Vert m))$, but in different ways. And, curiously, there is no theoretical formalism in the field of ‘provable security’ for the way that it figures into suffix-MAC, which is the one that, as you observed, is practically relevant.

The quick summary is that, for a $b$-bit hash function $H$, when $k$ is unknown to an attacker, for suffix-MAC $H(m \mathbin\Vert k)$, the attacker can spend $2^{b/2}$ work offline to find messages $m_a \ne m_b$ that collide under $H$, whereas for HMAC, the attacker must interact online with your system for $2^{b/2}$ messages before they're expected to stumble upon messages $m_a \ne m_b$ that collide under $\operatorname{HMAC-}\!H_k$.

Because $2^{b/2}$ offline work is sometimes feasible, e.g. if $b = 128$ as in MD5 (which also has nongeneric collision attacks that reduce the work to something negligible), whereas $2^{b/2}$ online interactions with a single application is nearly unthinkable, when summarizing MAC security we usually paper it over and say that suffix-MAC has $b/2$ bits of security while HMAC has $b$ bits of security—but you'll find the gory details in papers analyzing the ‘provable security’ of any MAC.

In a little more detail:

  1. The suffix-MAC construction $H(m \mathbin\Vert k)$ for an iterated hash function $H$, i.e. roughly where $H(m_0 \mathbin\Vert m_1 \mathbin\Vert \cdots \mathbin\Vert m_{n-1}) = f(\cdots(f(\mathit{IV}, m_0), m_1)\cdots, m_{n-1})$, is vulnerable to collisions in $f$: if you can find initial message blocks $m_a \ne m_b$ such that $f(\mathit{IV}, m_a) = f(\mathit{IV}, m_b) = h$, then the messages $m_a$ and $m_b$ always have the same authenticator $$H(m_a \mathbin\Vert k) = f(f(\mathit{IV}, m_a), k) = f(h, k) = f(f(\mathit{IV}, m_b), k) = H(m_b \mathbin\Vert k),$$ as do any pairs of messages that start with $m_a$ or $m_b$ and share a common prefix, $m_a \mathbin\Vert m'$ and $m_b \mathbin\Vert m'$.

    An adversary who knows $f$ and $\mathit{IV}$—which are a public function and constant, respectively, in cases like SHA-256—can work offline to try to find such a collision. Once they've found one, and they will know when they've found one because they can just test it, they may be able to break your application immediately with probability 1 and no prior interaction.

    This is practically relevant: cryptosystems based on MD5 and SHA-1 were broken in practice by finding such collisions, and MD5 was even exploited to forge HTTPS certificates in a widely publicized incident of international industrial sabotage by the United States and Israel against Iran (although with RSASSA-PSS signatures, rather than with symmetric authenticators).

    What's curious is that there's no theoretical formalism in the field of provable security about this. Every fixed compression function like SHA-256 has collisions. We just don't know any yet. We can't say anything formal about an attacker's success probability after a certain amount of work for attacks on these constructions, because there is nothing randomized about them. Either the attacker knows a collision (and one certainly exists) or they don't, and while we can informally conjecture about their expertise in cryptanalysis, no formalism in cryptography helps with quantifying probabilities about that knowledge.

  2. $\operatorname{HMAC-}\!H_k$ is vulnerable to an internal collision in $H((k \oplus \mathrm{ipad}) \mathbin\Vert m)$: for every $k$, there are guaranteed to be many pairs of messages $m_a \ne m_b$ such that $$H((k \oplus \mathrm{ipad}) \mathbin\Vert m_a) = H((k \oplus \mathrm{ipad}) \mathbin\Vert m_b).$$ In that case, the two messages share a common authentication tag under the key $k$, and so if the sender provides an authentication tag for $m_a$, the attacker can replace the message by $m_b$ and leave the tag intact, and the receiver will be none the wiser. (A collision may also happen in the outer $H$, of course.)

    But the attacker can't try offline to test whether $m_a$ and $m_b$ collide under $\operatorname{HMAC-}\!H_k$, because they don't know $k$, in the formalism of provable security. So, the attacker's best strategy (in the cases where we do have security reductions) is just to try substituting messages without changing their authentication tags, and the expected number of attempts at forgery before a collision will be about $2^{b/2}$.

    The same applies to other constructions, like CMAC, and this is why, if you look closely at the security reductions for many of these constructions, you will find references to the birthday bound, and forgery probabilities in terms of numbers of queries $q$ as long as $q \lll 2^{b/2}$. A notable exception to this is polynomial evaluation one-time MACs, which work differently, but that will have to be a bedtime story for another night.

  • $\begingroup$ What if the key that is used for authentication in the schemes you speak of in the last paragraph is derived from a master key and a nonce? Would the maximum number of queries still be $2^{b/2}$? $\endgroup$
    – Melab
    Feb 12, 2018 at 20:15

The part where you can find some way to make a collision useful in your attack.

With the first MAC, $H(m\parallel k)$ there's a simple forgery attack: Generate $(m,m')$ until $H(m)=H(m')$ with $m\neq m'$ (but same length), then submit $m$ to the signing oracle and use $m'$ as the message on which you created a forgery. Because the internal state is the same after $m$ or $m'$ is processed, the same MAC will be generated. In total this gets you away with $n/2$ offline hash evaluations. Note that this assumes that $m,m'$ have the same length which is a multiple of the block length of the Merkle-Damgård hash H.

With HMAC however, first you can't make offline evaluations of the hash because you don't know the prefix and secondly to discover the collision you'd have to query both colliding strings to the oracle at which point you can't use them anymore for submission as forgery.

For a primer on the security games, see this Q&A.

  • $\begingroup$ I know that it depends upon a part that the birthday paradox applies to, but what makes it so that it applies? CBC-MAC works just like a hash function, but why is its security not half of its output size? $\endgroup$
    – Melab
    Oct 6, 2017 at 21:14
  • $\begingroup$ @Melab I think it comes down to "can you compute a deterministic 'pre-value' to the MAC that doesn't involve the key". For CBC-MAC and HMAC and H(k||m) this is impossible. $\endgroup$
    – SEJPM
    Oct 6, 2017 at 21:16

Your Answer

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

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