A Practical Cryptanalysis of the Algebraic Eraser

Adi Ben-Zvi; Simon Blackburn; Boaz Tsaban

doi:10.1007/978-3-662-53018-4_7

A Practical Cryptanalysis of the Algebraic Eraser

Adi Ben-Zvi, Simon Blackburn, Boaz Tsaban

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

66 Downloads (Pure)

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 language	English
Title of host publication	Advances in Cryptology - CRYPTO 2016
Subtitle of host publication	36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I
Editors	Matthew Robshaw, Jonathan Katz
Publisher	Springer
Pages	179-189
Number of pages	11
ISBN (Electronic)	978-3-662-53018-4
ISBN (Print)	978-3-662-53017-7
DOIs	https://doi.org/10.1007/978-3-662-53018-4_7
Publication status	E-pub ahead of print - 21 Jul 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	9814
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-662-53018-4_7

Accepted ManuscriptAccepted author manuscript, 251 KB

http://link.springer.com/chapter/10.1007%2F978-3-662-53018-4_7

Cite this

Ben-Zvi, A., Blackburn, S., & Tsaban, B. (2016). A Practical Cryptanalysis of the Algebraic Eraser. In M. Robshaw, & J. Katz (Eds.), Advances in Cryptology - CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I (pp. 179-189). (Lecture Notes in Computer Science; Vol. 9814). Springer. Advance online publication. https://doi.org/10.1007/978-3-662-53018-4_7

@inproceedings{de970d83cd724d1f8e55f25256643dd7,

title = "A Practical Cryptanalysis of the Algebraic Eraser",

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.",

author = "Adi Ben-Zvi and Simon Blackburn and Boaz Tsaban",

year = "2016",

month = jul,

day = "21",

doi = "10.1007/978-3-662-53018-4_7",

language = "English",

isbn = "978-3-662-53017-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "179--189",

editor = "Matthew Robshaw and Jonathan Katz",

booktitle = "Advances in Cryptology - CRYPTO 2016",

}

Ben-Zvi, A, Blackburn, S & Tsaban, B 2016, A Practical Cryptanalysis of the Algebraic Eraser. in M Robshaw & J Katz (eds), Advances in Cryptology - CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9814, Springer, pp. 179-189. https://doi.org/10.1007/978-3-662-53018-4_7

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 proceeding › Conference contribution

TY - GEN

T1 - A Practical Cryptanalysis of the Algebraic Eraser

AU - Ben-Zvi, Adi

AU - Blackburn, Simon

AU - Tsaban, Boaz

PY - 2016/7/21

Y1 - 2016/7/21

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-662-53018-4_7

DO - 10.1007/978-3-662-53018-4_7

M3 - Conference contribution

SN - 978-3-662-53017-7

T3 - Lecture Notes in Computer Science

SP - 179

EP - 189

BT - Advances in Cryptology - CRYPTO 2016

A2 - Robshaw, Matthew

A2 - Katz, Jonathan

PB - Springer

ER -

Ben-Zvi A, Blackburn S, Tsaban B. A Practical Cryptanalysis of the Algebraic Eraser. In Robshaw M, Katz J, editors, Advances in Cryptology - CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I. Springer. 2016. p. 179-189. (Lecture Notes in Computer Science). Epub 2016 Jul 21. doi: 10.1007/978-3-662-53018-4_7