A Practical Cryptanalysis of the Algebraic Eraser

Adi Ben-Zvi, Simon R. Blackburn, and Boaz Tsaban

Abstract

Anshel, Anshel, Goldfeld and Lemieaux introduced the Colored Burau Key Agreement Protocol (CBKAP) as the concrete instantiation of their Algebraic Eraser scheme. This scheme, based on techniques from permutation groups, matrix groups and braid groups, is designed for lightweight environments such as RFID tags and other IoT applications. It is proposed as an underlying technology for ISO/IEC~29167-20. SecureRF, the company owning the trademark Algebraic Eraser, has presented the scheme to the IRTF with a view towards standardisation. We present a novel cryptanalysis of this scheme. 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.

Note: Final author version. Accepted for CRYPTO 2016

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2016
Keywords
Cryptanalysisgroup-theoretic cryptography
Contact author(s)
s blackburn @ rhul ac uk
History
2016-06-02: revised
See all versions
Short URL
https://ia.cr/2015/1102

CC BY

BibTeX

@misc{cryptoeprint:2015/1102,
author = {Adi Ben-Zvi and Simon R.  Blackburn and Boaz Tsaban},
title = {A Practical Cryptanalysis of the Algebraic Eraser},
howpublished = {Cryptology ePrint Archive, Paper 2015/1102},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/1102}},
url = {https://eprint.iacr.org/2015/1102}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.