Paper 2018/604

Attack on Kayawood Protocol: Uncloaking Private Keys

Matvei Kotov, Anton Menshov, and Alexander Ushakov

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. Our implementation of the attack is available on GitHub.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Kayawood protocolgroup-based cryptographykey agreementalgebraic eraserbraid groupcolored Burau presentationE-multiplicationcloaking problem
Contact author(s)
menshov a v @ gmail com
History
2019-04-26: revised
2018-06-18: received
See all versions
Short URL
https://ia.cr/2018/604
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/604,
      author = {Matvei Kotov and Anton Menshov and Alexander Ushakov},
      title = {Attack on Kayawood Protocol: Uncloaking Private Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2018/604},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/604}},
      url = {https://eprint.iacr.org/2018/604}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.