Det har kommit så många olika typer av attacker på hashfunktionen MD5 att man nästan skulle kunna tycka att liket borde få vila i frid. (Bara IACR listar 21 artiklar om MD5.) Men fortfarande används MD5, fortfarande publicerades det nya artiklar om attacker på och svagheter hos MD5.
Den första riktigt stora attacken mot MD5 var den artikel av Wang, Feng och Yu som 2004 presenterade kollisioner mot MD5, HAVAL och RIPEMD.
En av mina sommarläsningsartiklar var A New Collision Differential For MD5 With Its Full Differential Path av Tao Xie, DengGuo Feng och FangBao Liu. Skälet till att jag valde att läsa den är att den inte känns som en i gänget av alla som smånyper lite i sidan på MD5. Nej här handlar det om ett frontangrepp. Mer specifikt hävdar författarna att dom hittat en ny, komplett kollision mot MD5. Författarna skriver:
Since the first collision differential with its full differential path was presented for MD5 function by Wang et al. in 2004, renewed interests on collision attacks for the MD family of hash functions have surged over the world of cryptology. To date, however, no cryptanalyst can give a second computationally feasible collision differential for MD5 with its full differential path, even no improved differential paths based on Wang’s MD5 collision differential have appeared in literature.Firstly in this paper, a new differential cryptanalysis called signed difference is defined, and some principles or recipes on finding collision differentials and designing differential paths are proposed, the signed difference generation or elimination rules which are implicit in the auxiliary functions, are derived.
Then, based on these newly found properties and rules, this paper comes up with a new computationally feasible collision differential for MD5 with its full differential path, which is simpler thus more understandable than Wang’s, and a set of sufficient conditions considering carries that guarantees a full collision is derived from the full differential path.
Finally, a multi-message modification-based fast collision attack algorithm for searching collision messages is specialized for the full differential path, resulting in a computational complexity of 2**36 and 2**32 MD5 operations, respectively for the first and second blocks. As for examples, two collision message pairs with different first blocks are obtained.
Artikeln är tjock, med massor av information. Bland annat finns ett appendix med den kompletta differensvägen (om man skall tro artikeln) samt regler för att skapa kollisioner. Jag kan lätt erkänna att jag som lekman inte hängde med hela tiden, och det berodde inte bara på att skallen var i semester-mod.
Frågan man bör ställa sig är vad artikeln kommer att innebära. Som det verkar går det nu att på rimlig tid (även om 2**36 MD5-operationer inte görs i en handvändning) skapa kollisioner. Detta ökar risken för att den här typen av attackvektorer börjar utnyttjas. Men i vilka sammanhang kan detta vara ett problem?
No related posts.
Related posts brought to you by Yet Another Related Posts Plugin.
I vilka sammanhang kan detta vara ett problem?
Mest känt är väl olika webbsidor där lösenorden ofta hashas med md5 och lagras i någon sql-databas. Ett vanligt sätt att knäcka säkerheten på dessa sidor är att läsa ut md5-hasharna via någon typ av sql-injection. Det borde räcka med att hitta ett lösenord som genererar rätt md5-hash. Det behöver inte vara det rätta lösenordet, bara hashen är rätt. Där kan den här typen av kollissioner spela en roll. Eller behöver man det korrekta lösenordet också för att hitta en kollission?
albert: Nu talar du om att generera en preimage, dvs att givet en hash hitta en sträng som har den hashen. Det är ett annat problem än att hitta två strängar som har samma hash.