American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020073

Ironwood meta key agreement and authentication protocol

Iris Anshel , Derek Atkins , Dorian Goldfeld and  Paul E. Gunnells

100 Beard Sawmill Rd, Suite 350, Shelton, CT 06484, USA

Received  September 2019 Published  April 2020

Number theoretic public-key solutions, currently used in many applications worldwide, will be subject to various quantum attacks, making them less attractive for longer-term use. Certain group theoretic constructs are now showing promise in providing quantum-resistant cryptographic primitives, and may provide suitable alternatives for those looking to address known quantum attacks. In this paper, we introduce a new protocol called a Meta Key Agreement and Authentication Protocol (MKAAP) that has some characteristics of a public-key solution and some of a shared-key solution. Specifically, it has the deployment benefits of a public-key system, allowing two entities that have never met before to authenticate without requiring real-time access to a third-party, but does require secure provisioning of key material from a trusted key distribution system (similar to a symmetric system) prior to deployment. We then describe a specific MKAAP instance, the Ironwood MKAAP, discuss its security, and show how it resists certain quantum attacks such as Shor's algorithm or Grover's quantum search algorithm. We also show Ironwood implemented on several "internet of things" (IoT devices), measure its performance, and show how it performs significantly better than ECC using fewer device resources.

Keywords: Public-key cryptography, braids, Diffie-Hellman, post-quantum cryptography, internet of things, IoT.
Mathematics Subject Classification: Primary: 94A60, 20F36, 68P25; Secondary: 81P94, 20G40, 20E36.
Citation: Iris Anshel, Derek Atkins, Dorian Goldfeld, Paul E. Gunnells. Ironwood meta key agreement and authentication protocol. Advances in Mathematics of Communications, doi: 10.3934/amc.2020073
References:
[1]

I. Anshel, M. Anshel, D. Goldfeld and S. Lemieux, Key agreement, the Algebraic Eraser$^{TM}$, and lightweight cryptography, Algebraic Methods in Cryptography, Contemp. Math., Amer. Math. Soc., Providence, RI, 418 (2006), 1-34.  doi: 10.1090/conm/418/07943.  Google Scholar

[2]

I. Anshel, D. Atkins, D. Goldfeld and P. E. Gunnells, Defeating the Ben-Zvi, Blackburn, and Tsaban Attack on the Algebraic Eraser, arXiv: 1601.04780v1 [cs.CR]. Google Scholar

[3]

I. Anshel, D. Atkins, D. Goldfeld and P. E. Gunnells, WalnutDSA$^{TM}$: A Lightweight Quantum Resistant Digital Signature Algorithm, https://eprint.iacr.org/2017/058.pdf. Google Scholar

[4]

I. Anshel, M. Anshel and D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett., 6 (1999), 287-291.  doi: 10.4310/MRL.1999.v6.n3.a3.  Google Scholar

[5]

E. Artin, The theory of braids, Annals of Math., 48 (1947), 101-126.  doi: 10.2307/1969218.  Google Scholar

[6]

D. Atkins and D. Goldfeld, Addressing the algebraic eraser over the air protocol, https://eprint.iacr.org/2016/205.pdf. Google Scholar

[7]

A. Ben-Zvi, S. R. Blackburn and B. Tsaban, A practical cryptanalysis of the algebraic eraser, Advances in Cryptology - CRYPTO 2016, Part I, Lecture Notes in Comput. Sci., Springer, Berlin, 9814 (2016), 179–189. http://eprint.iacr.org/2015/1102. doi: 10.1007/978-3-662-53018-4_7.  Google Scholar

[8]

S. R. Blackburn and M. J. B. Robshaw, On the security of the algebraic eraser tag authentication protocol, Applied Cryptography and Network Security, Lecture Notes in Comput. Sci., Springer, 9696 (2016), 3–17. http://eprint.iacr.org/2016/091. doi: 10.1007/978-3-319-39555-5_1.  Google Scholar

[9]

M. Düll, B. Haase, G. Hinterwälder, M. Hutter, C. Paar, A. H. Sánchez and P. Schwabe, High-speed Curve25519 on 8-bit, 16-bit, and 32-bit microcontrollers, https://eprint.iacr.org/2015/343.pdf. Google Scholar

[10]

D. Garber, S. Kaplan, M. Teicher, B. Tsaban and U. Vishne, Length-based conjugacy search in the braid group, Algebraic Methods in Cryptography, Contemp. Math., Amer. Math. Soc., Providence, RI, 418 (2006), 75-87.  doi: 10.1090/conm/418/07947.  Google Scholar

[11]

V. Gebhardt, A new approach to the conjugacy problem in Garside groups, J. Algebra, 292 (2005), 282-302.  doi: 10.1016/j.jalgebra.2005.02.002.  Google Scholar

[12]

D. Goldfeld and P. E. Gunnells, Defeating the Kalka-Teicher-Tsaban linear algebra attack on the Algebraic Eraser, (2012), arXiv: 1202.0598. Google Scholar

[13] M. I. González Vasco, S. Magliveras and R. Steinwandt, Group-Theoretic Cryptography, Chapman & Hall/CRC Cryptography and Network Security, CRC Press, Boca Raton, FL, 2015.   Google Scholar
[14]

L. K. Grover, A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM, Symposium on the Theory of Computing, ACM, New York, (1996), 212-219.  doi: 10.1145/237814.237866.  Google Scholar

[15]

P. E. Gunnells, On the cryptanalysis of the generalized simultaneous conjugacy search problem and the security of the Algebraic Eraser, arXiv: 1105.1141v1 [cs.CR]. Google Scholar

[16]

D. Hofheinz and R. Steinwandt, A practical attack on some braid group based cryptographic primitives, Public Key Cryptography—PKC 2003, Lecture Notes in Comput. Sci., Springer, Berlin, 2567 (2002), 187-198.  doi: 10.1007/3-540-36288-6_14.  Google Scholar

[17]

A. Kalka, M. Teicher and B. Tsaban, Short expressions of permutations as products and cryptanalysis of the Algebraic Eraser, Advances in Applied Mathematics, 49 (2012), 57-76.  doi: 10.1016/j.aam.2012.03.001.  Google Scholar

[18]

K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang and C. Park, New public-key cryptosystem using braid groups, Advances in Cryptology - CRYPTO 2000, Lecture Notes in Computer Science, Springer, Berlin, 1880 (2000), 166-183.  doi: 10.1007/3-540-44598-6_10.  Google Scholar

[19]

C. Lomont, The hidden subgroup problem - review and open problems, (2004), arXiv: quant-ph/0411037. Google Scholar

[20]

H. R. Morton, The multivariable Alexander polynomial for a closed braid, Low-dimensional topology, Contemp. Math., Amer. Math. Soc., Providence, RI, 233 (1999), 167-172.  doi: 10.1090/conm/233/03427.  Google Scholar

[21]

C. Mulland and B. Tsaban, $ \rm SL _2$ homomorphic hash functions: Worst case to average case reduction and short collision search, Des. Codes Cryptogr., 81 (2016), 83–107, arXiv: 1306.5646v3 [cs.CR]. doi: 10.1007/s10623-015-0129-8.  Google Scholar

[22]

A. D. Myasnikov and A. Ushakov, Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux key agreement protocol, Groups Complex. Cryptol., 1 (2009), 63-75.  doi: 10.1515/GCC.2009.63.  Google Scholar

[23]

A. Myasnikov, V. Shpilrain and A. Ushakov, Group-Based Cryptography, Advanced Courses in Mathematics, CRM Barcelona Birkhäuser, Basel, 2008.  Google Scholar

[24]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Computing, 26 (1997), 1484-1509.  doi: 10.1137/S0097539795293172.  Google Scholar

[25]

G. Zémor, Hash functions and graphs with large girths, Eurocrypt '91, Lecture Notes in Computer Science, 547 (1991), 508-511.   Google Scholar

show all references

References:
[1]

I. Anshel, M. Anshel, D. Goldfeld and S. Lemieux, Key agreement, the Algebraic Eraser$^{TM}$, and lightweight cryptography, Algebraic Methods in Cryptography, Contemp. Math., Amer. Math. Soc., Providence, RI, 418 (2006), 1-34.  doi: 10.1090/conm/418/07943.  Google Scholar

[2]

I. Anshel, D. Atkins, D. Goldfeld and P. E. Gunnells, Defeating the Ben-Zvi, Blackburn, and Tsaban Attack on the Algebraic Eraser, arXiv: 1601.04780v1 [cs.CR]. Google Scholar

[3]

I. Anshel, D. Atkins, D. Goldfeld and P. E. Gunnells, WalnutDSA$^{TM}$: A Lightweight Quantum Resistant Digital Signature Algorithm, https://eprint.iacr.org/2017/058.pdf. Google Scholar

[4]

I. Anshel, M. Anshel and D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett., 6 (1999), 287-291.  doi: 10.4310/MRL.1999.v6.n3.a3.  Google Scholar

[5]

E. Artin, The theory of braids, Annals of Math., 48 (1947), 101-126.  doi: 10.2307/1969218.  Google Scholar

[6]

D. Atkins and D. Goldfeld, Addressing the algebraic eraser over the air protocol, https://eprint.iacr.org/2016/205.pdf. Google Scholar

[7]

A. Ben-Zvi, S. R. Blackburn and B. Tsaban, A practical cryptanalysis of the algebraic eraser, Advances in Cryptology - CRYPTO 2016, Part I, Lecture Notes in Comput. Sci., Springer, Berlin, 9814 (2016), 179–189. http://eprint.iacr.org/2015/1102. doi: 10.1007/978-3-662-53018-4_7.  Google Scholar

[8]

S. R. Blackburn and M. J. B. Robshaw, On the security of the algebraic eraser tag authentication protocol, Applied Cryptography and Network Security, Lecture Notes in Comput. Sci., Springer, 9696 (2016), 3–17. http://eprint.iacr.org/2016/091. doi: 10.1007/978-3-319-39555-5_1.  Google Scholar

[9]

M. Düll, B. Haase, G. Hinterwälder, M. Hutter, C. Paar, A. H. Sánchez and P. Schwabe, High-speed Curve25519 on 8-bit, 16-bit, and 32-bit microcontrollers, https://eprint.iacr.org/2015/343.pdf. Google Scholar

[10]

D. Garber, S. Kaplan, M. Teicher, B. Tsaban and U. Vishne, Length-based conjugacy search in the braid group, Algebraic Methods in Cryptography, Contemp. Math., Amer. Math. Soc., Providence, RI, 418 (2006), 75-87.  doi: 10.1090/conm/418/07947.  Google Scholar

[11]

V. Gebhardt, A new approach to the conjugacy problem in Garside groups, J. Algebra, 292 (2005), 282-302.  doi: 10.1016/j.jalgebra.2005.02.002.  Google Scholar

[12]

D. Goldfeld and P. E. Gunnells, Defeating the Kalka-Teicher-Tsaban linear algebra attack on the Algebraic Eraser, (2012), arXiv: 1202.0598. Google Scholar

[13] M. I. González Vasco, S. Magliveras and R. Steinwandt, Group-Theoretic Cryptography, Chapman & Hall/CRC Cryptography and Network Security, CRC Press, Boca Raton, FL, 2015.   Google Scholar
[14]

L. K. Grover, A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM, Symposium on the Theory of Computing, ACM, New York, (1996), 212-219.  doi: 10.1145/237814.237866.  Google Scholar

[15]

P. E. Gunnells, On the cryptanalysis of the generalized simultaneous conjugacy search problem and the security of the Algebraic Eraser, arXiv: 1105.1141v1 [cs.CR]. Google Scholar

[16]

D. Hofheinz and R. Steinwandt, A practical attack on some braid group based cryptographic primitives, Public Key Cryptography—PKC 2003, Lecture Notes in Comput. Sci., Springer, Berlin, 2567 (2002), 187-198.  doi: 10.1007/3-540-36288-6_14.  Google Scholar

[17]

A. Kalka, M. Teicher and B. Tsaban, Short expressions of permutations as products and cryptanalysis of the Algebraic Eraser, Advances in Applied Mathematics, 49 (2012), 57-76.  doi: 10.1016/j.aam.2012.03.001.  Google Scholar

[18]

K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang and C. Park, New public-key cryptosystem using braid groups, Advances in Cryptology - CRYPTO 2000, Lecture Notes in Computer Science, Springer, Berlin, 1880 (2000), 166-183.  doi: 10.1007/3-540-44598-6_10.  Google Scholar

[19]

C. Lomont, The hidden subgroup problem - review and open problems, (2004), arXiv: quant-ph/0411037. Google Scholar

[20]

H. R. Morton, The multivariable Alexander polynomial for a closed braid, Low-dimensional topology, Contemp. Math., Amer. Math. Soc., Providence, RI, 233 (1999), 167-172.  doi: 10.1090/conm/233/03427.  Google Scholar

[21]

C. Mulland and B. Tsaban, $ \rm SL _2$ homomorphic hash functions: Worst case to average case reduction and short collision search, Des. Codes Cryptogr., 81 (2016), 83–107, arXiv: 1306.5646v3 [cs.CR]. doi: 10.1007/s10623-015-0129-8.  Google Scholar

[22]

A. D. Myasnikov and A. Ushakov, Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux key agreement protocol, Groups Complex. Cryptol., 1 (2009), 63-75.  doi: 10.1515/GCC.2009.63.  Google Scholar

[23]

A. Myasnikov, V. Shpilrain and A. Ushakov, Group-Based Cryptography, Advanced Courses in Mathematics, CRM Barcelona Birkhäuser, Basel, 2008.  Google Scholar

[24]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Computing, 26 (1997), 1484-1509.  doi: 10.1137/S0097539795293172.  Google Scholar

[25]

G. Zémor, Hash functions and graphs with large girths, Eurocrypt '91, Lecture Notes in Computer Science, 547 (1991), 508-511.   Google Scholar

Figure 1.  Ironwood Data Flows
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Ironwood Protocol Flow
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Performance on MSP430, LPC1768 (in Cycles)
Artin Length MSP430 LPC1768
$ |\beta| $ $ |\beta'| $
2626 5272 6002668 2026216
2332 3580 4532480 1538472
2414 3944 4862464 1648742
3172 4266 5661952 1914009
2168 4514 5101824 1728545
3092 4698 5922048 2000312
2978 3968 5297664 1792959
2744 4420 5459456 1845502
2430 4762 5479424 1854446
2636 3600 4771840 1617670
2659.2 4302.4 5309182 1796687
Table Options

Download as excel

Artin Length MSP430 LPC1768
$ |\beta| $ $ |\beta'| $
2626 5272 6002668 2026216
2332 3580 4532480 1538472
2414 3944 4862464 1648742
3172 4266 5661952 1914009
2168 4514 5101824 1728545
3092 4698 5922048 2000312
2978 3968 5297664 1792959
2744 4420 5459456 1845502
2430 4762 5479424 1854446
2636 3600 4771840 1617670
2659.2 4302.4 5309182 1796687
Table 2.  Performance on MSP430, LPC1768, CC2650 (in ms)
Artin Length MSP430 LPC1768 CC2650 48Mhz
$ |\beta| $ $ |\beta'| $ 25MHz 48MHz (SST 5) (SST 2)
2626 5272 240.1 42.2 42 42
2332 3580 181.3 32.2 32 32
2414 3944 194.5 34.3 34 35
3172 4266 226.5 39.9 40 40
2168 4514 204.1 36.0 36 36
3092 4698 236.9 41.2 42 42
2978 3968 211.9 37.4 37 37
2744 4420 218.4 38.4 38 39
2430 4762 219.2 38.6 39 39
2636 3600 190.9 33.7 34 34
2659.2 4302.4 212.4 37.4 37.4 37.6
Table Options

Download as excel

Artin Length MSP430 LPC1768 CC2650 48Mhz
$ |\beta| $ $ |\beta'| $ 25MHz 48MHz (SST 5) (SST 2)
2626 5272 240.1 42.2 42 42
2332 3580 181.3 32.2 32 32
2414 3944 194.5 34.3 34 35
3172 4266 226.5 39.9 40 40
2168 4514 204.1 36.0 36 36
3092 4698 236.9 41.2 42 42
2978 3968 211.9 37.4 37 37
2744 4420 218.4 38.4 38 39
2430 4762 219.2 38.6 39 39
2636 3600 190.9 33.7 34 34
2659.2 4302.4 212.4 37.4 37.4 37.6
[1]

Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012
[2]

Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281
[3]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489
[4]

Felipe Cabarcas, Daniel Cabarcas, John Baena. Efficient public-key operation in multivariate schemes. Advances in Mathematics of Communications, 2019, 13 (2) : 343-371. doi: 10.3934/amc.2019023
[5]

Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013
[6]

Wenbo Fu, Debnath Narayan. Optimization algorithm for embedded Linux remote video monitoring system oriented to the internet of things (IOT). Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1341-1354. doi: 10.3934/dcdss.2019092
[7]

Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215
[8]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020046
[9]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281
[10]

Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169
[11]

Andreas Klein. How to say yes, no and maybe with visual cryptography. Advances in Mathematics of Communications, 2008, 2 (3) : 249-259. doi: 10.3934/amc.2008.2.249
[12]

Joan-Josep Climent, Juan Antonio López-Ramos. Public key protocols over the ring $E_{p}^{(m)}$. Advances in Mathematics of Communications, 2016, 10 (4) : 861-870. doi: 10.3934/amc.2016046
[13]

Jian-Wu Xue, Xiao-Kun Xu, Feng Zhang. Big data dynamic compressive sensing system architecture and optimization algorithm for internet of things. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1401-1414. doi: 10.3934/dcdss.2015.8.1401
[14]

Hanyu Cao, Meiying Zhang, Huanxi Cai, Wei Gong, Min Su, Bin Li. A zero-forcing beamforming based time switching protocol for wireless powered internet of things system. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-10. doi: 10.3934/jimo.2019086
[15]

André de Carvalho, Toby Hall. Decoration invariants for horseshoe braids. Discrete & Continuous Dynamical Systems - A, 2010, 27 (3) : 863-906. doi: 10.3934/dcds.2010.27.863
[16]

Rod Cross, Hugh McNamara, Leonid Kalachev, Alexei Pokrovskii. Hysteresis and post Walrasian economics. Discrete & Continuous Dynamical Systems - B, 2013, 18 (2) : 377-401. doi: 10.3934/dcdsb.2013.18.377
[17]

Felix Fontein. Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures. Advances in Mathematics of Communications, 2008, 2 (3) : 293-307. doi: 10.3934/amc.2008.2.293
[18]

Christoph Hauert, Nina Haiden, Karl Sigmund. The dynamics of public goods. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 575-587. doi: 10.3934/dcdsb.2004.4.575
[19]

D. Alderson, H. Chang, M. Roughan, S. Uhlig, W. Willinger. The many facets of internet topology and traffic. Networks & Heterogeneous Media, 2006, 1 (4) : 569-600. doi: 10.3934/nhm.2006.1.569
[20]

S. Öykü Yurttaş. Dynnikov and train track transition matrices of pseudo-Anosov braids. Discrete & Continuous Dynamical Systems - A, 2016, 36 (1) : 541-570. doi: 10.3934/dcds.2016.36.541

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (17)
  • HTML views (96)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences