Algebraic Eraser

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.^[1] This shared secret may be directly used as a key, or to derive another key which can then be used to encrypt subsequent communications using a symmetric key cipher. Algebraic Eraser was developed by Iris Anshell, Michael Anshell, Dorian Goldfeld and Stephane Lemieux. SecureRF owns patents covering the protocol^[2] and is attempting to standardize the protocol as part of ISO/IEC 29167-20,^[3] a standard for securing radio-frequency identification devices and wireless sensor networks.

Keyset parameters

Before two parties can establish a key they must first agree on a set of parameters, called the keyset parameters. These parameters comprise:

• $N$, the number of strands in the braid,
• $q$, the size of the finite field $\mathbb{F}_q$,
• $M_*$, the initial NxN seed matrix in $\mathbb{F}_q$,
• $\Tau$, a set of $N$ elements in the finite field $\mathbb{F}_q$ (also called the T-values), and
• $A,B$ a set of conjugates in the braid group designed to commute with each other.

E-multiplication

The fundamental operation of the Algebraic Eraser is a one-way function called E-multiplication. Given a matrix, permutation, an Artin generator $\beta$ in the braid group, and T-values, one applies E-multiplication by converting the generator to a colored Burau matrix and braid permutation, $(CB(\beta),\sigma_\beta)$, applying the permutation and T-values, and then multiplying the matrices and permutations. The output of E-multiplication is itself a matrix and permutation pair: $(M',\sigma') = (M,\sigma_0)*(CB(\beta),\sigma_\beta)$.

Key establishment protocol

The following example will illustrate how a key establishment is made. Suppose Alice wants to establish a shared key with Bob, but the only channel available for them 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) $(m_A,\Beta_a)$ where $m_A$ is a randomly selected polynomial of the seed matrix $m_A = \sum_{i=0}^{N-1}{a_i M_*^i}$ and a braid which is a randomly selected set conjugates and inverses chosen from the keyset parameters (A for Alice and B for Bob, where (for Alice) $\Beta_a = \prod_{i=1}^{k}A_i^{\pm 1}$).

From their private key material Alice and Bob each compute their public key $(Pub_A,\sigma_a)$ and $(Pub_B,\sigma_b)$ where e.g. $(Pub_A,\sigma_a) = (m_A,id) * b_a$, that is, the result of E-Multiplication of the private matrix and identity-permutation with the private braid.

Each party must know the other party's public key prior to execution of the protocol.

To compute the shared secret, Alice computes $(S_{ab},\sigma_{ab}) = (m_A Pub_B,\sigma_b) * \Beta_a$ and Bob computes $(S_{ba},\sigma{ba}) = (m_B Pub_A,\sigma_a) * \Beta_b$. The shared secret is the matrix/permutation pair $(S_{ab},\sigma_{ab})$ which equals $(S_{ba},\sigma_{ba})$. The shared secrets are equal because the conjugate sets $A$ and $B$ are chosen to commute and both Alice and Bob use the same seed matrix $M_*$ and T-values $\Tau$.

The only information about her private key that Alice initially exposes is her public key. 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. No party other than Alice or Bob can compute the shared secret, unless that party can solve the Diffie–Hellman problem.

The public keys are either static (and trusted, say via a certificate) or ephemeral. Ephemeral keys are temporary and not necessarily authenticated, so if authentication is desired, authenticity assurances must be obtained by other means. 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. Holders of static private keys should validate the other public key, and should apply a secure key derivation function to the raw Diffie–Hellman shared secret to avoid leaking information about the static private key.

Security

The security of AE is based on the Generalized Simultaneous Conjugacy Search Problem (GSCSP)^[4] within the braid group. This is a distinct and different hard problem than the Conjugacy Search Problem (CSP) which has been the central hard problem in what is called braid group cryptography.^[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.

Known attacks

The first attack by Kalka, Teicher and Tsaban shows a class of weak-keys when $M_*$ or $m_A$ are chosen randomly.^[6] The authors of Algebraic Eraser followed up with a preprint on how to choose parameters that aren't prone to the attack.^[7] In a preprint, Ben-Zvi, Blackurn, and Tsaban improved the first attack into one which 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 Gunnels, by showing that properly sized conjugator braids cannot be separated.^[4]

In February 2016, Simon R. Blackburn and Matthew J. B. Robshaw published a preprint containing a range of practical attacks against the draft (from January 2016) 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 2⁴⁹ time and 2⁴⁸ memory.^[11] Atkins and Goldfeld responded that adding a hash or message authentication code to the draft protocol defeats these attacks.^[12]

See also

• Anshel–Anshel–Goldfeld key exchange
• Group-based cryptography
• Non-commutative cryptography

Notes

1. Also referred to as the colored Burau key agreement protocol (CBKAP), Anshell–Anshell–Goldfeld–Lemieux key agreement protocol, Algebraic Eraser key agreement protocol (AEKAP), and Algebraic Eraser Diffie–Hellman (AEDH).

References

1. Anshel I, Anshel M, Goldfeld D, Lemieux S. Key Agreement, The Algebraic Eraser and Lightweight Cryptography Algebraic methods in cryptography, Contemp. Math., vol. 418, Amer. Math. Soc., Providence, RI, 2006, pp. 1–34.
2. Dan Goodin (17 November 2015). "Why Algebraic Eraser may be the riskiest cryptosystem you’ve never heard of". Ars Technica.
3. ISO/IEC AWI 29167-20 – Information technology – Automatic identification and data capture techniques – Part 20: Crypto suite Algebraic Eraser security services for air interface communications. Working Draft.
4. Gunnells PE. On the Cryptanalysis of the Generalized Simultaneous Conjugacy Search Problem and the Security of the Algebraic Eraser. 2011
5. Dehornoy P. (2004). "Braid-based cryptography" (PDF). Contemporary Mathematics (360): 5–33.
6. Kalka A, Teicher M, Tsaban B. (2008). "Short Expressions of Permutations as Products and Cryptanalysis of the Algebraic Eraser". Advances in Applied Mathematics 49 (1): 57–76.
7. Goldfield D, Gunnels PE. Defeating the Kalka-Teicher-Tsaban Linear Algebra Attack on the Algebraic Eraser, 2012
8. Ben-Zvi, A, Blackurn, Simon R, Tsaban B. (arXiv:1511.03870 [math.GR]) A Practical Cryptanalysis of the Algebraic Eraser, 2015
9. Anshel I, Atkins D, Goldfeld D,Gunnels PE. (arXiv:1601.04780 [cs.CR]) Defeating the Ben-Zvi, Blackburn, and Tsaban Attack on the Algebraic Eraser, 2016
10. Myasnikov AD, Ushakov A. Cryptanalysis of Anshel-Anshel-Goldfeld-Lemieux key agreement protocol, 2008
11. Simon R. Blackburn, M.J.B. Robshaw (2016-02-02). "On the Security of the Algebraic Eraser Tag Authentication Protocol" (PDF).
12. Derek Atkins, Dorian Goldfeld (2016-02-25). "Addressing the Algebraic Eraser Diffie--Hellman Over-the-Air Protocol".

External links

• SecureRF home page