Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
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?
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:
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 the next one ("Secure Hash Algorithm 3") is currently in the process of being standardized, after a competition.
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:
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:
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.
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)
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.
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:
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.
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:
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.
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
