This Hash Result Startled Me!

Even when you work with this technology, sometimes you are really surprised to find that things don’t work at all as you might expect.

Hash functions are one-way operations. It is easy to calculate the hash of even a large piece of data. But it should be impractically difficult to find an input that generates a specified output.

The Flame malware, which I discussed recently, relied on a forged Microsoft signature. This required a combination of a previously undescribed cryptographic breakthrough and brute-force searching.

To everyone’s benefit, this has brought more attention of hash functions.

This being cryptography, it isn’t easy going.

Summaries in cybersecurity newsletters point us to things like “Attacks on Hash Functions and Applications,” which happens to be Marc Stevens’ Ph.D. thesis, which leads in turn to research papers like “Breaking the ICE — Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions” and “Multicollisions in Iterated Hash Functions: Application to Cascaded Constructions.” These aren’t easy reading, but they lead to a fairly simple conclusion that really surprised me.

A collision is the situation when two different inputs generate identical hash outputs. If you can find different inputs that collide with an existing example, then you could forge a digital certificate. We want it to be hard enough to find a collision that we don’t need to worry about our adversary doing that.

The thing is, once you define a hash function you’re stuck with it for all time. But mathematicians can can discover mathematical weaknesses, however subtle, and computers certainly get faster and faster. We’re stuck with a static defense while the attacks improve. “Hard enough” today will eventually, perhaps soon, not be good enough.

Let’s say that you have multiple hash functions available. It certainly seemed reasonable to me to assume that if it was hard to find a pair of inputs that collided in any one of these hash functions, it would be astronomically more difficult to find a pair of inputs that simultaneously collided in two different hash functions.

Here is why I leave the analysis of cryptographic functions to the pros:

These studies consider the approach of concatenating the outputs of multiple hash functions of the input. “Concatenate” means simply writing one right after the other: Thesewordshavebeenconcatenated. So, maybe you calculate the MD5, SHA-1, and RIPEMD-160 hash values for a given input and write them as one 448-bit string. Examples of collisions for individual hash functions have been published, but to collide in two, let alone three, simultaneously would be so much more difficult we wouldn’t have to worry about it, right?

Wrong!

Collisions in the concatenation of multiple hash functions, as long as they are all iterated functions (as our current toolkit provides), are no more difficult to find than a collision in the single strongest one.

Wow. Mind = blown.

We who aren’t mathematical geniuses will never create a useful cryptographic function of our own. We must carefully choose from what is available. Learning Tree’s Cloud Security Essentials course discusses how to compare the available security offerings.

Bob Cromwell

Type to search blog.learningtree.com

Do you mean "" ?

Sorry, no results were found for your query.

Please check your spelling and try your search again.