Title: Practical key-recovery attack against APOP, an MD5-based challenge-response authentication

Authors: Gaetan Leurent

Addresses: Laboratoire d'Informatique de l'Ecole Normale Superieure, Departement d'Informatique, 45 rue d'Ulm, Paris Cedex 05 75230, France

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.

Keywords: hash functions; MD4; MD5; message modification; meaningful collisions; APOP security; key recovery attack; challenge-response authentication; applied cryptography; collision attacks; authentication protocols.

DOI: 10.1504/IJACT.2008.017049

International Journal of Applied Cryptography, 2008 Vol.1 No.1, pp.32 - 46

Published online: 06 Feb 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article