51

I mean, is it just a matter of "how difficult is it to reverse the function with the current technology"?

Or is there a mathematical concept or property that makes them different?

If it is a matter of "how difficult is it to reverse the function", then is it correct to say that with the progress of the technology, some Cryptographic Hash Functions stop being Cryptographic to be just Hash Functions? Is this what happened to MD5?

57

Every cryptographic hash function is a hash function. But not every hash function is a cryptographic hash.

A cryptographic hash function aims to guarantee a number of security properties. Most importantly that it's hard to find collisions or pre-images and that the output appears random. (There are a few more properties, and "hard" has well defined bounds in this context, but that's not important here.)

Non cryptographic hash functions just try to avoid collisions for non malicious input. Some aim to detect accidental changes in data (CRCs), others try to put objects into different buckets in a hash table with as few collisions as possible.

In exchange for weaker guarantees they are typically (much) faster.

I'd still call MD5 a cryptographic hash function, since it aimed to provide security. But it's broken, and thus no longer usable as a cryptographic hash. On the other hand when you have a non cryptographic hash function, you can't really call it "broken", since it never tried to be secure in the first place.

  • 2
    Thanks for your answer! why is MD5 broken? Is it because the technology improved? or is it because somebody detected a mathematic flaw? If it is due to the improvement of technology, can we say that the "cryptographic property" of any cryptographic hash function is relative to the current state of technology? and that soon or later, all the currently considered "cryptographic hash functions" will eventually be "broken", and thus stop being cryptographic? – Mr.Eddart Feb 17 '12 at 10:17
  • 4
    There are mathematical flaws in MD5 which allow an attacker to construct several messages which have the same MD5 hash cheaply. SHA-1/2 also have some minor mathematical flaws. If such a mathematical flaw will be discovered in a certain hash function is hard to predict, since it requires the discovery of new crypto analysis methods. – CodesInChaos Feb 17 '12 at 10:29
  • 1
    On the other hand, the mere increase of computational power of conventional computers will not threaten larger hash functions in the foreseeable future. – CodesInChaos Feb 17 '12 at 10:31
  • 2
    @edutesoy That's just playing with words, and I'm no philosopher. Personally I call every hash function that aims to be secure a "cryptographic hash function", even if it has been broken by now. – CodesInChaos Feb 17 '12 at 10:45
  • 1
    @edutesoy If you're looking for a label for it, I guess you could say MD5 is an 'insecure' cryptographic hash function, aka broken. – greatwolf Feb 5 '17 at 3:22
21

There are some properties that cryptographically secure hash functions strongly require, that are not so strongly required for non-cryptographically secure hash functions:

  • preimage resistance (given a hash h it must be difficult to find a message m that yields h when hashed
  • weak collision resistance (given a message m1 it must be difficult to find a different message m2 so that m1 and m2 yield the same hash)
  • strong collision resistance (it should be difficult to find any messages m1 and m2 that yield the same hash)

In those points, you see a lot of difficult, which is a qualitative measure instead of a quantitative one. The best answer here is feasibility: there is a fuzzy line when something becomes feasible and those lines move over time (as computation capabilities grow exponentially according to Moore's Law, once difficult problems can now be solved by your cell phone).

In general it's good practice to assume that difficult means that the time to achieve some goal is NP-complete. This means the time required to break the hash grows strongly as you increase the hash length.

Another point is, that a cryptographically secure hashing algorithm can be useful in some applications, but not in others. It depends on the model of your attacker, the nature of the information you want to protect and things like performance requirements (as a general rule, the better the cryptographic properties of a hash, the worse it's runtime behaviour).

  • 5
    NP-complete does not mean exponential growth. Not until one proves that P < NP. – ypercubeᵀᴹ Feb 17 '12 at 8:55
  • For hash functions difficult mean - can not be done better than using brute force. – ralu Feb 17 '12 at 9:08
  • 5
    The appropriate prefix is "cryptographically secure" and not just "cryptographic". For instance, MD5 is no longer considered cryptographically secure, but it is arguably still a cryptographic hash function, given the original purpose of its design. – Henrick Hellström Feb 17 '12 at 12:03
  • 2
    The weak collision resistance is also known as second preimage resistance. – Paŭlo Ebermann Feb 17 '12 at 18:25
  • 1
    The meaning of difficult is quite well defined in this context: 2^n for preimage and second preimage resistance, and 2^(n/2) for collision resistance. While we can't prove that the problem is that hard, a hash function is considered broken, once algorithm are known which are faster than these bounds. – CodesInChaos May 12 '12 at 8:57
3

I'd say that the two key things to understand here are:

  1. The term "hash function" is vague—or more precisely, polysemous: it has a "family" of meanings that are closely related but distinct. If somebody labels a function as a "hash function," the label simply doesn't tell you what properties that function must have. You have to examine the context where the term is used and the requirements of that context.
  2. The term "cryptographic hash function" is a slight misnomer—it looks like a description, but it has an involved technical definition that the term itself doesn't actually describe. To put it simply, there are functions like message authentication codes (MAC) that are often labeled as hash functions and offer some form of cryptographic security, but are not "cryptographic hash functions" in the conventional definition.

The term "cryptographic hash function" is conventionally used to refer to what might be better labeled as collision-resistant hash functions, which are public functions ("public" = don't require a secret key) that are required to have these three properties:

  • Second preimage resistance: For a random value m1 chosen by an honest party, it's very costly for an attacker to find any value m2 ≠ m1 such that hash(m1) = hash(m2).
  • Preimage resistance: For a random value h chosen by an honest party, it's very costly for an attacker to find any value m such that hash(m) = h.
  • Collision resistance: It's very costly for an attacker to find any pair of values m1 ≠ m2 such that hash(m1) = hash(m2).

There's a fourth property that older cryptographic hash functions fail trivially but which newer ones like SHA-3 and Blake2 are designed to achieve:

  • Random oracle indifferentiability: This one is all but impossible to explain briefly, but let's dumb it down to this: it's very costly for an attacker to find any non-chance correlations between the outputs of inputs of their choice.

The random oracle property (when correctly formulated) implies the three previous properties, as well as additional ones like the absence of efficient length extension attacks. (Length extensions are the most obvious reason why older hash functions like SHA-256 and SHA-512 fail the random oracle property.)

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.