American Institute of Mathematical Sciences

Advanced
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

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

[2]

C. Boyd and A. Mathuria, Protocols for authentication and key establishment, in "Information Security and Cryptography,'' Springer, 2003. Google Scholar

[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/ Google Scholar

[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.  Google Scholar

[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 Google Scholar

[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.  Google Scholar

[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. Google Scholar

[8]

Python Software Foundation, Python Programming Language - Offical Website,, available online at \url{http://www.python.org}, ().   Google Scholar

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

[2]

C. Boyd and A. Mathuria, Protocols for authentication and key establishment, in "Information Security and Cryptography,'' Springer, 2003. Google Scholar

[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/ Google Scholar

[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.  Google Scholar

[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 Google Scholar

[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.  Google Scholar

[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. Google Scholar

[8]

Python Software Foundation, Python Programming Language - Offical Website,, available online at \url{http://www.python.org}, ().   Google Scholar

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

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy