Algebraic Eraser (AE)[note 1] is an anonymous key agreement protocol that allows two parties, each having an AE public–private key pair, to establish a shared secret over an insecure channel.
Algebraic Eraser was developed by Iris Anshel, Michael Anshel, Dorian Goldfeld and Stephane Lemieux.
SecureRF owns patents covering the protocol[2] and unsuccessfully attempted (as of July 2019) to standardize the protocol as part of ISO/IEC 29167-20,[3] a standard for securing radio-frequency identification devices and wireless sensor networks.
These parameters comprise: The fundamental operation of the Algebraic Eraser is a one-way function called E-multiplication.
in the braid group, and T-values, one applies E-multiplication by converting the generator to a colored Burau matrix and braid permutation,
The output of E-multiplication is itself a matrix and permutation pair:
The following example illustrates how to make a key establishment.
Suppose Alice wants to establish a shared key with Bob, but the only channel available may be eavesdropped by a third party.
Initially, Alice and Bob must agree on the keyset parameters they will use.
Each party must have a key pair derived from the keyset, consisting of a private key (e.g., in the case of Alice)
is a randomly selected polynomial of the seed matrix
and a braid, which is a randomly selected set of conjugates and inverses chosen from the keyset parameters (A for Alice and B for Bob, where (for Alice)
The shared secrets are equal because the conjugate sets
are chosen to commute and both Alice and Bob use the same seed matrix
So, no party other than Alice can determine Alice's private key, unless that party can solve the Braid Group Simultaneous Conjugacy Separation Search problem.
Bob's private key is similarly secure.
The public keys are either static (and trusted, say via a certificate) or ephemeral.
Authentication is necessary to avoid man-in-the-middle attacks.
If one of Alice or Bob's public key is static then man-in-the-middle attacks are thwarted.
Static public keys provide neither forward secrecy nor key-compromise impersonation resilience, among other advanced security properties.
The security of AE is based on the Generalized Simultaneous Conjugacy Search Problem (GSCSP)[4] within the braid group.
[5] Even if CSP is uniformly broken (which has not been done to date), it is not known how this would facilitate a break of GSCSP.
The first attack by Kalka, Teicher and Tsaban shows a class of weak-keys when
[6] The authors of Algebraic Eraser followed up with a preprint on how to choose parameters that aren't prone to the attack.
[7] Ben-Zvi, Blackburn, and Tsaban improved the first attack into one the authors claim can break the publicized security parameters (claimed to provide 128-bit security) using less than 8 CPU hours, and less than 64MB of memory.
[8] Anshel, Atkins and Goldfeld responded to this attack in January 2016.
[9] A second attack by Myasnikov and Ushakov, published as a preprint, shows that conjugates chosen with a too-short conjugator braid can be separated, breaking the system.
[10] This attack was refuted by Gunnells, by showing that properly sized conjugator braids cannot be separated.
B. Robshaw published a range of practical attacks against the January 2016 draft of the ISO/IEC 29167-20 over-the-air protocol, including impersonation of a target tag with negligible amount of time and memory and full private key recovery requiring 249 time and 248 memory.
[11] Atkins and Goldfeld responded that adding a hash or message authentication code to the draft protocol defeats these attacks.