[erlang-questions] wow: MD5 broken

[Richard Kelsall]

Toby Thain wrote:
...
> My point was that any *single* hash might one day be shown vulnerable to 
> a similar technique, but using two together (as is sometimes already 
> done) should be much more resistant?
...

Hello Toby, Sorry, I should have explained that a bit. In essence
using two weak hashes rather than one strong hash is more work
for a less secure result. SHA-256 is perfectly good, but if you're
at all worried about it then use SHA-512 which is vastly more secure.

If you're worried the NSA has put a back-door in SHA-512 then
concoct your scheme by put something on top of it in a way that
you know the result will be at least as secure as SHA-512. Do not
start with weak components like MD5 and SHA-1.

Here's an extended and corrected version of my post on this page
that maybe explains some of my reasoning

http://www.lightbluetouchpaper.org/2007/11/23/a-cryptographic-hash-function-reading-guide/

A hash may be applied to a very large file that won't fit in memory
and normally processes the whole file in one pass. (Or a hash may be
applied to data fed through a communications device in which case
you may have to do it in one pass.) By using two hashes you have
potentially doubled the file access effort. I suppose we could
theoretically re-write the two hash functions to interleave as
the file data becomes available, but this isn't worth doing because
the result, as well as being more work, would also be less secure
than one strong hash.

A hash needs to be as short as possible because we may store and 
transfer lots of them and don’t want to waste effort with longer
than necessary hashes. Storing two different hashes adds length
without fully utilising the extra length. (I think this may be
because you have two separate piles of bits that never mix rather
than one big pile that is totally mixed. Compare 64! with 32! * 32!
and you're probably in the right area.) Since we're not using the
extra length it might be better to XOR the hashes onto each other,
but either way you risk some sort of unknown interaction between
the hashes that may weaken the combination. If you are going to do
two passes over the file I think it would be better to do it like
this :

Hash2( Hash1( message ) + message )

but not like this :

Hash2( message + Hash1( message ) )

rather than like this :

Hash1( message ) + Hash2( message )

Given diverse algorithms for Hash1 and Hash2 this looks like a good 
scheme to me. You can extend this recursively to as many different
hashes as you want. The strength will of course be limited by the
length of the final hash.

Michael's post looks correct and maybe explains some of this better.
Michal's post however I disagree with for the reasons I give above.


Richard.