Paper 2016/091

On the Security of the Algebraic Eraser Tag Authentication Protocol

Simon R. Blackburn and M. J. B. Robshaw

Abstract

The Algebraic Eraser has been gaining prominence as SecureRF, the company commercializing the algorithm, increases its marketing reach. The scheme is claimed to be well-suited to IoT applications but a lack of detail in available documentation has hampered peer-review. Recently more details of the system have emerged after a tag authentication protocol built using the Algebraic Eraser was proposed for standardization in ISO/IEC SC31 and SecureRF provided an open public description of the protocol. In this paper we describe a range of attacks on this protocol that include very efficient and practical tag impersonation as well as partial, and total, tag secret key recovery. Most of these results have been practically verified, they contrast with the 80-bit security that is claimed for the protocol, and they emphasize the importance of independent public review for any cryptographic proposal.

Note: Final author version. Accepted for ACNS

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ACNS 2016
Keywords
Algebraic Erasercryptanalysistag authenticationIoT
Contact author(s)
s blackburn @ rhul ac uk
History
2016-06-02: revised
2016-02-02: received
See all versions
Short URL
https://ia.cr/2016/091
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/091,
      author = {Simon R.  Blackburn and M. J. B.  Robshaw},
      title = {On the Security of the Algebraic Eraser Tag Authentication Protocol},
      howpublished = {Cryptology ePrint Archive, Paper 2016/091},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/091}},
      url = {https://eprint.iacr.org/2016/091}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.