An attack on the Walnut digital signature algorithm

Matvei Kotov, Anton Menshov, Alexander Ushakov

Research output: Contribution to journalArticle

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 updated parameters values (including a new way to generate cloaking elements, see NIST Post-quantum Cryptography Forum). Implementation of our attack in C++, as well as our implementation of the WalnutDSA protocol, is available on GitHub.

Original languageEnglish (US)
JournalDesigns, Codes, and Cryptography
DOIs
StatePublished - Jan 1 2019

Fingerprint

Electronic document identification systems
Digital Signature
Braid
Attack
Network protocols
Quantum Cryptography
Public key cryptography
Quantum cryptography
Heuristic algorithms
Public Key Cryptography
Braid Group
Conjugacy
Substitute
C++
Heuristic algorithm
Assign
Galois field
Finite Set
Multiplication
Signature

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Computer Science Applications

Cite this

@article{034675359fea4ed1a56ee5990444f532,
title = "An attack on the Walnut digital signature algorithm",
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 updated parameters values (including a new way to generate cloaking elements, see NIST Post-quantum Cryptography Forum). Implementation of our attack in C++, as well as our implementation of the WalnutDSA protocol, is available on GitHub.",
author = "Matvei Kotov and Anton Menshov and Alexander Ushakov",
year = "2019",
month = "1",
day = "1",
doi = "https://doi.org/10.1007/s10623-019-00615-y",
language = "English (US)",
journal = "Designs, Codes, and Cryptography",
issn = "0925-1022",
publisher = "Springer Netherlands",

}

An attack on the Walnut digital signature algorithm. / Kotov, Matvei; Menshov, Anton; Ushakov, Alexander.

In: Designs, Codes, and Cryptography, 01.01.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An attack on the Walnut digital signature algorithm

AU - Kotov, Matvei

AU - Menshov, Anton

AU - Ushakov, Alexander

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 updated parameters values (including a new way to generate cloaking elements, see NIST Post-quantum Cryptography Forum). Implementation of our attack in C++, as well as our implementation of the WalnutDSA protocol, is available on GitHub.

AB - 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 updated parameters values (including a new way to generate cloaking elements, see NIST Post-quantum Cryptography Forum). Implementation of our attack in C++, as well as our implementation of the WalnutDSA protocol, is available on GitHub.

UR - http://www.scopus.com/inward/record.url?scp=85061256482&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85061256482&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/s10623-019-00615-y

DO - https://doi.org/10.1007/s10623-019-00615-y

M3 - Article

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

SN - 0925-1022

ER -