Computer Security and Cryptography Reading Group Suggested Reading

A whole bunch of papers from DIMVA 2005 sound very interesting:

• "Hybrid Engine for Polymorphic Shellcode Detection" Udo Payer, Peter Teufl, and Mario Lamberger (Institute of Applied Information Processing and Communications, Austria).
• "Experiences Using Minos as a Tool for Capturing and Analyzing Novel Worms for Unknown Vulnerabilities" Jedidiah R. Crandall, S. Felix Wu, and Frederic T. Chong (UC Davis, USA)
• "METAL - A Tool for Extracting Attack Manifestations" Ulf Larson, Emilie Lundin-Barse, and Erland Jonsson (Chalmers University of Technology, Sweden)
• "A Learning-Based Approach to the Detection of SQL Attacks" Fredrik Valeur, Darren Mutz, and Giovanni Vigna (UC Santa Barbara, USA)
• "Masquerade Detection via Customized Grammars" Mario Latendresse (Volt Services/Northrop Grumman, FNMOC U.S. Navy, USA)
• "A Prevention Model for Algorithmic Complexity Attacks" Suraiya Khan and Issa Traore (University of Victoria, Canada)
• "Detecting Malicious Code by Model Checking" Johannes Kinder, Stefan Katzenbeisser, Christian Schallhart, and Helmut Veith (Technical University Munich, Germany)
• "Enhancing the Accuracy of Network-based Intrusion Detection with Host-based Context" Holger Dreger (Technical University Munich, Germany), Christian Kreibich (University of Cambridge, UK), Vern Paxson (ICSI and LBNL, USA), and Robin Sommer (Technical University Munich, Germany)

This page demonstrates an attack on MD5. Although the attack is not (that) new, the description is clear enough to cause alarm without being clear about the technical limitations of the attack.

Technical limitations:

• Finding a pair of messages which collide is different from finding a collision for an arbitrary input (i.e. birthday paradox [1]).
• Look at the raw postscript (the two inputs provided which match). They differ by only a few bits. The demonstration takes advantage of the fact that two nearly identical postscript documents can look completely different when printed.

That said, there may be applications (such as the one described) where the attacker gets to choose the input to md5 and the signer or verifier doesn't scrutinize the input carefully enough to note its construction.

A technical description of the underlying attack method can be found here:

as referenced from:

[1] "The birthday paradox is a standard statistics problem. How many people must be in a room for the chance to be greater than even that one of them shares your birthday? The answer is 253. Now, how many people must there be for the chance to be greater than even that at least two of them will share the same birthday? The answer is surprisingly low: 23. With only 23 people in the room, there are still 253 different pairs of people in the room." -- Bruce Schneier, Applied Cryptography, p. 166.