Re^12.5: On showing the weakness in the MD5 digest function and getting bitten by scalar context

And any application, especially a security application that ignores the congectural nature of the uniqueness factor of md5s, and relies upon that uniqueness, is broken--not by this discovery, but by design.

Everything is conjecture, I'm afraid. If you're holding out for absolute proof of security, you will be waiting a long time.

What assurances we have come from mathematical proofs that assume the existence of a collision-free hash function(1) and reason from there. Since someone has found a way to generate collisions, that makes the proofs useless for MD5. You are correct in pointing out that the collisions that are generated take a particular form, and that form may or may not expose an actual vulnerability in real cryptographic protocols. We could try to prove that no vulnerability exists, but the proofs would become fiendishly difficult, and not everyone would have confidence in the ability of mathematicians to get them right. The prudent course of action is to switch to a hash function for which the original conjecture still holds.

(1) Collision-free is a technical term meaning collisions are hard to find, not that they don't exist. Some proofs don't need the collision-free property, so I guess they're still safe. Void where taxed, licensed, or restricted. Professional driver -- do not attempt.

Others must reach their own conclusions, based on their knowledge of their uses of md5...

Another interesting thing about cryptography is that everyone thinks they're an expert.

Comment on Re^12.5: On showing the weakness in the MD5 digest function and getting bitten by scalar context

Replies are listed 'Best First'.
Re: Re^12.5: On showing the weakness in the MD5 digest function and getting bitten by scalar context by BrowserUk (Patriarch) on Aug 30, 2004 at 19:41 UTC
I can't (nor would I try) to dispute the math, but I do wonder about your conclusion: The prudent course of action is to switch to a hash function for which the original conjecture still holds. Given that it is sheer scale, that is the basis of these hashing algorithm's utility, it is almost non-sequitous to consider proving them. The very thing that prevents them from being trivially cracked through brute force, is the same thing that prevents them from being rigorously proved by that same method. Mathematicians can construct proofs (that are way (way, way) over my head) for seemingly much more complex algorithms than these. Many such proofs have later been shown to be false, in the light of further analysis, years or even decades later. Anyone who's read ISBN 1-85702-699-1 know's this to be so. Any new algorithm is just as likely to be weak in the same respect as md5. Except it could be that those that discover the weakness of a new algorithm are not so publically spirited as to announce their discovery to the entire world. To me, (a self described non-expert), it seems it would make more sense to base one's security upon protocols that acknowledge that hashing algorithms do produce duplicates and factor that into the overall protocol. It also makes sense to use the combinatorial effect of multiple passes of the same (or different) weak hashes to produce a much harder target for the mathematical attack to aim for. Admittedly, these can be even harder to prove, but in that lies a little reassurance that the are also harder to attack. It also seems that it would be better to analyse the method of attack, and use it's properties to devise protocols that specifically counter that attack, than to surrender that hard won knowledge in favour of another, equally unverified and unverifiable algorithm. Another interesting thing about cryptography is that everyone thinks they're an expert. S'funny, but had you said that about security, I would have been in complete agreement. The world, or at least the internet, seems to be full of, usually self proclaimed, "security experts". In my experience, there is nothing more dubious than those that need to "claim" expertise. If your a student of the history of cryptography, you'll know that most of the best cryptographers have been hobbiest and enthusiasts, though many were mathematicians first and foremost. As for myself, it is yet another of those subjects that I am facinated by, but claim absolutely zero expertise in. Not in this thread, nor any other will you see me claim expertise. I have some experience in a range of different computer related fields. And I've worked with, and know, some genuine experts in several. Nothing more. I am reminded of (one of) Pournelle's Laws: If you don't know what you're doing, make sure you know someone who does. Examine what is said, not who speaks. "Efficiency is intelligent laziness." -David Dunham "Think for yourself!" - Abigail "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon	[reply]

Replies are listed 'Best First'.

Re: Re^12.5: On showing the weakness in the MD5 digest function and getting bitten by scalar context
by BrowserUk (Patriarch) on Aug 30, 2004 at 19:41 UTC

I can't (nor would I try) to dispute the math, but I do wonder about your conclusion:

The prudent course of action is to switch to a hash function for which the original conjecture still holds.

Given that it is sheer scale, that is the basis of these hashing algorithm's utility, it is almost non-sequitous to consider proving them. The very thing that prevents them from being trivially cracked through brute force, is the same thing that prevents them from being rigorously proved by that same method.

Mathematicians can construct proofs (that are way (way, way) over my head) for seemingly much more complex algorithms than these. Many such proofs have later been shown to be false, in the light of further analysis, years or even decades later. Anyone who's read ISBN 1-85702-699-1 know's this to be so.

Any new algorithm is just as likely to be weak in the same respect as md5. Except it could be that those that discover the weakness of a new algorithm are not so publically spirited as to announce their discovery to the entire world.

To me, (a self described non-expert), it seems it would make more sense to base one's security upon protocols that acknowledge that hashing algorithms do produce duplicates and factor that into the overall protocol. It also makes sense to use the combinatorial effect of multiple passes of the same (or different) weak hashes to produce a much harder target for the mathematical attack to aim for.

Admittedly, these can be even harder to prove, but in that lies a little reassurance that the are also harder to attack.

It also seems that it would be better to analyse the method of attack, and use it's properties to devise protocols that specifically counter that attack, than to surrender that hard won knowledge in favour of another, equally unverified and unverifiable algorithm.

Another interesting thing about cryptography is that everyone thinks they're an expert.

S'funny, but had you said that about security, I would have been in complete agreement. The world, or at least the internet, seems to be full of, usually self proclaimed, "security experts". In my experience, there is nothing more dubious than those that need to "claim" expertise.

If your a student of the history of cryptography, you'll know that most of the best cryptographers have been hobbiest and enthusiasts, though many were mathematicians first and foremost. As for myself, it is yet another of those subjects that I am facinated by, but claim absolutely zero expertise in. Not in this thread, nor any other will you see me claim expertise. I have some experience in a range of different computer related fields. And I've worked with, and know, some genuine experts in several. Nothing more.

I am reminded of (one of) Pournelle's Laws: If you don't know what you're doing, make sure you know someone who does.

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

[reply]