Attacks of the MAC construction $\mathcal{H}(m\mathbin\|k)$ for common hashes $\mathcal{H}$?

Question

Consider a common practically-collision-resistant hash function $\mathcal{H}$ (e.g. SHA-1, SHA-256, SHA-512, RIPEMD-160), perhaps based on the Merkle–Damgård construction as are the first three. We define a Message Authentication Code $\mathcal{C}$ $$(k,m) \mapsto \mathcal{C}(k,m)=\mathcal{H}(m\mathbin\|k)$$ where $\mathbin\|$ denotes concatenation, $k$ is a secret key (constant, or at least of fixed size), and $m$ is a message (possibly of variable length). Assume that an adversary can (iteratively) submit queries with $m_j$ and obtain $C(k,m_j)$, and wants to obtain $k$ or otherwise compute $C(k,m)$ for some $m\ne m_j$.

That MAC $\mathcal{C}$ is not trivially bad. In particular, if $\mathcal{H}$ was indistinguishable from a random function in the Random Oracle Model, $\mathcal{C}$ would be secure. And even though $\mathcal{H}$ may have the length-extension property, it does not turn into a devastating attack on $\mathcal{C}$.

The less impractical generic attack that I see is that if a collision was known for $\mathcal{H}$ with the colliding messages of moderate identical length, it could be deduced countless collisions for $\mathcal{C}$. Hence security is demonstrably not better than collision-resistance of $\mathcal{H}$ (for identical-length messages). We could assume that $k$ is half the size of the result of $\mathcal{H}$, and hope that the security is about 2⁶⁹ or is it 2⁵⁷ or even 2⁵², 2⁸⁰, 2¹²⁸, 2²⁵⁶ hash rounds for SHA-1, RIPEMD-160, SHA-256, SHA-512.

What are the known attacks against $\mathcal{C}$ (better than the above), and their cost, for each of these common hashes?

Is there hope for an argument that an attack against $\mathcal{C}$ would turn into an attack of similar cost against $\mathcal{H}$, or hint of the contrary?

Update: this answer to a similar question is of interest, but I fail to find that it really answers the present question.

Update 2: I am aware that the construction considered is weaker than HMAC, and in particular is vulnerable to collision on $\mathcal H$; I stated that, and that it is thus pointless to have the key wider hopeless to target security against some attacks better than half the hash's size. I'm asking exactly what cryptanalytic attack better than finding a collision on $\mathcal H$ there are. There is room for such an attack only by exploiting a weakness in the structure or/and the round function of a concrete $\mathcal H$.

Answer 1

One issue with this construction is described in section 6 of the original HMAC paper, "Keying hash functions for message authentication" by Bellare, Canetti and Krawczyk, where they note that finding a collision on $\mathcal H$, i.e. two inputs $x \ne x'$ such that $\mathcal H(x) = \mathcal H(x')$, directly yields a collision on $\mathcal C$ such that $\mathcal C(k,x) = \mathcal C(k,x')$ regardless of $k$. (Technically, this only works if the collision is internal, in the sense that $\mathcal H(x \| s) = \mathcal H(x' \| s)$ for any suffix $s$, but that's true for pretty much all known M-D hash collision attacks anyway.)

Of course, this issue is mostly irrelevant if $\mathcal H$ is assumed to be collision resistant. (Although it should be noted that, even for a perfect $n$-bit hash, a birthday attack can find a collision with only about $2^{n/2}$ evaluations, and that this collision can then be used to break $\mathcal C$ for any $k$.) However, given how hard achieving complete collision resistance seems to be compared to most other security properties asked of hash functions, immunity to collision attacks (which the HMAC construction provides, as long as the other security properties it depends on aren't compromised) is nothing to sneer at.

Answer 2

Using $H(m\mathbin\Vert k)$ with hash function $H$, message $m$ and key $k$, is one possible way to build a MAC algorithm. It is not necessarily a good one; it depends on the used hash function. Even when it is a good one, that does not preclude the possibility of other, "better" algorithms (e.g. for performance).

As an illustration of potential security issues, let's define hash function $H$ as being SHA-256 applied on the bit-reversed input; that is, we take the input to the hash function as a sequence of bits, reverse the order of bits (first bit becomes last, second bit becomes next-to-last, and so on). It's a bit of a contrived example, but it should show my point. That function $H$ is (obviously) as resistant to collisions, preimages and second-preimages as SHA-256, so, from that point of view, it is a secure cryptographic hash function. However, using $H(m\mathbin\|k)$ with that hash function would be weak, because $H(m\mathbin\|k) = \textrm{SHA-256}(\textrm{rev}(k)\mathbin\|\textrm{rev}(m))$, for which so-called length extension attacks apply.

So whether $H(m\mathbin\|k)$ is a secure MAC depends on subtle properties of the hash function $H$ which are not covered by the classic assertions of resistance to collisions and preimages. HMAC was defined with two nested function hash function calls precisely so that its security could be proven in the case of hash functions of the Merkle-Damgård type (like SHA-256); a simpler construction like $H(m\mathbin\|k)$ was not amenable to such proofs. So this is the reason why HMAC exists: because we can convince ourselves that it is secure, more readily than with your proposal.

As for performance, you have to consider that hash functions are not necessarily the best in town for processing bulk data. On a modern PC, dedicated MAC algorithms like Poly1305 or GHASH (the MAC part of GCM) are easily 5 times faster (or more) than SHA-256 or SHA-512.

Answer 3

The MAC you created is what's commonly called a keyed hash function. The way you have done it has a couple of issues.

One is that you're hashing the message and then the key, but it's better to do the key and then the message.

The reason for that is that if someone finds a collision with your message, then they are going to end up with the same MAC. It is better to have the known-different data at the front of the construction, where it makes the most difference.

The other is the length extension attack. It's just a generalization of the above -- you want to reduce the chance that two messages of different lengths will end up making a collision.

If you assume a hash function that is immune to a length extension attack, then a keyed hash (with the key at the front) is as good as an HMAC.

Skein has this property, and also combines with it the fact that it's built on a tweak able cipher with the tweak carrying deltas. That's Skein's one-pass MAC, and there's a description of it and the security proofs in the Skein papers (see www.skein-hash.info).

Answer 4

According to academic recordings Gene Tsudik's article in 1992;

• Message Authentication with One-Way Hash Functions

is the first academic paper that this construction $(k,m) \mapsto \mathcal{C}(k,m)=\mathcal{H}(m\mathbin\|k)$ is defined and a name is given as secret suffix technique. The reference of invertors are not given in the article.

Tsudik also looked at the analysis and provides the first birthday-attack on this construction as follows;

Assume that the attacker generates $R$ random messages and intercepts $S$ messages. Using the probability on the birthday-paradox one can say that at least one message from the intercepted messages collides with the random messages is given by $$P \approx R \cdot \frac{S}{N}$$ where $N$ is the output size of the hash function. Due to the birthday-attack, we need around $R = 2^{N/2}$ messages so that $P=50$, i.e. we have 50% of probability of a hit.

The advantage of this attack is that can be executed in an off-line manner the attacker can generate $R = 2^{N/2}$ messages and store them in a fast query structure. Once a message $m$ is intercepted the attacker looks for a candidate collision $m'$ such that $H(m) = H(m')$

The cost of this attack is $\mathcal{O}(2^{N/2})$ operations with $\mathcal{O}(2^{N/2})$ space.

This attack a hidden requirement that the key is always aligned with the start of a block. Otherwise, a collision $m'$ may not have the same length. Generating more random messages can eliminate this requirement.

---

Note 1: I've written this as a historical note of secret-prefix and the first attack. This is later revisited 4 years later by HMAC paper of Bellare et. al, as mentioned in the first answer.

Note 2: Tsudik talked about 3 constructions;

• the secret-prefix $(k,m) \mapsto \mathcal{C}(k,m)=\mathcal{H}(m\mathbin\|k)$
• the secret-suffix $(k,m) \mapsto \mathcal{C}(k,m)=\mathcal{H}(k\mathbin\|m)$ and
• the envelope construction $(k,m) \mapsto \mathcal{C}(k,m)=\mathcal{H}(k\mathbin\|m\mathbin\|k)$