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

Rainer Steinwandt; Adriana Suárez Corona

doi:10.3934/amc.2011.5.87

Article Contents

2011, Volume 5, Issue 1: 87-92. Doi: 10.3934/amc.2011.5.87

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

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

Received: June 30, 2010

Revised: September 30, 2010

Published: January 2011

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 94A60.

Citation:

Related Papers

Cited by

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