11
$\begingroup$

It is known that setting the secret key to a fixed, public value does not make MACs like CBC-MAC or GMAC into secure unkeyed cryptographic hash functions that could be used - for instance - for digital signatures.

In other words, the resulting hash function is not 1st pre-image, 2nd pre-image, and collision resistant.

What are the MACs that do not suffer from that limitation? I believe HMAC is one of them, provided the underlying unkeyed hash is strong.

Are there any others?

EDIT: if the hash used for HMAC is broken, also the HMAC constructed with it will probably be so.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ If the underlying hash of HMAC is secure, then I agree that using HMAC in this way should result in a secure hash. However, does using HMAC and a less secure hash (the HMAC construction may still be secure) in this way, still result in a secure hash? If that is the case, we have a way of construction cryptographically secure hash functions from less secure hash functions... $\endgroup$
    – MartinSuecia
    Commented May 28, 2012 at 10:07
  • $\begingroup$ My point being that I think your statement that "HMAC is one of them" is probably wrong. Since HMAC is simply a hash function iterated twice, any weaknesses in the used hash-function will shine through and be valid also for the resulting hash-function. Please correct me if I'm wrong. $\endgroup$
    – MartinSuecia
    Commented May 28, 2012 at 10:15
  • $\begingroup$ @MartinSuecia You are totally right. I edited the question. However, I believe an HMAC (used really as a MAC) can be more secure than the underlying hash. It really depends on how broken the hash is. To say, MD5 is broken, but HMAC-MD5 is not currently deemed to be so (although it is not a brilliant idea to use it for new designs). RFC6151 explains it better than I can. $\endgroup$
    – SquareRootOfTwentyThree
    Commented May 28, 2012 at 10:28
  • $\begingroup$ Yes, that's what I meant by "(the HMAC construction may still be secure)". Or do you mean that the resulting unkeyed hash, using your construction, may also still be secure? $\endgroup$
    – MartinSuecia
    Commented May 28, 2012 at 10:30
  • $\begingroup$ An attack on the hash does not automatically apply to the HMAC construction (used as an unkeyed hash). To say, the hash could be broken in that you can construct collisions for messages that follow a certain structure. If you cannot efficiently force the hash to produce digests according to said structure, the attack won't apply to the HMAC construction. So, IMO iterating the hash function twice might foil certain attacks the original hash function is subject to. $\endgroup$
    – SquareRootOfTwentyThree
    Commented May 28, 2012 at 12:20

2 Answers 2

Reset to default
3
$\begingroup$

I have ask as part of my answer, "What problem are you trying to solve?"

Do you want a secure unkeyed hash function? If you do, then there are plenty of them around. Even some of the ones that are broken for some uses might be okay for yours (SHA-1 springs to mind -- note the discussion above on HMAC and how broken a hash function has to be). But really, you ought to look at SHA-256, SHA-512, or the new SHA-512/t construction.

If you don't like that, look at any of the SHA-3 finalists. (Full disclosure, I'm the co-author of Skein.)

You're right that HMAC is one of them -- but that's basically the null statement. HMAC is a wrapper around an unkeyed hash function that strengthens it against a number of attacks (and adds a key). If you remove the key (or make it a constant), then all you have is a function with two iterations of a hash function with a bunch of frosting and sprinkles over it. It is obvious that if you start with a secure hash function, make a secure MAC and then remove the key then that you will end up with a secure hash function.

What are you really asking? What do you really want to do?

Jon

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I ask the question for two reasons:i) Curiosity ii) To know the limitation of the MACs and avoid an error that quite often people tend to do. One practical reason could also be that sometime you don't have the luxury of having the whole crypto zoo available. In some constrained systems, you may only pick one or two primitives. A MAC that can be turned into a (non-standard) secure unkeyed hash is beneficial in those cases. $\endgroup$
    – SquareRootOfTwentyThree
    Commented May 30, 2012 at 4:30
  • $\begingroup$ The thing is, even in a limited environment, you are going to have either a MAC from symmetric encryptions, which cant be used for a hash... or you already have a hash function. In general, the "more primitive" type is the hash function, and MACs are hash functions with fluff. $\endgroup$
    – tylo
    Commented Jun 21, 2013 at 9:32
0
$\begingroup$

As pointed out by others, MAC systems based on hash functions can trivially be made back into hash functions by making the key a public constant. E.g. $hash(msg) = HMAC(key_{const}, msg)$.

It's also possible to convert MAC systems based on ciphers into hash functions but the lack of a secret key needs to be compensated for. If the message is not longer than the authentication tag then a simple xor between them works, otherwise some compression function is needed so that they are the same length, e.g. $hash(msg) = CBCMAC(key_{const}, msg)\oplus compress(msg)$. This ensures that an attacker cannot decrypt the output even with the correct key if they don't know the message. Important however that the compression function doesn't lose too much information from the message. Trucation, for example, which discards everything except for the first chunk of the message, would be unsuitable as a compression function, and xor-folding which xor:s together each chunk of the message into one chunk, ensuring that all parts of the message affects the output, would be at least a little bit better. One could of course use a secure hash function as compression function but that defeats the purpose of a construction based on a MAC since you might as well just use that instead then.

Unfortunately, I don't know enough about universal hash functions to say if or how MAC systems based on them could be turned into regular secure hash functions.

Improve this answer
$\endgroup$

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.