23
$\begingroup$

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 269 or is it 257 or even 252, 280, 2128, 2256 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$.

$\endgroup$
4
  • 2
    $\begingroup$ "and that it is thus pointless to have the key wider than half the hash's size" I disagree with that. Larger keys can prevent multi-target attacks against the key. $\endgroup$ Nov 11 '14 at 16:13
  • 1
    $\begingroup$ Broadly speaking, you can — but only with more modern algorithms that don't suffer from length-extension attacks... and I believe it's preferable to prepend the key to the message, as opposed to append. See crypto.stackexchange.com/questions/17735/… and crypto.stackexchange.com/questions/35127/… $\endgroup$
    – hunter
    Jun 15 '17 at 15:45
  • 13
    $\begingroup$ Your question really isn't 'why do we use a MAC algorithm'; instead, it's actually 'is H(m||k) a good MAC algorithm $\endgroup$
    – poncho
    Jun 15 '17 at 15:48
  • $\begingroup$ crypto.stackexchange.com/a/2717/991 ​ ​ $\endgroup$
    – user991
    Jun 15 '17 at 16:02
13
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Yes; that's the "generic attack" that I mention. $\endgroup$
    – fgrieu
    May 26 '12 at 20:06
  • 1
    $\begingroup$ I conclude there is no known attack better than this generic attack, and accept the answer. $\endgroup$
    – fgrieu
    Apr 13 '16 at 7:07
16
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ The length extension attack applies to $\mathcal C(k,m)=\mathcal H(k||m)$, not $\mathcal C(k,m)=\mathcal H(m||k)$. Yes I'm aware that the later is not more secure than half the hash size, this is sated in the question. $\endgroup$
    – fgrieu
    May 29 '12 at 20:18
  • $\begingroup$ I'm not buying that with $\mathcal H$ immune to a length extension attack, $\mathcal H(k||m)$ is as good as HMAC; my understanding is that part of HMAC's revised security argument relies on having $k$ processed at both ends. $\endgroup$
    – fgrieu
    May 29 '12 at 20:49
  • 2
    $\begingroup$ @fgrieu Skein uses a scheme similar to $H(k||m)$ as MAC, and I believe the paper contains some security proofs for this mode. You could compare that with the proof for HMAC, and check if they made any additional assumptions. I think most proofs in the Skein paper assume certain properties of the underlying block cipher. $\endgroup$ May 30 '12 at 10:30
2
$\begingroup$

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

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)$
$\endgroup$
4
  • 1
    $\begingroup$ Nice to have the origin of the construction. The attack is that in the question. The space cost can be reduced to constant, and the attack parallelized, see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999. $\endgroup$
    – fgrieu
    Jan 12 at 11:31
  • $\begingroup$ @fgrieu yes, That is the sole reason. After Paul C. van Oorschot and Michael J. Wiener's publish their seminal paper, it is almost everywhere. I want to go deep in some directions and I think I almost hit the bottom :), And Birthday-Attack is ubiquitous. $\endgroup$
    – kelalaka
    Jan 12 at 11:40
  • $\begingroup$ It's nice to see it stated explicitly that $Pr(\text{collision})$ after $2^{\frac{n}{2}}$ attempts is only 0.5. So many times on this site it's written as if it's a certainty. $\endgroup$
    – Paul Uszak
    Jan 13 at 1:46
  • 1
    $\begingroup$ @PaulUszak I'm trying to write it all the time, it is part of it. In the end, the birthday-attack is a probabilistic attack. $\endgroup$
    – kelalaka
    Jan 13 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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