Chaum's protocol for detecting man-in-the-middle: Explanation, demonstration, and timing studies for a text-messaging scenario

ABSTRACT

This article explains, demonstrates, and evaluates Chaum’s protocol for detecting a man-in-the-middle (MitM) of text-messaging network communications. MitM attacks pose serious risks to many network communications. Networks often mitigate these risks with robust protocols, such as TLS, which assume some type of public-key infrastructure that provides a mechanism for the authenticated exchange of public keys. By contrast, Chaum’s protocol aims to detect a MitM with minimal assumptions and technology, and in particular without assuming the authenticated exchange of public keys. Chaum assumes that the eavesdropper can “sound like” the communicants but that the eavesdropper cannot fabricate sensible conversations.

Using an encryption function and one-way function, Chaum’s protocol works in three phases. In Phase I, the communicants exchange their public keys. In Phase II, each communicant generates a random string. The first communicant cryptographically commits to that string, and sends the string to the other communicant after receiving the other’s string. In Phase III, using any of four different “scenarios” the communicants verify that each possesses the same two strings. The protocol forces any MitM to cause the communicants to possess different pairs of strings. The text-messaging scenario is similar to a forced-latency protocol proposed by Wilcox-O’Hearn in 2003.

This article implements and experimentally demonstrates the effectiveness of the third scenario, which uses timing to detect a MitM in text-messaging. Even assuming a MitM can send messages without any network latency, the protocol forces the MitM to cause delays noticeable by the communicants. This article is the first to explain, demonstrate, and evaluate Chaum’s protocol, which Chaum described only in an abandoned and nearly inscrutable patent application.

KEYWORDS:

• Chaum’s man-in-the-middle protocol
• cryptanalysis
• forced latency
• Interlock protocol
• key establishment
• man-in-the-middle (MitM)
• network security protocols
• U.S. Patent Application 2006/0218636 A1
• Zfone protocol

About the authors

Alan T. Sherman is a professor of computer science at the University of Maryland, Baltimore County (UMBC) in the CSEE Department and Director of UMBC’s Center for Information Security and Assurance. His main research interest is high-integrity voting systems. He has carried out research in election systems, algorithm design, cryptanalysis, theoretical foundations for cryptography, applications of cryptography, cloud forensics, and cybersecurity education. Dr. Sherman is also a private consultant performing security analyses. Sherman earned the PhD degree in computer science at MIT in 1987 studying under Ronald L. Rivest (see www.csee.umbc.edu/∼sherman).

John Seymour is a PhD student of computer science at the University of Maryland, Baltimore County (UMBC) where he performs research at the intersection of machine learning and information security under the supervision of Dr. Charles Nicholas. His tentative PhD dissertation topic is quantifying value in open source malware datasets. In 2014, he completed his master’s thesis, titled, “Quantum Classification of Malware,” which was later presented at DEFCON 23. He currently performs machine learning research, quantum computing research, and work on the DARPA STAC project at CyberPoint International, LLC, located in Baltimore.

Akshayraj Kore works as an Android programmer for the startup Apio Systems in Virginia. He is a member of the lead Android team which builds situational awareness apps for driver safety and driver behavior improvement. Raj is also an International Grandmaster, playing for UMBC’s chess team for two years while pursuing his master’s in Computer Science at UMBC. His main research interests are cryptography, programming languages, and algorithms.

William Newton is a software development project manager at Booz Allen Hamilton. He received his bachelor’s in 2004 and master’s in 2010 from the University of Maryland, Baltimore County (UMBC). His main research interests are wireless security and related vulnerabilities, unique steganography techniques, and detecting and analyzing man-in-the-middle attacks.

Acknowledgments

We thank David Chaum and Zooko Wilcox-O’Hearn for fruitful discussions. Thanks also to Jonathan Katz, Neal McBurnett, and members of the UMBC Cyber Defense Lab (including Edward Birrane, Josiah Dykstra, Russ Fink, Christopher Vatcher, Michael Oehler, and Ed Zieglar) for useful feedback. William E. Byrd helped guide Kore’s software implementation.

Notes

¹Gilles Brassard, Ueli Maurer, Rafail Ostrovsky, Ronald Rivest, Victor Shoup, Zooko Wilcox-O’Hearn, and Moti Yung.

²Private communications with David Chaum.

³https://hackage.haskell.org/package/cpsa

⁴maude.cs.uiuc.edu/tools/Maude-NPA/

⁵http://www.cs.ox.ac.uk/people/cas.cremers/scyther/

⁶Private communications with Zooko Wilcox-O’Hearn.

⁷Private communications with Ed Zieglar.

⁸Private communications with David Chaum.

⁹Ibid.

¹⁰Ibid.