5
$\begingroup$

I have an application that needs a fast 128-bit MAC to guarantee message authenticity in a protocol. I would like to reuse this MAC value as a binding identifier, so that even those who know the key cannot later generate another message with the same MAC value for that key.

"Second preimage resistance", or whatever you call it here, is not normally a required property of MACs and the only one with it that comes to mind is HMAC. However, I would like something faster (with many relatively short messages per key). AES hardware can be assumed, so if there is a block cipher based MAC that does not allow generating a colliding message, that could fit the bill.

Do such MACs exist?

Collision resistance is not required.

|improve this question
$\endgroup$
  • $\begingroup$ Are you sure you don't need (at least some form of) collision resistance? If the person generating the messages thinks they might want to find a second preimage later, they could plan ahead and only send messages for which they already have a second colliding message prepared. $\endgroup$ – Ilmari Karonen Sep 10 '15 at 13:30
  • $\begingroup$ @IlmariKaronen, collision resistance is not required, because the purpose is to prevent the recipients from later claiming the ID refers to another message. (Yes, even then there are holes to plug to prevent collision attacks, so some collision resistance would be nice.) $\endgroup$ – otus Sep 10 '15 at 15:27
4
$\begingroup$

I really like this question, and have two things to say.

First note that CBC-MAC is no good since given the key it's easy to find a collision. Let $t$ be a tag for a message $m=m_1,m_2$ of length $\ell$ bits. Then, in CBC-MAC the input to AES first is $\ell$ and then the output is XORed with $m_1$ and input to AES, and so on. Let $t_1$ be the intermediate value output from AES with $m_1$. Then, you can make any change to $m_1$ and compute $t_1'$. Now take $m_2'$ so that $m_2'\oplus t_1' = m_2 \oplus t_1$. This will give you the same output tag $t$. (I hope that this is clear.)

Now, let's try and answer better. Specifically, let's assume that there exists a construction that gives what you want, and so you have collision resistance even given the key. This actually gives you a construction of a hash function from a block cipher. We have some such constructions in the ideal cipher model, like Davies-Meyer. However, these are problematic to apply to AES since AES has weaknesses under related key attacks (which are exactly the types of attacks that appear when constructing a hash function from a block cipher).

Based on @otus's comment, I will extend my answer to deal with theory as well. What you are really asking is to build a second-preimage resistant hash function from a block cipher. Practically, we don't know how to do this differently to full collision resistance (to the best of my knowledge; please correct me if I'm wrong). However, theoretically, it is possible to construct universal one-way hash functions (which are second preimage-resistant hash functions) from one-way functions. This is a famed result by Rompel, with a full proof here. Thus, theoretically speaking, it is possible to construct such a hash function from block ciphers (since block ciphers are pseudorandom permutations and one-way functions can easily be constructed from them).

In contrast, Simon proved that collision-resistant hash functions cannot be constructed from one-way functions in a black-box way.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Actually, otus specifically didn't ask for collision resistance; only second preimage resistance $\endgroup$ – poncho Sep 10 '15 at 13:50
  • 1
    $\begingroup$ You are right, but I don't know of any PRACTICAL distinction regarding constructions from block ciphers. Of course, theory-wise there's a massive difference and universal one-way hash functions (which are essentially second-preimage resistant) can be constructed from one-way functions, whereas full-blown collision-resistant hash functions cannot (using black-box constructions). $\endgroup$ – Yehuda Lindell Sep 10 '15 at 14:39
  • $\begingroup$ Davies–Meyer would, ignoring the need for an ideal cipher, give a hash, but would it also double as a MAC? Or would you need e.g. HMAC-Davies–Meyer-<cipher> to get both both forgery resistance and second preimage resistance? $\endgroup$ – otus Sep 10 '15 at 15:41
  • $\begingroup$ Well, you can Davies-Meyer and get a single block (128-bit output) which you can then compute AES on with a secret key. This will then give you a MAC by the "hash-then-MAC" paradigm. However, be warned! First, with a 128-bit output from AES it is possible to find a birthday collision in $2^{64}$ time. In addition, as I have mentioned, AES is not ideal for use inside Davies-Meyer and this isn't recommended. $\endgroup$ – Yehuda Lindell Sep 10 '15 at 17:40
  • $\begingroup$ @YehudaLindell, with a 256-bit block size and final truncation it seems like it might have 128-bit security? Of course, it still wouldn't be practical, but at least a theoretical solution. $\endgroup$ – otus Sep 11 '15 at 6:03

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.