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

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

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.
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

Metrics

  • PDF downloads (117)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]