Ironwood meta key agreement and authentication protocol

Iris Anshel; Derek Atkins; Dorian Goldfeld; Paul E. Gunnells

doi:10.3934/amc.2020073

Previous Article
New self-dual codes of length 68 from a $ 2 \times 2 $ block matrix construction and group rings
AMC Home
This Issue
Next Article
Infinite families of $ 3 $-designs from o-polynomials

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]	Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046
[2]	Linhao Xu, Marya Claire Zdechlik, Melissa C. Smith, Min B. Rayamajhi, Don L. DeAngelis, Bo Zhang. Simulation of post-hurricane impact on invasive species with biological control management. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 4059-4071. doi: 10.3934/dcds.2020038
[3]	Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020451
[4]	Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure & Applied Analysis, 2021, 20 (2) : 885-902. doi: 10.3934/cpaa.2020295
[5]	Xiuli Xu, Xueke Pu. Optimal convergence rates of the magnetohydrodynamic model for quantum plasmas with potential force. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 987-1010. doi: 10.3934/dcdsb.2020150
[6]	Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $ q $-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020440
[7]	José Luis López. A quantum approach to Keller-Segel dynamics via a dissipative nonlinear Schrödinger equation. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020376

2019 Impact Factor: 0.734

Tools

Metrics

Tools

Article outline

Figures and Tables

2019 Impact Factor: 0.734

Tools

Figures and Tables

2019 Impact Factor: 0.734

American Institute of Mathematical Sciences

Ironwood meta key agreement and authentication protocol

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Ironwood meta key agreement and authentication protocol

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors