Abstract
This paper introduces a new type of attack, termed a nonlinear decomposition attack, against two known group-based key agreement protocols, namely, protocol based on extensions of (semi)groups by endomorphisms introduced by Kahrobaei, Shpilrain et al., and the noncommutative Diffie–Hellman protocol introduced by Ko, Lee et al. This attack works efficiently in the case when finitely generated nilpotent (more generally, polycyclic) groups are used as platforms. This attack is based on a deterministic algorithm that finds the secret shared key from the public data in both the protocols under consideration. Furthermore, we show that in this case one can break the schemes without solving the algorithmic problems on which the assumptions are based. The efficacy of the attack depends on the platform group, so it requires a more thorough analysis in each particular case.
Funding source: Russian Science Foundation
Award Identifier / Grant number: 16-11-10002
Funding statement: This research was supported by Russian Science Foundation (project 16-11-10002).
References
[1] Anshel I., Anshel M. and Goldfeld D., An algebraic method for public-key cryptography, Math. Res. Lett. 6 (1999), 287–291. 10.4310/MRL.1999.v6.n3.a3Search in Google Scholar
[2] Baumslag G., Cannonito F. B., Robinson D. J. S. and Segal D., The algorithmic theory of polycyclic-by-finite groups, J. Algebra 142 (1991), 118–149. 10.1016/0021-8693(91)90221-SSearch in Google Scholar
[3] Ben-Zvi A., Kalka A. and Tsaban B., Cryptanalysis via algebraic spans, preprint 2014, https://eprint.iacr.org/2014/041. 10.1007/978-3-319-96884-1_9Search in Google Scholar
[4] Bosma W., Cannon J. and Playoust C., The MAGMA algebra system I: The user language, J. Symbolic Comput. 24 (1997), 235–265. 10.1006/jsco.1996.0125Search in Google Scholar
[5] Cavallo B. and Kahrobaei D., A family of polycyclic groups over which the conjugacy problem is NP-complete, preprint 2014, https://arxiv.org/abs/1403.4153v2. 10.1142/S0218196714500234Search in Google Scholar
[6] Cheon J. and Jun B., A polynomial time algorithm for the braid Diffie–Hellman conjugacy problem, Advances in Cryptology (CRYPTO 2003), Lecture Notes in Comput. Sci. 2729, Springer, Berlin (2003), 212–225. 10.1007/978-3-540-45146-4_13Search in Google Scholar
[7] Ding J., Miasnikov A. D. and Ushakov A., A linear attack on a key exchange protocol using extensions of matrix semigroups, preprint 2015, https://eprint.iacr.org/2015/018. Search in Google Scholar
[8] Eick B. and Kahrobaei D., Polycyclic groups: A new platform for cryptology?, preprint 2004, https://arxiv.org/abs/math/0411077. Search in Google Scholar
[9] Eick B. and Ostheimer G., On the orbit-stabilizer problem for integral matrix actions of polycyclic groups, Math. Comp. 72 (2003), 1511–1529. 10.1090/S0025-5718-03-01493-5Search in Google Scholar
[10] Garber D., Kahrobaei D. and Lam H. T., Analysing the length-based attack on polycyclic groups, preprint 2013, https://arxiv.org/abs/1305.0548v1. Search in Google Scholar
[11] Garber D., Kaplan S., Teicher M., Tsaban B. and Vishne U., Probabilistic solutions of equations in the braid group, Adv. Appl. Math. 35 (2005), 323–334. 10.1016/j.aam.2005.03.002Search in Google Scholar
[12] Garber D., Kaplan S., Teicher M., Tsaban B. and Vishne U., Length-based conjugacy search in the braid group, Algebraic Methods in Cryptography (Mainz/Bochum 2005), Contemp. Math. 418, American Mathematical Society, Providence (2006), 75–87. 10.1090/conm/418/07947Search in Google Scholar
[13] Habeeb M., Kahrobaei D., Koupparis C. and Shpilrain V., Public key exchange using semidirect product of (semi)groups, preprint 2013, https://arxiv.org/abs/1304.6572v1. 10.1007/978-3-642-38980-1_30Search in Google Scholar
[14] Hall P., Edmonton Notes on Nilpotent Groups, Queen Mary College Math. Notes, Queen Mary College, London, 1969. Search in Google Scholar
[15] Hughes J. and Tannenbaum A., Length-based attacks for certain group-based encryption rewriting systems, Workshop SECI02 Securite de la Communication sur Internet 2002. Search in Google Scholar
[16] Janusz G. J., Faithful representations of p-groups at characteristic p, J. Algebra 15 (1970), 335–351. 10.1016/0021-8693(70)90063-3Search in Google Scholar
[17] Kahrobaei D. and Anshel M., Decision and search in non-abelian Cramer–Shoup public key cryptosystem, Groups Complex. Cryptol. 1 (2009), 217–225. 10.1515/GCC.2009.217Search in Google Scholar
[18] Kahrobaei D. and Khan B., A non-commutative generalization of ElGamal key exchange using polycyclic groups, Global Telecommunications Conference 2006 (GLOBECOM ’06), IEEE Press, Piscataway (2006), DOI 10.1109/GLOCOM.2006.290. 10.1109/GLOCOM.2006.290Search in Google Scholar
[19] Kahrobaei D. and Koupparis C., Non-commutative digital structures using non-commutative groups, Groups Complex. Cryptol. 4 (2012), 377–384. 10.1515/gcc-2012-0019Search in Google Scholar
[20] Kahrobaei D., Koupparis C. and Shpilrain V., Key exchange using semidirect product of (semi)groups, Applied Cryptography and Network Security (ACNS 2013), Lecture Notes in Comput. Sci. 7954, Springer, Berlin (2013), 475–486. 10.1007/978-3-642-38980-1_30Search in Google Scholar
[21] Kahrobaei D., Lam H. and Shpilrain V., Public key exchange using extensions by endomorphisms and matrices over a Galois field, preprint, http://www.sci.ccny.cuny.edu/~shpil/res.html. Search in Google Scholar
[22] Kahrobaei D. and Shpilrain V., Using semidirect product of (semi)groups in public key cryptography, preprint 2016, https://arxiv.org/abs/1604.05542v1. 10.1007/978-3-319-40189-8_14Search in Google Scholar
[23] Ko K. H., Lee S. J., Cheon J. H., Han J. W., Kang J. and Park C., New public-key cryptosystem using braid groups, Advances in Cryptology (CRYPTO 2000), Lecture Notes in Comput. Sci. 1880, Springer, Berlin (2000), 166–183. 10.1007/3-540-44598-6_10Search in Google Scholar
[24] Kreuzer M., Myasnikov A. D. and Ushakov A., A linear algebra attack to group-ring-based key exchange protocols, Applied Cryptography and Network Security (ACNS 2014), Lecture Notes in Comput. Sci. 8479, Springer, Berlin (2014), 37–43; https://eprint.iacr.org/2015/018.pdf. 10.1007/978-3-319-07536-5_3Search in Google Scholar
[25] Leedham-Green C. and Soicher L., Symbolic collection from the left and other strategies, J. Symbolic Comput. 9 (1990), 665–675. 10.1016/S0747-7171(08)80081-8Search in Google Scholar
[26] Lennox J. C. and Robinson D. J. S., The Theory of Infinite Soluble Groups, Oxford Mathematical Monographs, Clarendon Press, Oxford, 2004. 10.1093/acprof:oso/9780198507284.001.0001Search in Google Scholar
[27] Mahalanobis A., The Diffie–Hellman key exchange protocol and non-abelian nilpotent groups, Israel J. Math. 165 (2008), 161–87. 10.1007/s11856-008-1008-zSearch in Google Scholar
[28] Miasnikov A. G., Shpilrain V. and Ushakov A., Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol, Public Key Cryptography (PKC 2006), Lecture Notes in Comput. Sci. 3958, Springer, Berlin (2006), 302–314. 10.1007/11745853_20Search in Google Scholar
[29] Miasnikov A. G. and Ushakov A., Random subgroups and analysis of the length-based and quotient attacks, J. Math. Cryptol. 2 (2008), 29–61. 10.1515/JMC.2008.003Search in Google Scholar
[30] Myasnikov A. G. and Roman’kov V. A., A linear decomposition attack, Groups Complex. Cryptol. 7 (2015), 81–94; see also https://arxiv.org/abs/1412.6401v1. 10.1515/gcc-2015-0007Search in Google Scholar
[31] Myasnikov A., Shpilrain V. and Ushakov A., Group-Based Cryptography, Adv. Courses Math. CRM Barcelona, Birkhäuser, Basel, 2008. Search in Google Scholar
[32] Myasnikov A., Shpilrain V. and Ushakov A., Non-Commutative Cryptography and Complexity of Group-theoretic Problems. With appendix by Natalia Mosina, Math. Surveys Monogr. 177, American Mathematical Society, Providence, 2011. 10.1090/surv/177Search in Google Scholar
[33] Myasnikov A. D. and Ushakov A., Length based attack and braid groups: Cryptanalysis of Anshel–Anshel–Godlfeld key exchange protocol, Public Key Cryptography (PKC 2007), Lecture Notes in Comput. Sci. 4450, Springer, Berlin (2007), 76–88. 10.1007/978-3-540-71677-8_6Search in Google Scholar
[34] Roman’kov V. A., Equations over groups, Groups Complex. Cryptol. 4 (2012), no. 2, 191–239. 10.1515/gcc-2012-0015Search in Google Scholar
[35] Roman’kov V. A., Algebraic Cryptography (in Russian), Omsk, Omsk State University, 2013. Search in Google Scholar
[36] Roman’kov V. A., Cryptanalysis of some schemes applying automorphisms (in Russian), Appl. Discrete Math. 3 (2013), 35–51. 10.17223/20710410/21/5Search in Google Scholar
[37] Roman’kov V. A., A polynomial time algorithm for the braid double shielded public key cryptosystems, preprint 2014, https://arxiv.org/abs/1412.5277v1. Search in Google Scholar
[38] Roman’kov V. A., Linear decomposition attack on public key exchange protocols using semidirect products of (semi)groups, preprint 2015, https://arxiv.org/abs/1501.01152v1. Search in Google Scholar
[39] Roman’kov V. A. and Menshov A., Cryptanalysis of Andrecut’s public key cryptosystem, preprint 2015, https://arxiv.org/abs/1507.01496v1. Search in Google Scholar
[40] Segal D., Polycyclic Groups, Cambridge Tracts in Math. 82, Cambridge University Press, Cambridge, 2005. Search in Google Scholar
[41] Shpilrain V. and Zapata G., Using the subgroup membership search problem in public key cryptography, Algebraic Methods in Cryptography (Mainz/Bochum 2005), Contemp. Math. 418, American Mathematical Society, Providence (2006), 169–181. 10.1090/conm/418/07955Search in Google Scholar
[42] Sims C. C., Computation with Finitely Presented Groups, Encyclopedia Math. Appl. 48, Cambridge University Press, Cambridge, 1994. 10.1017/CBO9780511574702Search in Google Scholar
[43] Tsaban B., Practical polynomial time solutions of several major problems in noncommutative-algebraic cryptography (preliminary announcement), preprint 2014, https://eprint.iacr.org/2014/041/20140115:201530. Search in Google Scholar
[44] Tsaban B., Polynomial time solutions of computational problems in noncommutative algebraic cryptography, J. Cryptology 28 (2015), no. 2, 601–622. 10.1007/s00145-013-9170-9Search in Google Scholar
[45] The GAP group, GAP – Groups, Algorithms and Programming, 2000. Search in Google Scholar
© 2016 by De Gruyter
