Cryptanalysis of a 2-party key establishment based on a semigroup action problem

Previous Article
Codes from incidence matrices and line graphs of Paley graphs
AMC Home
This Issue
Next Article
The enumeration of Costas arrays of order 28 and its consequences

February 2011, 5(1): 87-92. doi: 10.3934/amc.2011.5.87

Cryptanalysis of a 2-party key establishment based on a semigroup action problem

Rainer Steinwandt ^1, and Adriana Suárez Corona ^2,

1.	Department of Mathematical Sciences, Florida Atlantic University, Boca Raton, FL 33431
2.	Departamento de Matemáticas, Universidad de Oviedo, 33007 Oviedo, Spain

Received July 2010 Revised October 2010 Published February 2011

Abstract
Related Papers

An Advances in Mathematics of Communications article from 2007 proposes an informal 2-party key establishment along the lines of the classic Diffie-Hellman construction, but using a two-sided matrix semiring action. The article contains no formal security analysis, but a specific parameter choice has been considered. We describe a heuristic attack technique against the suggested instance, which for the published "challenge value" results in a complete session key recovery with only a minor computational effort.

Keywords: semigroup action problem, key establishment, Cryptanalysis, semiring..

Mathematics Subject Classification: 94A6.

Citation: Rainer Steinwandt, Adriana Suárez Corona. Cryptanalysis of a 2-party key establishment based on a semigroup action problem. Advances in Mathematics of Communications, 2011, 5 (1) : 87-92. doi: 10.3934/amc.2011.5.87

References:

[1]	M. Bellare and P. Rogaway, Entity authentication and key distribution, in "Advances in Cryptology - CRYPTO '93'' (ed. D.R. Stinson), Springer, (1993), 232-249.
[2]	C. Boyd and A. Mathuria, Protocols for authentication and key establishment, in "Information Security and Cryptography,'' Springer, 2003.
[3]	R. Canetti, Universally composable security: a new paradigm for cryptographic protocols, Cryptology ePrint Archive, Report 2000/067, December 2005; available online at http://eprint.iacr.org/2000/067/
[4]	M. I. González Vasco and R. Steinwandt, Clouds over a public key cryptosystem based on Lyndon words, Inform. Processing Letters, 80 (2001), 239-242. doi: 10.1016/S0020-0190(01)00170-3.
[5]	J. Hughes and A. Tannenbaum, Length-based attacks for certain group based encryption rewriting systems, in "Workshop SECI02 SEcurité de la Communication sur Intenet, 2002,'' preprint, arXiv:cs/0306032
[6]	G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup actions, Adv. Math. Commun., 1 (2007), 489-507. doi: 10.3934/amc.2007.1.489.
[7]	V. Shoup, On formal models for secure key exchange (version 4), Technical report, IBM Zurich Research Lab, November 1999; available online at http://www.shoup.net/papers/skey.pdf, revision of IBM Research Report RZ 3120.
[8]	Python Software Foundation, Python Programming Language - Offical Website, available online at http://www.python.org

show all references

References:

[1]	M. Bellare and P. Rogaway, Entity authentication and key distribution, in "Advances in Cryptology - CRYPTO '93'' (ed. D.R. Stinson), Springer, (1993), 232-249.
[2]	C. Boyd and A. Mathuria, Protocols for authentication and key establishment, in "Information Security and Cryptography,'' Springer, 2003.
[3]	R. Canetti, Universally composable security: a new paradigm for cryptographic protocols, Cryptology ePrint Archive, Report 2000/067, December 2005; available online at http://eprint.iacr.org/2000/067/
[4]	M. I. González Vasco and R. Steinwandt, Clouds over a public key cryptosystem based on Lyndon words, Inform. Processing Letters, 80 (2001), 239-242. doi: 10.1016/S0020-0190(01)00170-3.
[5]	J. Hughes and A. Tannenbaum, Length-based attacks for certain group based encryption rewriting systems, in "Workshop SECI02 SEcurité de la Communication sur Intenet, 2002,'' preprint, arXiv:cs/0306032
[6]	G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup actions, Adv. Math. Commun., 1 (2007), 489-507. doi: 10.3934/amc.2007.1.489.
[7]	V. Shoup, On formal models for secure key exchange (version 4), Technical report, IBM Zurich Research Lab, November 1999; available online at http://www.shoup.net/papers/skey.pdf, revision of IBM Research Report RZ 3120.
[8]	Python Software Foundation, Python Programming Language - Offical Website, available online at http://www.python.org

[1]	Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247
[2]	Rainer Steinwandt, Adriana Suárez Corona. Attribute-based group key establishment. Advances in Mathematics of Communications, 2010, 4 (3) : 381-398. doi: 10.3934/amc.2010.4.381
[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]	Viorel Nitica, Andrei Török. On a semigroup problem. Discrete and Continuous Dynamical Systems - S, 2019, 12 (8) : 2365-2377. doi: 10.3934/dcdss.2019148
[5]	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
[6]	J. I. Díaz, J. F. Padial. On a free-boundary problem modeling the action of a limiter on a plasma. Conference Publications, 2007, 2007 (Special) : 313-322. doi: 10.3934/proc.2007.2007.313
[7]	Vladimir E. Fedorov, Natalia D. Ivanova. Identification problem for a degenerate evolution equation with overdetermination on the solution semigroup kernel. Discrete and Continuous Dynamical Systems - S, 2016, 9 (3) : 687-696. doi: 10.3934/dcdss.2016022
[8]	Joan-Josep Climent, Elisa Gorla, Joachim Rosenthal. Cryptanalysis of the CFVZ cryptosystem. Advances in Mathematics of Communications, 2007, 1 (1) : 1-11. doi: 10.3934/amc.2007.1.1
[9]	Yu Tian, John R. Graef, Lingju Kong, Min Wang. Existence of solutions to a multi-point boundary value problem for a second order differential system via the dual least action principle. Conference Publications, 2013, 2013 (special) : 759-769. doi: 10.3934/proc.2013.2013.759
[10]	Brandon Seward. Every action of a nonamenable group is the factor of a small action. Journal of Modern Dynamics, 2014, 8 (2) : 251-270. doi: 10.3934/jmd.2014.8.251
[11]	Subhabrata Samajder, Palash Sarkar. Another look at success probability of linear cryptanalysis. Advances in Mathematics of Communications, 2019, 13 (4) : 645-688. doi: 10.3934/amc.2019040
[12]	Michael Hutchings. Mean action and the Calabi invariant. Journal of Modern Dynamics, 2016, 10: 511-539. doi: 10.3934/jmd.2016.10.511
[13]	David Bechara Senior, Umberto L. Hryniewicz, Pedro A. S. Salomão. On the relation between action and linking. Journal of Modern Dynamics, 2021, 17: 319-336. doi: 10.3934/jmd.2021011
[14]	J. W. Neuberger. How to distinguish a local semigroup from a global semigroup. Discrete and Continuous Dynamical Systems, 2013, 33 (11&12) : 5293-5303. doi: 10.3934/dcds.2013.33.5293
[15]	Yvo Desmedt, Niels Duif, Henk van Tilborg, Huaxiong Wang. Bounds and constructions for key distribution schemes. Advances in Mathematics of Communications, 2009, 3 (3) : 273-293. doi: 10.3934/amc.2009.3.273
[16]	Andrzej Biś. Entropies of a semigroup of maps. Discrete and Continuous Dynamical Systems, 2004, 11 (2&3) : 639-648. doi: 10.3934/dcds.2004.11.639
[17]	Michael Blank. Recurrence for measurable semigroup actions. Discrete and Continuous Dynamical Systems, 2021, 41 (4) : 1649-1665. doi: 10.3934/dcds.2020335
[18]	Carlos Cabrera, Peter Makienko, Peter Plaumann. Semigroup representations in holomorphic dynamics. Discrete and Continuous Dynamical Systems, 2013, 33 (4) : 1333-1349. doi: 10.3934/dcds.2013.33.1333
[19]	Helmut Kröger. From quantum action to quantum chaos. Conference Publications, 2003, 2003 (Special) : 492-500. doi: 10.3934/proc.2003.2003.492
[20]	Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Rainer Steinwandt Adriana Suárez Corona
on Google Scholar
Rainer Steinwandt Adriana Suárez Corona

[Back to Top]