Which hashing function do YOU trust?

[mjuarez]

I'm doing a thesis/project involving hashes to verify authenticity, and I've been wondering which hash function is trusted today as a secure hash standard.

I've been doing a lot of reading lately, and although the commercial side of computing has decided that 128-bit MD5 is enough for their needs, the academic community is not really that sure. I've seen things like the MD5CRK project [http://www.md5crk.com/], which try to find collisions in MD5 out of completely different meaning (but still legible) text. Then there's also the classic man-in-the-middle and birthday theoretical attacks, but I've still to see any real life examples of one of these attacks.

Schneier trusts NSA's SHA-1, according to his "Applied Cryptography" book, but there's people around here mentioning SHA-256 as the bare minimum. There's even a SHA-512. And of course, there's also HAVAL, RIPE-MD, Tiger, GOST-hash and others, all of which seem "better than MD5" in most cases.

Finally, there's something I've been thinking about, which is a dual-hash security algorithm. That is, include the original text that needs to be authenticated, and, say, an MD5 hash and a SHA-512 hash (both signed, if needed). The computational power needed for getting an MD5 collision is already huge, but it would seem to me that the computational power needed to find a duplicate message that encodes to the same MD5 and SHA-512 values would be completely out of this universe. (This is just my opinion. Please correct me if I'm wrong).

Comments?

Marcos

[Stormhawk]

From the paranoia-model point of view, I'd say SHA-256 as the bare minimum. However, to all intents and purposes, MD5 is good enough for most everyday use. From a cryptographic point of view, however, MD5 doesn't present the desired security level. I'm sure JustinT will be down on this thread like a vulture as soon as he sees it; and will provide a coherent and useful explanation for this tendency to lean towards SHA-256 as the bare minimum, along with many reasons for the reduction in trust of MD5.

In the meantime, a search or browse through the crypto forums here should present you with many threads on related topics, including a now lengthy thread on "cracking" MD5, located here.
_________________
Andrew J. Bennieston
http://www.nmap-tutorial.com/

[JustinT]

This has been discussed before, but it's a good topic to refresh ourselves on, so thanks for posting this thread. It's best that folks are aware of what we deem as an acceptable security margin.

In short, the SHA structure, itself, has proven to be resilient to most of what we generally design a hash function to resist, hence why SHA-1 has long since been a co-de facto standard, alongside MD5. It's essentially NSA-made, and contrary to what the overly-paranoid want to believe, they know how to make good cryptography. We can skip the internals of these hash functions in questions, and get right to addressing the core of the topic - "Which hash function do we trust." Trust is an enormous word. To quote myself, first, I'm going to define the word trust, as the integral meaning of this word is vital in understanding my views:

trust - one in which confidence is instilled; reliance; an entity entrusted to one to be used or cared for in the interest of another; a duty or charge imposed in faith or confidence.

We'll have to assume the hash function meets this expectation, practically.

There are decent hash functions, that meet certain security bounds, and for most applicable scenarios in practice, would suffice, realistically. These hash functions come in the form of 128-bit, 160-bit, 192-bit, 224-bit, et cetera. However, just because the hash function, structurally, is secure, it doesn't mean that the security margin it renders is sufficient. Due to the issues I have raised in a post entitled, "Just How Secure ARE Those 128-bit Keys", it's going to take double-the-n to give us the security of n. We should only tolerate 128-bit security marings, so we need 256-bit minimum bounds for any cryptographic value of this sort. In other words, 128-bit, 160-bit, 192-bit, and 224-bit values fall short, by only rendering 64-bit, 80-bit, 96-bit, and 112-bit security margins. 256-bit values give us 128-bit security margins - that's what we're after. That's why SHA-256 is a conservative minimum. This is the most realistic form of trust we can conjecture.

Because of the simple fact that, in practice, 128-bit, 160-bit, 192-bit, and 224-bit designs will suffice, both in satisfying certain security bounds and resilience to the average computational resources available to an analyst, provided there is not mathematical way to exploit the algorithm, most don't feel it inherent to bump up the minimum bound for security, because these parameters are "good enough." For the majority of purposes, they'll get lucky and remain secure, for a myriad of environmental conditions.

However, there are those cryptographers among us, such as myself, that push for maximum security etiquette, above all. We try to get the most out of what we have, so we set sufficiently large minimum bounds, and allow for flexibility, when it comes time to raise the notch on the sizes of the values we choose.

Assuming that the algorithm is secure, our 256-bit minimum bound holds one significant purpose; that being, it provides us with a 128-bit security margin. This is only effective if the underlying algorithm is resilient to cryptanalytical attacks that we intend for them to thwart, during their design phase; this doesn't necessarily mean, in any way, that a larger hash is inherently more secure than a smaller hash. This only holds true if you can ensure that both algorithms are secure against attack methodologies they were designed to resist. Even then, you can't always be certain. So, as aforementioned, we assume, to the best of our cryptographic knowledge, that the algorithm is cryptographically sound, and at that point, we specify parameters that utilize this algorithm in the most secure fashion. 256-bit values fit the bill, for now. Naturally, go higher from the get-go, if you can afford it; if you can't, at least allow the flexibility to do so in the future.

So, trusting the SHA design is nothing we've just started doing; trusting 256-bit values as our minimum bound, however, is something we need to start doing, very soon. The magnitude of this matter is just as much about the latter, as it is the former.
_________________
"Strict Avalanche Criterion n. Restrictive clause in ski-insurance policy."

[mjuarez]

Thanks for the comments, JustinT and Technetium. After reading your responses, and investigating quite a bit more, I'm now convinced of the need to abandon 128-bit one-way hashes in favor of 256-bit or even 512-bit ones.

Anybody care to comment on my dual-hash scheme? Although it might make the hashing/verification cumbersome, it would seem to me that this approach would nullify the potential danger of somebody breaking one of the hash algorithms in the future (ie, maybe useful for a signature which has to resist 20-50 years).

BTW, Whirlpool seems like a very good 512-bit hash function, based on the AES cipher, and designed by one of the Rijndael creators, but I still haven't seen enough analysis out there to trust it completely.

http://planeta.terra.com.br/informatica/paulobarreto/WhirlpoolPage.html

What's your opinion on this relatively recent one-way hash function?

Thanks,

Marcos

[JustinT]

Whirlpool comes to us from two noted designers in this field, Rijmen and Barreto, who've collaborated on other interesting designs, so there is no surprise that I find this to be one of the most interesting hash functions. There isn't a wealth of analysis representing it, other than what was conducted by the designers and through the Nessie project, of which it was a submission. As such, there isn't that much I can say about the confidence instilled by the utilization of this algorithm; however, I can comment a bit about what I like about what I'm aware of, simply because Whirlpool is constructed of, essentially, conceptual structures that we've seen before (i.e., Merkle-Damgård strengthening, Miyaguchi-Preneel hashing schematics, et cetera), so that aids in the process of cryptanalyzing it.

The core of this hash function is basically a block cipher, operating on 512-bit blocks, which they deem W. This block cipher is what compares to Rijndael, in several respects, but there are still contrasting elements that differentiate the two, and correspond to different aspects of security notions. Overall, I'd have to say they remain quite relative in design.

Assuming the Whirlpool design is free from any algorithmic defects, structure-wise, we're dealing with a 256-bit security margin, based on the expected occurrence of collisions after 2^n/2 Whirlpool executions. This is twice that of the 128-bit security margin I recommend for our minimum, tolerable bound; of course, this is nice. There is also support for security notions that state resilience against both linear and differential cryptanalysis. It was obviously designed to resist attack methodologies for hash functions, and provide a certain degree of confidence for its thwarting of internal collisions. Using a block cipher construct to act as a hash function is nothing new, and the security notions satisfied by this are often much easier to cryptanalyze, and demonstrate provability for, than strictly one-way hash functions. The results I've seen are promising.

I normally recommend the SHA design, and for a 512-bit hash, I'd normally go with SHA-512, because of that. This advocation is based solely on the favorable margin of security we've witnessed during the cryptanalysis of SHA principles, and the length of time it has been deployed in the conventional, public mainstream. Although Whirlpool hasn't yet seen this kind of treatment, I generally like its design, and the fact that it was designed by two gurus, and chosen for the Nessie project, who's foundation is composed of a majority of the most prolific cryptographers and cryptanalysts we have, helps to ease my mind a bit, as to how much I do trust it. Simply put, and all things considered, if not SHA-512, then I'd feel moderately comfortable using Whirlpool.

As for your "dual-hash scheme", there are notions to show where it may obfuscate trivial cryptanalytical attempts that plague other schemes, where the input is something predictable, such as dictionary attacks. The reason being, the input to a second hash function has already undergone a "random mapping", which is the general theoretical definition, and aim, of a hash function, so you have much more randomization, and less predictability. Much of this would fall under similar notions as cascading block and stream ciphers, in that the overall design may or may not be as secure as the strongest algorithm, based on how the algorithms commute or relate in structure. Analyses show it can sway either way, so a definite answer ultimately depends on the configuration. In my opinion, I can see the advantageous effect of making things much more difficult for an attacker, so there seems to be some inherent security, in that regard. However, using sufficiently large, secure hash functions, in solitaire, will give you security margins that are cryptographically satisfiable; hence, why you don't see many of such designs used in practice. The same goes for most cryptographic primitives. Still not a bad idea, nonetheless.
_________________
"Strict Avalanche Criterion n. Restrictive clause in ski-insurance policy."