Paper 2018/393

AN ATTACK ON THE WALNUT DIGITAL SIGNATURE ALGORITHM

Matvei Kotov, Anton Menshov, and Alexander Ushakov

Abstract

In this paper, we analyze security properties of the WalnutDSA, a digital signature algorithm recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels,that has been accepted by the National Institute of Standards and Technology for evaluation as a standard for quantum-resistant public-key cryptography. At the core of the algorithm is an action, named E-multiplication, of a braid group on some finite set. The protocol assigns a pair of braids to the signer as a private key. A signature of a message $m$ is a specially constructed braid that is obtained as a product of private keys, the hash value of $m$ encoded as a braid, and three specially designed cloaking elements. We present a heuristic algorithm that allows a passive eavesdropper to recover a substitute for the signer's private key by removing cloaking elements and then solving a system of conjugacy equations in braids. Our attack has $100\%$ success rate on randomly generated instances of the protocol. It works with braids only and its success rate is not affected by a choice of the base finite field. In particular, it has the same $100\%$ success rate for recently suggested parameters values (including a new way to generate cloaking elements, see NIST PQC forum https://groups.google.com/a/list.nist.gov/forum/#!forum/pqc-forum). Implementation of our attack in C++, as well as our implementation of the WalnutDSA protocol, is available on GitHub (https://github.com/stevens-crag/crag).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
WalnutDSAgroup-based cryptographydigital signaturealgebraic eraserbraid groupcolored Burau presentationconjugacy problem
Contact author(s)
menshov a v @ gmail com
History
2018-05-01: received
Short URL
https://ia.cr/2018/393
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/393,
      author = {Matvei Kotov and Anton Menshov and Alexander Ushakov},
      title = {AN ATTACK ON THE WALNUT DIGITAL SIGNATURE ALGORITHM},
      howpublished = {Cryptology ePrint Archive, Paper 2018/393},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/393}},
      url = {https://eprint.iacr.org/2018/393}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.