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, (1993), 232.

[2]

C. Boyd and A. Mathuria, Protocols for authentication and key establishment,, in, (2003).

[3]

R. Canetti, Universally composable security: a new paradigm for cryptographic protocols,, Cryptology ePrint Archive, (2000).

[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. 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, (2002).

[6]

G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup actions,, Adv. Math. Commun., 1 (2007), 489. doi: 10.3934/amc.2007.1.489.

[7]

V. Shoup, On formal models for secure key exchange (version 4),, Technical report, (1999).

[8]

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

show all references

References:
[1]

M. Bellare and P. Rogaway, Entity authentication and key distribution,, in, (1993), 232.

[2]

C. Boyd and A. Mathuria, Protocols for authentication and key establishment,, in, (2003).

[3]

R. Canetti, Universally composable security: a new paradigm for cryptographic protocols,, Cryptology ePrint Archive, (2000).

[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. 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, (2002).

[6]

G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup actions,, Adv. Math. Commun., 1 (2007), 489. doi: 10.3934/amc.2007.1.489.

[7]

V. Shoup, On formal models for secure key exchange (version 4),, Technical report, (1999).

[8]

Python Software Foundation, Python Programming Language - Offical Website,, available online at \url{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]

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

[5]

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

[6]

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

[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]

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

[9]

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

[10]

Michael Hutchings. Mean action and the Calabi invariant. Journal of Modern Dynamics, 2016, 10: 511-539. doi: 10.3934/jmd.2016.10.511

[11]

J. W. Neuberger. How to distinguish a local semigroup from a global semigroup. Discrete & Continuous Dynamical Systems - A, 2013, 33 (11&12) : 5293-5303. doi: 10.3934/dcds.2013.33.5293

[12]

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

[13]

Andrzej Biś. Entropies of a semigroup of maps. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 639-648. doi: 10.3934/dcds.2004.11.639

[14]

Carlos Cabrera, Peter Makienko, Peter Plaumann. Semigroup representations in holomorphic dynamics. Discrete & Continuous Dynamical Systems - A, 2013, 33 (4) : 1333-1349. doi: 10.3934/dcds.2013.33.1333

[15]

Helmut Kröger. From quantum action to quantum chaos. Conference Publications, 2003, 2003 (Special) : 492-500. doi: 10.3934/proc.2003.2003.492

[16]

Jana Kopfová. Nonlinear semigroup methods in problems with hysteresis. Conference Publications, 2007, 2007 (Special) : 580-589. doi: 10.3934/proc.2007.2007.580

[17]

Renato Iturriaga, Héctor Sánchez Morgado. The Lax-Oleinik semigroup on graphs. Networks & Heterogeneous Media, 2017, 12 (4) : 643-662. doi: 10.3934/nhm.2017026

[18]

Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281

[19]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[20]

Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052

2016 Impact Factor: 0.8

Metrics

  • PDF downloads (1)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]