Practical key-recovery attack against APOP, an MD5-based challenge-response authentication. (7th February 2008)

• Record Type: Journal Article
• Authors: Leurent, Gaetan
• Is Part Of: International journal of applied cryptography. Volume 1:Number 1(2008)
• Page Start: 32
• Page End: 46
• Publication Date: 2008-02-07
• Subjects: hash functions -- MD4 -- MD5 -- message modification -- meaningful collisions -- APOP security -- key recovery attack -- challenge-response authentication -- applied cryptography -- collision attacks -- authentication protocols; Data encryption (Computer science) -- Periodicals; Cryptography -- Periodicals; Computer security -- Periodicals; 652.8
• Languages: English
• ISSNs: 1753-0563

Abstract

Hash functions are used in many cryptographic constructions under various assumptions, and the practical impact of collision attacks is often unclear. In this paper, we show how collisions can be used to recover part of the password used in the APOP authentication protocol. Since we actually need a little more than mere collisions, we look into the details of MD5 collisions. In Wang's attack, message modifications allow to deterministically satisfy certain sufficient conditions to find collisions efficiently. Unfortunately, message modifications significantly change the messages and one has little control over the colliding blocks. In this paper, we show how to choose small parts of the colliding messages, which will allow to build the APOP attack. This shows that collision attacks can be used to attack real protocols, which means that finding collisions is a real threat.