How to evaluate the strength of a hashing algorithm?

Question

At work the hashing algorithm we use for passwords appears to be bespoke. Obviously that's a pretty bad idea, but the management don't seem bothered.

The algorithm always produces 20 character long upper case strings. One particularly worrying aspect of its behaviour is that similar passwords produce similar hashes: Password1 and Password2 produce hashes that are different by only about 5 characters.

The other obvious issue is that it doesn't look like the algorithm is deliberately slow, which I'm told good hashing algorithms (bcrypt, scrypt) should be.

How does one go about evaluating the strength of a hashing algorithm? And what sorts of attacks should we be particularly concerned about with a fast hashing algorithm with poor uniformity?

I have access to the source (although unfortunately I can't post it on a public forum, for obvious reasons).

Answer 1

A strong hashing algorithm would imply that changing even one character will result in a completely different hash.

A good hashing algo has these characteristics:

• The hash value is determined by the data being hashed
• The hash function uses all given data
• The hash distributes all possible hashes uniformly across all possible hash outcomes
• If you have a string and you take a very similar string, you will get a completely different hash result (changing one single bit of input should change all output bits with a probability of 50%. Another requirement is that the hash is, to the highest extent possible, statistically independent of the input, e.g. a high hamming weight in the input does not produce an abnormal hamming weight in the output. -Polynomial)

Please tell your management

not to be Dave, and just use one of the standard hashing algorithms. If you are using the hashes to store passwords, use bcrypt. When hashing a password you are also concerned about salts, bcrypt does all that for you. Plus it's all free.

Answer 2

Noticing that:

similar passwords produce similar hashes: Password1 and Password2 produce hashes that are different by only about 5 characters

is enough to declare that this "hashing" algorithm is pure junk. The least that an algorithm which purports to be a "hash" is to, at least, look random. Even thoroughly broken algorithms like MD4 or even non-cryptographic hashes (like CRC32) offer an output which is "satisfying" with regards to simple statistical analysis.

The hash function you allude to appears to follow the Hollywood fantasy of "close decryption" (when you have almost the right key, the text is almost readable, just a bit blurred). This is just a revival of the Mastermind board game.

Security is about defeating a dedicated, smart and malevolent adversary. The hash function at your work can be breached by a chimpanzee.

Answer 3

A professional evaluation is very complicated and has to be done by experts in the field over a long time. That being said, I don't think you need to have an expert have a look at this: With a fast hashing algorithm with poor uniformity and small size (20 uppercase characters are approximately 94 bits, even md5 has 128) you are vulnerable to both brute force attacks and hash collision attacks.

Your company should change this system asap.

(Actually, depending on how bad that algorithm really is, it may be possible to reverse it so that a quick program can immediately give correct passwords for certain hashes. This is particularly terrible as it would break all passwords at once.)

Answer 4

A good hashing function must have what's called good "avalanche characteristics"; a small change to the message produces a large (and theoretically unpredictable) change in the hash digest. Your hash function has very little avalanche effect.

Avalanche effect is one of the primary ways that hash functions resist "preimage attacks". A preimage attack is essentially "de-hashing" the digest; given a hash digest and the hash function, find a message (usually any will do; sometimes there are message length and byte value limitations) that will produce the target hash. The basic purpose of a hash function is its deterministic but one-way transformation, and so any algorithm that can find a preimage in less than 2^N time, for a hash digest of N bits, should be taken as evidence that the hash is fundamentally broken.

Case in point; the low avalanche effect means that the changes to a hash digest, given a known change to the message, can be tracked and predicted. That allows for a "goal-seeking" approach; given a starting message, make a small change, compute the hash, and see if it's "closer" to the real one (more of the correct bits set). Surgical changes can then be used to mold the working message into a preimage.