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).