A practical cryptanalysis of the Algebraic Eraser

DOI10.1007/978-3-662-53018-4_7zbMATH Open1351.94025arXiv1511.03870OpenAlexW2254391108MaRDI QIDQ2835587FDOQ2835587

Authors: Adi Ben-Zvi, Simon R. Blackburn, Boaz Tsaban 

Publication date: 30 November 2016

Published in: Advances in Cryptology – CRYPTO 2016 (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1511.03870

Recommendations

• Key agreement, the Algebraic Eraser\(^{\text{TM}}\) and lightweight cryptography
• Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux Key Agreement Protocol
• Short expressions of permutations as products and cryptanalysis of the algebraic eraser
• A class of hash functions based on the Algebraic Eraser\(^{\text{TM}}\)
• A practical cryptanalysis of \({\mathrm {walnutdsa}^{\mathrm {TM}}}\)

Mathematics Subject Classification ID

Cryptography (94A60)

Cites Work

• The Magma algebra system. I: The user language
• A method for obtaining digital signatures and public-key cryptosystems
• Key agreement, the Algebraic Eraser\(^{\text{TM}}\) and lightweight cryptography
• Braid Groups
• Cryptanalysis via algebraic spans
• Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography
• Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux Key Agreement Protocol
• Short expressions of permutations as products and cryptanalysis of the algebraic eraser

Cited In (7)

• Optimizing Guessing Strategies for Algebraic Cryptanalysis with Applications to EPCBC
• Short expressions of permutations as products and cryptanalysis of the algebraic eraser
• A practical cryptanalysis of \({\mathrm {walnutdsa}^{\mathrm {TM}}}\)
• Ironwood meta key agreement and authentication protocol
• Key agreement, the Algebraic Eraser\(^{\text{TM}}\) and lightweight cryptography
• Practical Algebraic Cryptanalysis for Dragon-Based Cryptosystems
• Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux Key Agreement Protocol

Uses Software

• Magma

This page was built for publication: A practical cryptanalysis of the Algebraic Eraser

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835587)