Cryptology ePrint Archive: Report 2015/1102
A Practical Cryptanalysis of the Algebraic Eraser
Adi Ben-Zvi and 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.
Category / Keywords: public-key cryptography / Cryptanalysis, group-theoretic cryptography
Original Publication (with minor differences): IACR-CRYPTO-2016
Date: received 12 Nov 2015, last revised 2 Jun 2016
Contact author: s blackburn at rhul ac uk
Available format(s): PDF | BibTeX Citation
Note: Final author version. Accepted for CRYPTO 2016
Version: 20160602:135413 (All versions of this report)
Short URL: ia.cr/2015/1102
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]