Attack on Kayawood protocol: uncloaking private keys

Matvei Kotov, Anton Menshov, Alexander Ushakov

Type: Article

Publication Date: 2020-12-01

Citations: 1

DOI: https://doi.org/10.1515/jmc-2019-0015

Abstract

Abstract We analyze security properties of a two-party key-agreement protocol recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels, called Kayawood protocol. At the core of the protocol is an action (called E-multiplication ) of a braid group on some finite set. The protocol assigns a secret element of a braid group to each party (private key). To disguise those elements, the protocol uses a so-called cloaking method that multiplies private keys on the left and on the right by specially designed elements (stabilizers for E-multiplication). We present a heuristic algorithm that allows a passive eavesdropper to recover Alice’s private key by removing cloaking elements. Our attack has 100% success rate on randomly generated instances of the protocol for the originally proposed parameter values and for recent proposals that suggest to insert many cloaking elements at random positions of the private key. Implementation of the attack is available on GitHub.

Locations

Journal of Mathematical Cryptology - View - PDF
DOAJ (DOAJ: Directory of Open Access Journals) - View

Similar Works

Action	Title	Year	Authors
+	AN ATTACK ON THE WALNUT DIGITAL SIGNATURE ALGORITHM.	2018	Matvei Kotov Anton Menshov Alexander Ushakov
+ PDF Chat	Mean-set attack: cryptanalysis of Sibert et al. authentication protocol	2010	Natalia Mosina Alexander Ushakov
+	Mean-Set Attack: Cryptanalysis of Sibert et al. Authentication Protocol	2010	Natalia Mosina Alexander Ushakov
+	Mean-Set Attack: Cryptanalysis of Sibert et al. Authentication Protocol	2010	Natalia Mosina Alexander Ushakov
+	A Practical Attack on the Root Problem in Braid Groups.	2005	Anja Groch Dennis Hofheinz Rainer Steinwandt
+ PDF Chat	The Cracking of WalnutDSA: A Survey	2019	José Ignacio Escribano Pablos María Isabel González Vasco Misael E. Marriaga Ángel L. Pérez del Pozo
+	Conjugacy Separation Problem in Braids: an Attack on the Original Colored Burau Key Agreement Protocol.	2018	Matvei Kotov Anton Menshov Alex D. Myasnikov Dmitry Panteleev Alexander Ushakov
+ PDF Chat	A Practical Cryptanalysis of WalnutDSA$$^{\text {TM}}$$	2018	Daniel Hart Dohoon Kim Giacomo Micheli Guillermo Pascual-Perez Christophe Petit Yuxuan Quek
+ PDF Chat	A Practical Attack on a Braid Group Based Cryptographic Protocol	2005	Alexei Myasnikov Vladimir Shpilrain Alexander Ushakov
+ PDF Chat	Group key management based on semigroup actions	2016	J. A. López-Ramos Joachim Rosenthal Davide Schipani Reto Schnyder
+	Public-key cryptosystem using braid groups	2001	박해룡
+	Key agreement, the Algebraic Eraser^{𝑇𝑀}, and lightweight cryptography	2006	Iris Anshel Michael Anshel Dorian Goldfeld Stéphane Lemieux
+	WalnutDSA: Another attempt at braid group cryptography	2019	Magnus Ringerud
+	Random Subgroups of Braid Groups: An Approach to Cryptanalysis of a Braid Group	2006	Alexei Myasnikov Vladimir Shpilrain Alexander Ushakov
+	Another Look at ALGORAND	2019	Yongge Wang
+	Shamir's 3-pass protocol The difference between a protocol and a cryptograph-	2000
+	Algorand	2016	Jing Chen Silvio Micali
+	Short expressions of permutations as products and cryptanalysis of the Algebraic Eraser	2012	Arkadius Kalka Mina Teicher Boaz Tsaban
+	Group key management based on semigroup actions	2015	J. A. López-Ramos Joachim Rosenthal Davide Schipani Reto Schnyder
+	Group key management based on semigroup actions	2015	J. A. López-Ramos Joachim Rosenthal Davide Schipani Reto Schnyder

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (19)

Action	Title	Year	Authors
+ PDF Chat	A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem	2003	Jung Hee Cheon Byungheup Jun
+ PDF Chat	New Public-Key Cryptosystem Using Braid Groups	2000	Ki Hyoung Ko Sangjin Lee Jung Hee Cheon Jae Woo Han Ju-Sung Kang Choon‐Sik Park
+	A Practical Attack on Some Braid Group Based Cryptographic Primitives	2002	Dennis Hofheinz Rainer Steinwandt
+	Word Processing in Groups	1992	D. B. A. Epstein
+ PDF Chat	A Practical Attack on a Braid Group Based Cryptographic Protocol	2005	Alexei Myasnikov Vladimir Shpilrain Alexander Ushakov
+ PDF Chat	Random Subgroups of Braid Groups: An Approach to Cryptanalysis of a Braid Group Based Cryptographic Protocol	2006	Alexei Myasnikov Vladimir Shpilrain Alexander Ushakov
+	Length Based Attack and Braid Groups: Cryptanalysis of Anshel-Anshel-Goldfeld Key Exchange Protocol	2007	Alex D. Myasnikov Alexander Ushakov
+ PDF Chat	Length-based conjugacy search in the braid group	2006	David Garber S. Kaplan Mina Teicher Boaz Tsaban Uzi Vishne
+ PDF Chat	The set of minimal braids is co-NP-complete	1991	Mike Paterson Alexander Razborov
+ PDF Chat	Polynomial-Time Solutions of Computational Problems in Noncommutative-Algebraic Cryptography	2013	Boaz Tsaban