A Practical Cryptanalysis of the Algebraic Eraser. / Ben-Zvi, Adi; Blackburn, Simon; Tsaban, Boaz.

Advances in Cryptology - CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I. ed. / Matthew Robshaw; Jonathan Katz. Springer, 2016. p. 179-189 (Lecture Notes in Computer Science; Vol. 9814).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

E-pub ahead of print

Documents

Links

Abstract

We present a novel cryptanalysis of the Algebraic Eraser primitive. This key agreement scheme, based on techniques from permutation groups, matrix groups and braid groups, is proposed as an underlying technology for ISO/IEC 29167-20, which is intended for authentication of RFID tags. SecureRF, the company owning the trademark Algebraic Eraser, markets it as suitable in general for lightweight environments such as RFID tags and other IoT applications. Our attack is practical on standard hardware: for parameter sizes corresponding to claimed 128-bit security, our implementation recovers the shared key using less than 8 CPU hours, and less than 64MB of memory.
Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2016
Subtitle of host publication36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I
EditorsMatthew Robshaw, Jonathan Katz
PublisherSpringer
Pages179-189
Number of pages11
ISBN (Electronic)978-3-662-53018-4
ISBN (Print)978-3-662-53017-7
DOIs
Publication statusE-pub ahead of print - 21 Jul 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume9814
ISSN (Print)0302-9743
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 26504089