Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: 94A60.

 Citation:

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