Well, from the discussion of hashing methods weaknesses, I've got that the only ol' good brute-force is efficient to break.
So, the question is:
Is there a hashing algorithm which is more rigid against brute-force than others?
In case of hashing passwords.
The only protection against brute force is the fact that it takes an inordinately long time to perform a brute force.
Brute force works by simply going through every possible input string and trying it, one at a time. There's no way to protect against simply trying every possible combination.
This question is a decade old and now I've got the answer.
Yes, there are bruteforce-proof algorithms. The key for such algo is being slow. It will do no harm if correctness will be verified in a few milliseconds. But it will drastically slow the brute-force. Moreover, those algorithms can adapt to the future CPU's performance increase. Such algorithms include
Particularly in PHP, the password_hash() function must be used for hashing passwords
If you know that the input space is small enough for a brute force attack to be feasible, then there are two options for protecting against brute-force attacks:
So that's the answer: the slower a hash algorithm is to compute, the less susceptible it is against brute-forcing the input space
(Original Answer follows)
Any additional bit in the output format makes the algorithm twice as strong against a straightforward brute force attack.
But consider that if you had a trillion computers that could each try a trillion hashes per second, it would still take you over 100 trillion years to brute-force a 128 bit hash, and you'll realize that a straightforward brute-force attack on the output is simply not worth wasting any throughts on.
Of course, if the input of the hash has less than 128bits of entropy, then you can brute-force the input - this is why it's often feasible to brute-force password cracking (Nobody can actually remember a password with 128 bits of entropy).
Brute force is the worst attack, nothing can be brute force proof...
right now ~80-90 bits is considered cryptographically safe from a brute force attack standpoint, so you only need 10 bytes if a Collision Resistant Hash function is perfect, but they aren't so you just do more bits...
the proof that nothing can be brute force proof is in the Pigeon Hole Principle.
since hash function H allows arbitrary sized input [0,1]^n and outputs constant output [0,1]^k when the size of input exceeds the output size:, n>k, there are necessarily some outputs that can be produced by more than one input.
you can visualize that with a square divided into 9 sub squares.
0 | 0 | 0
0 | 0 | 0
0 | 0 | 0
these are your 9 holes. We are a brute force attacker, we have unlimited chances to attack... we have unlimited pigeons... but we at most need 10 to find a collision...
after 4 pidgeons and a good collision resistant hashing algorithm:
P | 0 | 0
0 | P | P
0 | 0 | P
after 9 pidgeons:
P | P | P
P | P | P
P | P | P
so our 10th pigeon will necessarily be a collision, because all of the holes are full.
but it really isn't even that good, because of another numerical property called the Birthday Paradox where given a number of independent selections you will find a duplicate much much faster than it takes to fill all of your "holes".
Consider the output of the hash algorithms.
A MD5 (128 bit) or SHA-1 (160 bit) is certainly easier to brute-force than a SHA-2 (224, 384 or even 512 bit).
Of course, there can be other flaws (like in MD5 or a bit less in SHA-1) which weaken the algorithm a lot more.
As Codeka said, no hashing algorithm is 100% secure against brute force attacks. However, even with hardware-assisted password cracking (using the GPU to try passwords), the time it takes to crack a sufficiently long password is astronomical. If you have a password of 8ish characters, you could be vulnerable to a brute force attack. But if you add a few more characters, the time it takes to crack increases radically.
Of course, this doesn't mean you're safe from rainbow attacks. The solution to that is to add a salt to your password and use a hashing algorithm that isn't vulnerable to preimage attacks.
If you use a salted password of 12-14 characters, preferably hashed with an sha2 algo (or equivalent), you've got a pretty secure password.
Read more here: http://www.codinghorror.com/blog/2007/10/hardware-assisted-brute-force-attacks-still-for-dummies.html
All cryptographic systems are vulnerable to brute force. Another term for this is a "Trivial Attack".
A simple explanation for hashing is that all hashing algorithms we use accept an infinitely sized input and have a fixed sized output. This is an unavoidable collision, and for something like sha256 it takes 2^256 operations to find one naturally. md5() has a shortcut making it 2^39th operations to find a collision.
One thing you can do to make your passwords stronger is to hide your salt. A password hash cannot be broken until its salt is retrieved. John The Ripper can be given a Dictionary, a Salt and a Password to recover password hashes of any type. In this case sha256() and md5() will break in about the same amount of time. If the attacker doesn't have the salt he will have to make significantly more guesses. If your salt is the same size as sha256 (32 bytes) it will take (dictionary size)*2^256 guesses to break one password. This property of salts is the basis of CWE-760.
