Paper 2016/205

Addressing the Algebraic Eraser Diffie--Hellman Over-the-Air Protocol

Derek Atkins and Dorian Goldfeld

Abstract

The Algebraic Eraser Diffie-Hellman (AEDH) protocol, first introduced in 2005 as a key agreement and authentication protocol, has been proposed as a standard in ISO JTC-1/SC-31 (29167-20) to protect various communication protocols like RFID, NFC, or Bluetooth for devices associated with ISO-18000 and the Internet of Things. A recent paper by M.J.B. Robshaw and Simon R Blackburn claims to recover sufficient data to impersonate a device or, with a bit more work, recover the private keys of a device if an attacker uses the draft 29167-20 protocol and gains direct access to the resulting shared secret computation. This paper shows that simply adding a Hash or a Message Authentication Code (MAC) to the proposed authentication protocol overcomes the purported attacks. These simple standard enhancements thwart all of these attacks; that is, attacks of this nature fail. As the 29167-20 draft is currently a work item under active development within the ISO process, all these attacks would normally have been addressed in the working group, and no AEDH protocol in the public domain currently transmits the computed shared secret. Therefore, contrary to the conclusion of Robshaw and Blackburn, a simple addition to the draft protocol, similar in nature to protections in other protocols like TLS, makes the AEDH protocol perfectly suitable for authentication of passive tags and other low-power, constrained devices.