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 that can then be used to encrypt subsequent communications using a symmetric key cipher. 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.

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}$ ,
$\mathrm {T}$ , 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 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) $(m_{A},\mathrm {B} _{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 of conjugates and inverses chosen from the keyset parameters (A for Alice and B for Bob, where (for Alice) $\mathrm {B} _{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})*\mathrm {B} _{a}$ and Bob computes $(S_{ba},\sigma _{ba})=(m_{B}Pub_{A},\sigma _{a})*\mathrm {B} _{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 $\mathrm {T}$ .

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] 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.^[4]

In 2016, Simon R. Blackburn and Matthew J. 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 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]

Notes

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

References

^ Anshel, I.; Anshel, M.; Goldfeld, D.; Lemieux, S. (2006). "Key Agreement, The Algebraic Eraser and Lightweight Cryptography" (PDF). Algebraic methods in cryptography. Vol. 418. Contemp. Math.: American Mathematical Society. pp. 1–34. ISBN 978-0-8218-4037-5.
^ Goodin, Dan (17 November 2015). "Why Algebraic Eraser may be the riskiest cryptosystem you've never heard of". Ars Technica.
^ 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.
^ ^a ^b Gunnells, P.E. (2011). "On the Cryptanalysis of the Generalized Simultaneous Conjugacy Search Problem and the Security of the Algebraic Eraser". arXiv:1105.1141 [cs.CR].
^ Dehornoy, Patrick (2004). "Braid-based cryptography". Group theory, statistics, and cryptography. Contemporary Mathematics. Vol. 360. American Mathematical Society. pp. 5–33. CiteSeerX 10.1.1.10.1759. doi:10.1090/conm/360/06566. ISBN 9780821834442. MR 2105432.
^ Kalka A, Teicher M, Tsaban B (2012). "Short Expressions of Permutations as Products and Cryptanalysis of the Algebraic Eraser". Advances in Applied Mathematics. 49 (1): 57–76. arXiv:0804.0629. Bibcode:2008arXiv0804.0629K. doi:10.1016/j.aam.2012.03.001. S2CID 10040122.
^ Goldfield, D.; Gunnels, P.E. (2012). "Defeating the Kalka-Teicher-Tsaban Linear Algebra Attack on the Algebraic Eraser". arXiv:1202.0598 [cs.CR].
^ Ben-Zvi, A, Blackburn, Simon R, Tsaban B (2016). "A Practical Cryptanalysis of the Algebraic Eraser". Advances in Cryptology – CRYPTO 2016. Lecture Notes in Computer Science. Vol. 9814. Springer. pp. 179–189. arXiv:1511.03870. CiteSeerX 10.1.1.738.4755. doi:10.1007/978-3-662-53018-4_7. ISBN 978-3-662-53018-4. S2CID 1277023.
^ Anshel, I.; Atkins, D.; Goldfeld, D.; Gunnels, P.E. (2016). "Defeating the Ben-Zvi, Blackburn, and Tsaban Attack on the Algebraic Eraser". arXiv:1601.04780 [cs.CR].
^ Myasnikov AD, Ushakov A (2008). "Cryptanalysis of Anshel-Anshel-Goldfeld-Lemieux key agreement protocol". arXiv:0801.4786 [math.GR].
^ Blackburn, Simon R.; Robshaw, M.J.B. (2016). "On the Security of the Algebraic Eraser Tag Authentication Protocol" (PDF). Applied Cryptography and Network Security. Lecture Notes in Computer Science. Vol. 9696. pp. 3–17. arXiv:1602.00860. doi:10.1007/978-3-319-39555-5_1. ISBN 978-3-319-39554-8. S2CID 371335.
^ Derek Atkins; Dorian Goldfeld (2016-02-25). "Addressing the Algebraic Eraser Diffie–Hellman Over-the-Air Protocol". Cryptology ePrint Archive. IACR.

External links

SecureRF home page

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

[2] Anshel, I.; Anshel, M.; Goldfeld, D.; Lemieux, S. (2006). "Key Agreement, The Algebraic Eraser and Lightweight Cryptography" (PDF). Algebraic methods in cryptography. Vol. 418. Contemp. Math.: American Mathematical Society. pp. 1–34. ISBN 978-0-8218-4037-5.

[arstechnica-3] Goodin, Dan (17 November 2015). "Why Algebraic Eraser may be the riskiest cryptosystem you've never heard of". Ars Technica.

[4] 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.

[gscsp-5] Gunnells, P.E. (2011). "On the Cryptanalysis of the Generalized Simultaneous Conjugacy Search Problem and the Security of the Algebraic Eraser". arXiv:1105.1141 [cs.CR].

[6] Dehornoy, Patrick (2004). "Braid-based cryptography". Group theory, statistics, and cryptography. Contemporary Mathematics. Vol. 360. American Mathematical Society. pp. 5–33. CiteSeerX 10.1.1.10.1759. doi:10.1090/conm/360/06566. ISBN 9780821834442. MR 2105432.

[7] Kalka A, Teicher M, Tsaban B (2012). "Short Expressions of Permutations as Products and Cryptanalysis of the Algebraic Eraser". Advances in Applied Mathematics. 49 (1): 57–76. arXiv:0804.0629. Bibcode:2008arXiv0804.0629K. doi:10.1016/j.aam.2012.03.001. S2CID 10040122.

[8] Goldfield, D.; Gunnels, P.E. (2012). "Defeating the Kalka-Teicher-Tsaban Linear Algebra Attack on the Algebraic Eraser". arXiv:1202.0598 [cs.CR].

[9] Ben-Zvi, A, Blackburn, Simon R, Tsaban B (2016). "A Practical Cryptanalysis of the Algebraic Eraser". Advances in Cryptology – CRYPTO 2016. Lecture Notes in Computer Science. Vol. 9814. Springer. pp. 179–189. arXiv:1511.03870. CiteSeerX 10.1.1.738.4755. doi:10.1007/978-3-662-53018-4_7. ISBN 978-3-662-53018-4. S2CID 1277023.

[10] Anshel, I.; Atkins, D.; Goldfeld, D.; Gunnels, P.E. (2016). "Defeating the Ben-Zvi, Blackburn, and Tsaban Attack on the Algebraic Eraser". arXiv:1601.04780 [cs.CR].

[11] Myasnikov AD, Ushakov A (2008). "Cryptanalysis of Anshel-Anshel-Goldfeld-Lemieux key agreement protocol". arXiv:0801.4786 [math.GR].

[12] Blackburn, Simon R.; Robshaw, M.J.B. (2016). "On the Security of the Algebraic Eraser Tag Authentication Protocol" (PDF). Applied Cryptography and Network Security. Lecture Notes in Computer Science. Vol. 9696. pp. 3–17. arXiv:1602.00860. doi:10.1007/978-3-319-39555-5_1. ISBN 978-3-319-39554-8. S2CID 371335.

[13] Derek Atkins; Dorian Goldfeld (2016-02-25). "Addressing the Algebraic Eraser Diffie–Hellman Over-the-Air Protocol". Cryptology ePrint Archive. IACR.

[note 1]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]