# Simple message authentication code

I used to figure that message authentication codes function like digital signatures: a hash of a message is calculated and then encrypted with a secret key. To verify the authenticity of a message, the recipient calculates the hash of the message, decrypts the MAC with the secret key, and compares the two. I have not seen a single MAC that works like this. Is this insecure?

• That construction requires collision-resistance of the hash function. $\;$ – user991 Jan 23 '15 at 2:16
• @Ricky Demer Yeah, and so does every other friggin' message authentication code, digital signature scheme, and CSPRNG out there. What's your point? That it needs to be a secure hash function is not lost on me. – Melab Jan 23 '15 at 6:02
• My point is that I believe the result "so does every other friggin' message authentication code, digital signature scheme, and CSPRNG out there" would potentially be publishable, since those can be based on one-way functions, and from what I can find (section 4.3), there is currently no publicly known way to base collision-resistance on one-way functions. $\:$ (... continued) $\;\;\;\;$ – user991 Jan 23 '15 at 7:43
• @RickyDemer is correct. HMAC does not rely on collision resistance of the underlying hash; HMAC-MD5 is still completely sound (although poor taste), outside of its digest length. – Stephen Touset Jan 23 '15 at 18:50
• Your understanding of digital signatures is also wrong -- RSA signatures resemble that process, but many other signature schemes have nothing whatsoever to do with encryption schemes. – cpast Feb 22 '15 at 4:08

Actually, there are Carter-Wegman MACs that work like this; of course, there the "hash" function is not a cryptographical hash function, but instead it is an almost-universal hash (with a key).

If we replace this almost-universal hash, well, we run into some potential problems.

The first one is the malleability of some encryption methods. If we were to use, say, counter mode, then it would be easy to modify the message arbitrarily. All one would need to do is compute the hashes of both the original message, and the modified one, and xor in both to the encrypted MAC; this modified MAC would decrypt to the hash of the modified message. Carter-Wegman MACs don't run into this problem, because we assume that an attacker cannot compute the almost-universal hash function (because they don't have the key).

One way to attempt to get around this problem is simply use ECB mode, and encrypt only one block -- that is certainly not malleable. This runs into the second potential problem -- hash collisions. If we use only 128 bits of the hash, someone can find two plaintexts that share those 128 bits, obtain the MAC for one, and then he has found a valid MAC for the other message. While clearly this isn't as severe as the first problem (where the attacker can generate a valid MAC for any message), it's still enough for us to be wary of this. Again, Carter-Wegman MACs don't run into this problem.

So, it can potentially work; however we need to choose our encryption method carefully.

• What is the difference between a "universal" hash and a "cryptographical" hash? – Melab Jan 23 '15 at 6:03
• @Melab : $\:$ en.wikipedia.org/wiki/Universal_hashing $\;\;\;\;$ – user991 Jan 23 '15 at 7:42
• @RickyDemer Not seeing where the "universal" comes in. – Melab Jan 23 '15 at 21:39
• Doesn't GMAC fall in this category? – Maarten Bodewes Feb 22 '15 at 4:12
• @MaartenBodewes: yes, it is a Carter-Wegman MAC that works like this. – poncho Feb 22 '15 at 4:31