Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 31 down vote accepted

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 hashfunction, since it aimed to provide security. But it's broken, and thus no longer usable as 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.

share|improve this answer
1  
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? –  edutesoy Feb 17 '12 at 10:17
3  
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
    
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
    
thanks CodeInChaos, so just to be sure, now that it is "cheap" to produce collisions on MD5, is it a "Cryptographic Hash Function" anymore? or it became simply a regular "Hash Function" due to the discovery of this mathematical flaw? Also, conceptually, MD5 has never been a Cryptographic hash, because it has always had this flaw, although it was not still discovered, is this correct? thanks a lot again! –  edutesoy Feb 17 '12 at 10:38
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

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

share|improve this answer
2  
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
4  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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