Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

After reading this interesting question, I felt like I had a good idea of which insecure hashing algorithm I'd use if I needed one, but no idea why I might use a secure algorithm instead.

So what is the distinction? Isn't the output just a random number representing the hashed thing? What makes some hashing algorithms secure?

share|improve this question
6  
This question is better suited for the IT Security SE site. –  Bernard Apr 26 '12 at 18:22
    
@Bernard If that's the case then I'm fine with that, but my question wasn't really about how or when to use a secure hash, but what distinguishes a secure hashing algorithm from an insecure one. That seems more like a programming question to me, but I don't browse IT Security SE so maybe that works there too. –  CodexArcanum Apr 26 '12 at 19:29
2  
A very similar question has already been asked on IT Security –  ChrisF Apr 26 '12 at 22:11
add comment

7 Answers

up vote 23 down vote accepted

There are three properties one wants from every cryptographic hash function H:

  • preimage resistance: Given h, it should be hard to find any value x with h = H(x).

  • second preimage resistance: Given x1, it should be hard to find x2 != x1 with H(x1) = H(x2).

  • collision resistance: It should be hard to find two values x1 != x2 with H(x1) = H(x2).

With hash functions as used in common programming languages for hash tables (of strings), usually none of these is given, they only provide for:

  • weak collision resistance: For randomly (or "typically") selected values of the domain, the chance of collision is small. This says nothing about an attacker intentionally trying to create collisions, or trying to find preimages.

The three properties above are (among) the design goals for every cryptographic hash function. For some functions (like MD4, SHA-0, MD5) it is known that this failed (at least partially). The current generation (SHA-2) is assumed to be secure, and there is now a competition for the "Secure Hash Algorithm 3".

For some uses (like password hashing and key derivation from passwords), the domain of actually used values x is so small that brute-forcing this space becomes feasible with normal (fast) secure hash functions, and this is when we also want:

  • slow execution: Given x, it takes some minimum (preferably configurable) amount of resources to calculate the value H(x).

But for most other uses, this is not wanted, one wants instead:

  • fast execution: Given x, calculating the value of H(x) is as fast as possible (while still secure).

There are some constructions (like PBKDF2 and scrypt) to create a slow hash function from a fast one by iterating it often.

For some more details, have a look at the hash tag on our sister site Cryptography Stack Exchange.

share|improve this answer
add comment

Secure means that someone wanting to induce you into error by using a collision (i.e. the fact that two sources are hashed to the same value) will have difficulties.

Some characteristics:

  • knowing the hash, building a file who hash to that value is difficult (variant, part of the new file is given as well as the desired hash)

  • building two different files which hash to the same value is difficult (variant, part of the files is given)

share|improve this answer
add comment

The primary difference is pretty simple: a normal hash is meant to minimize the number of accidental collisions, to the extent that it can without slowing down a whole lot in the process.

A secure hash it intended to prevent collisions, even when somebody's doing their best to cause one. You generally don't want to trade any possibility of a collision for faster operation. In fact, making operation intentionally slow has some security benefits in itself, even if doesn't make finding collisions any harder.

For an example of the latter: if computing a hash takes 50 ms, it won't have an material affect on a normal user's login (i.e., most users won't notice a difference of 50ms when they login). At the same time, if an attacker wants to do a dictionary attack, being able to produce only 20 hashes a second is a serious handicap. In other words, within some kind of reason, for a secure hash, slower is better.

share|improve this answer
3  
In the domain of cryptographic hash functions, there are two important subgroups: the fast ones (used for message authentication, signature and the like), and the slow ones - used for key derivation and password hashing. Don't mix these, there are applications for both. –  Paŭlo Ebermann Apr 26 '12 at 19:57
    
Actually, there are also hash functions which are designed to maximize collisions: Soundex is an example. Obviously, this makes it a very crappy secure hash function. –  Jörg W Mittag Apr 27 '12 at 15:25
    
@JörgWMittag: Not just crappy as a secure hash, but would also be quite poor for use with a hash table. Then again, while certainly somewhat hash-like, I'd hesitate to call Soundex a hash function, simply because its intent and use is so thoroughly different from normal hash functions. –  Jerry Coffin Apr 27 '12 at 15:28
    
@JerryCoffin: I guess it depends on the definition. E.g. the English Wikipedia page simply says that a hash function is any algorithm or subroutine that maps a larger (potentially infinite) set of arbitrary values into a smaller, finite set of (typically scalar) values. Whereas the German Wikipedia page says that the "hashing" (German: "zerhacken") is an integral part, i.e. that collision avoidance and distribution of the mapped values is key. Soundex very much fulfills the first definition but not the second. –  Jörg W Mittag Apr 28 '12 at 0:24
add comment

Read this http://www.codinghorror.com/blog/2012/04/speed-hashing.html it will explain everything much better than I could ever explain it. Here are the two most important headers in the article that directly address your question:

  • Secure hashes are designed to be tamper-proof
    • changes its output radically with tiny single bit changes to the input data
  • Secure hashes are designed to be slow

His TL;DR section at the end:

If you are a user:

Make sure all your passwords are 12 characters or more, ideally a lot more. I recommend adopting pass phrases, which are not only a lot easier to remember than passwords (if not type) but also ridiculously secure against brute forcing purely due to their length.

If you are a developer:

Use bcrypt or PBKDF2 exclusively to hash anything you need to be secure. These new hashes were specifically designed to be difficult to implement on GPUs. Do not use any other form of hash. Almost every other popular hashing scheme is vulnerable to brute forcing by arrays of commodity GPUs, which only get faster and more parallel and easier to program for every year.

share|improve this answer
3  
Jeff has it wrong here on the second point ... while for some uses (as password hashing and key derivation from a password) you want to be slow, for other uses (like message authentication, signatures, etc.) fast (secure) hash functions are good. –  Paŭlo Ebermann Apr 26 '12 at 20:04
    
You are correct Paŭlo. The performance of the hash depends on the application of the hash. However, slow hashes are always more secure than fast ones. The reason you would use a fast hash is if you are okay sacrificing security for performance. –  Nate Apr 26 '12 at 22:04
2  
@Nate “More secure” is always ambiguous, but even under the most charitable application, “slow hashes are always more secure than fast ones” is definitely wrong. There are plenty of applications where the speed of a hash is irrelevant. –  Gilles Apr 26 '12 at 22:07
    
@Gilles can you give an example? That actually sounds true to me, but more specifics would be helpful. –  Nate Apr 26 '12 at 22:14
2  
@Nate The most obvious application of hashes is verifying the integrity of a piece of data: transmit the hash over a secure but possibly low-bandwidth channel, transmit the possibly large payload over an insecure channel, then check that the received payload has the expected hash. Hashes also figure prominently in signing methods (where you not only verify the integrity, but also who sent you the data). Hashing passwords is rather the exception. –  Gilles Apr 26 '12 at 22:17
add comment

A "secure" hash is a hash that is believed to be difficult to "spoof" in a formulaic, reproducible way without prior knowledge of the message used to create the hash. As that information is generally secret, hence the need for a hash, this is a good property of a hashing function intended for use in authentication.

A hash is generally considered "secure" if, given a message M, a hash function hash(), and a hash value H produced by hash(M) with a length in bits L, none of the following can be performed in less than O(2L) time:

  • Given hash() and H, produce M. (preimage resistance)
  • Given hash() and M, produce a different M2 such that hash(M2) == H. (weak collision resistance)
  • Given hash(), produce any M1 and M2 such that hash(M1) == hash(M2). (strong collision resistance)

Additionally, a "secure" hash must have a hash length L such that 2L is not a feasible number of steps for a computer to perform given current hardware. A 32-bit integer hash can only have 2.1 billion values; while a preimage attack (finding a message that produces a specific hash H) would take a while, it's not infeasible for many computers, especially those in the hands of government agencies chartered with code-breaking. In addition, an algorithm that creates and stores random messages and their hashes would, according to probability, have a 50% shot at finding a duplicate hash with each new message after trying only 77,000 messages, and would have a 75% chance to hit a duplicate after only 110,000. Even 64-bit hashes still have a 50% chance to collide after trying only about 5 billion values. Such is the power of the birthday attack on small hashes. By contrast, a computer looking for collisions in a 256-bit hash (SHA-256) wouldn't even have a one-in-a-billion chance for the next message it tried to collide until it had tried 15 decillion numbers (1.5*1034).

Most demonstrated attacks on cryptographic hashes have been collision attacks, and have demonstrated the ability to generate colliding messages in less than 2L time (most have still been exponential-time, but reducing the exponent by half is a significant reduction in complexity as it makes a 256-bit hash as easy to solve as a 128-bit, a 128-bit as easy to solve as a 64-bit, etc).

In addition to small hash size, other factors that can make a hash demonstrably insecure are:

Low work - a hash designed for use by a hashtable or for other "checksum"-type purposes are usually designed to be computationally inexpensive. That makes a brute-force attack that much easier.

"Sticky State" - The hashing function is prone to patterns of input where the current hashed value of all inputs so far does not change when given a particular additional byte of input. Having "sticky state" makes collisions easy to find, because once you identify a message that produces a "sticky state" hash it is trivial to generate other messages that have the same hash by appending input bytes that keep the hash in its "sticky state".

Diffusion - Each input byte of the message should be distributed among the bytes of the hash value in an equally-complex way. Certain hash functions create predictable changes to certain bits in the hash. This again makes collision creation trivial; given a message that produces a hash, collisions can be easily created by introducing new values to the message that only affect the bits that change predictably.

share|improve this answer
add comment

What about a hash that constantly changed? So, you have a key and a door with a hash right? What if you could scramble the keys and doors by having a function to apply a change to the hash each time it was run? Since the contents function is only runtime and exists as code it would be difficult to crack. Maybe?

share|improve this answer
3  
A hash that constantly changed would prevent the primary use of a hash; that is the ability to compare two hashes and determine equality of their source plaintexts. The behavior you describe would have to be expected by both parties and would be similar to the function of a one-time pad in cryptography. –  KeithS Apr 26 '12 at 18:44
    
...and I don't think a one-time really counts as a hash function. –  FrustratedWithFormsDesigner Apr 26 '12 at 19:03
1  
What you're describing is more of a salt than a hash. ie. Something which is added to a key to further obfuscate it but which can still be recognised by the lock. As KeithS says, this is something like a one-time pad and, like a one-time pad, you would have to transfer a number of salts to both devices at some point, which then get used in cycle until you generate some more. Over-complicated for most situations, but certainly doable and secure. –  pdr Apr 26 '12 at 19:27
add comment

Use the right algorithm for the task at hand.

CRCs are used for error detection/correction.

Cryptographic message digests such as SHA2 are used as a building block for cryptographic constructs (digital signatures, MACs, key derivation/password hashing functions) and security protocols.

In hash tables/dictionaries/maps use SipHash.

What you call insecure hashing algorithms should not be used in hash tables, as proven by the following CVE entries: CVE-2003-0364, CVE-2011-4461, CVE-2011-4838, CVE-2011-4885, CVE-2011-4462, CVE-2011-4815, CVE-2012-0840, CVE-2012-5371, CVE-2012-5374, CVE-2012-5375

share|improve this answer
add comment

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.