# TCR hash functions from MD5

I'm reading Collision-Resistant Hashing: Towards Making UOWHFs Practical (pag. 10 and 11) and here say

The most direct way to construct a TCR hash function is to key a function like MD5 or SHA-1. ...

A safer approach might be to incorporate key bits throughout the message being hashed. For example, with $|K| = 128$ one might intertwine $128$ bits of key and the next 384 bits of message into every 512-bit block. (For example, every fourth byte might consist of key.) Now the cryptanalyst's job amounts to finding a collision $M,M'$ in MD5 where we have pre-specified a large number of (random) values to be sprinkled in particular places throughout $M$ and $M'$ . This would seem to be very hard.

... But if I add keys bits throughout the message being hashed; for me, nothing prevents fall in the MD5 again (MD5 is broken), then my question is Why that approach is safer?

• MD5 being broken only means that an attacker can find collisions when its used without a key. – CodesInChaos Nov 28 '13 at 12:44