[Cryptography] multicollision resistance in protocol design?

[Ron Garret]

On Oct 21, 2015, at 3:37 PM, Ray Dillinger <bear at sonic.net> wrote:

> 
> As everyone on this list is aware, MD5 is no longer suitable for use
> as a general purpose cryptographic hash function because it lacks
> strong collision resistance.  It is now known how to generate pairs
> of files having the same MD5 hash.
> 
> However, MD5 still has weak collision resistance (meaning it is hard
> to generate a file that has a predetermined hash) and still has
> multicollision resistance (meaning it is hard to generate sets of more
> than two files which all have the same hash).
> 
> We don't usually think about these weaker properties, but there are
> some peculiar circumstances in which multicollision resistance could
> be useful in protocol design.
> 
> For example, we can present a file and then when we later disclose a
> different file with the same MD5 hash, that can serve as a proof
> that the already-committed file has no MD5 collision with anything
> else.

Intuitively it seems one should be able to construct a hash with strong collision resistance out of one with weak collision resistance by concatenating (or maybe even xoring) two HMACs with different keys.

This seems like the sort of thing that, if it were actually true, would be a known result.  Is it?  Or does it turn out that this doesn’t actually work?

rg

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151021/4372d11b/attachment.sig>