Algebraic Eraser™ is a relatively new asymmetric key agreement protocol (also designated the Colored Burau Key Agreement Protocol), based on a simultaneous conjugacy search problem in a braid group.
An initial exposition is: Iris Anshel, Michael Anshel, Dorian Goldfeld, Stephane Lemieux, Key agreement, the Algebraic Eraser™, and lightweight cryptography, in Contemporary Mathematics 418 (2006) (free slightly later pdf). There has been two early, concurrent attacks:
- Arkadius Kalka, Mina Teicher, Boaz Tsaban, Short expressions of permutations as products and cryptanalysis of the Algebraic Eraser, in Advances in Applied Mathematics Volume 49, Issue 1 (July 2012); free possibly earlier pdf at arXiv:0804.0629 (April 2008 - March 2012; first presented by Kalka and Tsaban in Bar-Ilan University's CGC Seminar on January 13, 2008).
This was answered by a different proposed method for choosing a certain fixed matrix: Dorian Goldfeld, Paul E. Gunnells, Defeating the Kalka-Teicher-Tsaban linear algebra attack on the Algebraic Eraser, in arXiv:1202.0598 (February 2012).
- Alex D. Myasnikov, Alexander Ushakov, Cryptanalysis of Anshel-Anshel-Goldfeld-Lemieux key agreement protocol, in Groups-Complexity-Cryptology Volume 1 No. 1 (2009), pre-published as arXiv:0801.4786 (January 30, 2008).
A rebuttal of that attack is: Paul E. Gunnells, On the cryptanalysis of the generalized simultaneous conjugacy search problem and the security of the Algebraic Eraser, in arXiv:1105.1141 (May 2011).
Here's a recent introductory paper: Derek Atkins, Algebraic Eraser™: A lightweight, efficient asymmetric key agreement protocol for use in no-power, low-power, and IoT devices, accepted paper at Lightweight Cryptography Workshop 2015, with presentation by Paul E. Gunnells.
Algebraic Eraser™ has been proposed for standardization as ISO/IEC 29167-20 (currently an Approved Work Item). The company apparently petitioning for standardization and holding some related patents made available a description worded as a standard proposal (October 2015), and several other technical papers.
There is a recent claimed attack, improving on the Kalka-Teicher-Tsaban attack: Adi Ben-Zvi, Simon R. Blackburn, Boaz Tsaban, A Practical Cryptanalysis of the Algebraic Eraser, in arXiv:1511.03870 and eprint (November 12, 2015); and some controversy about it, according to this Ars Technica article. The aforementioned company made a preliminary analysis of the attack. They acknowledge that it applies to one of two profiles proposed for standardization, and recovers the shared secret key (but not the private key; hence my understanding is that the attack "only" compromises the confidentiality of past recorded sessions, or the integrity of the current session if it can be frozen long enough to carry the attack).
Disclaimer: I have not studied the above references in much depth.
I'm asking the status of the cryptosystem. In particular:
- What was the claimed security level of the 5 challenges (with $q = 256$ and $n = 16$) solved in the recent attack?
- Would the attack work for the B10F256 Keyset Parameters in normative Annex C.1 in the October 2015 description ? It supposedly
provides a security level of 280 using a braid with 10 strands and a field of 256 (28)
- Is the method by which these Keyset Parameters where generated public? They seem to include the matrix $m\in GL(n,\mathbb F)$ which careful choice was acknowledged critical to defeat the Kalka-Teicher-Tsaban attack, and I read in section 7 of the Atkins introductory paper these are [emphasis mine]
chosen via a proprietary method
- How can it be that only the second profile is affected, given that according to the description on section 2, it differs from the other only by having the public key obtained as part of a certificate? [emphasis mine]
Profile [ii] (Certificate on Tag):
The Interrogator begins by obtaining the Tag’s certificate (CERT_t). The Tag sends its certificate, which contains its public key (PUB_t), to the Interrogator. The Interrogator obtains PUB_t from CERT_t. The protocol then follows Profile [i]. This protocol allows for tracking the Tag via the Tag’s fixed CERT_t.
- Are there significant differences between the October 2015 description and what was proposed for standardization, in 2014?