×

An attack on the Walnut digital signature algorithm. (English) Zbl 1419.94040

Summary: 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.

MSC:

94A60 Cryptography
68W30 Symbolic computation and algebraic computation

Software:

WalnutDSA; GitHub; CRAG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anshel I., Atkins D., Goldfeld P., Gunnels D.: The Walnut digital signature algorithm(TM) specification. Submitted to NIST PQC project (2017). Available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions, accessed 4 April 2018.
[2] Anshel I., Atkins D., Goldfeld P., Gunnels D.: Kayawood, a key agreement protocol. Preprint. Available at https://eprint.iacr.org/2017/1162 (version: 30-Nov-2017) (2017).
[3] Anshel I., Atkins D., Goldfeld P., Gunnels D.: WalnutDSA(TM): a quantum-resistant digital signature algorithm. Preprint. Available at https://eprint.iacr.org/2017/058 (version: 30-Nov-2017) (2017).
[4] Beullens W., Blackburn S.R.: Practical attacks against the Walnut digital signature scheme. Preprint. Available at https://eprint.iacr.org/2018/318/20180404:153741 (2018). · Zbl 1446.94101
[5] Birman J.S., Ko K.H., Lee S.J.: A new approach to the word and conjugacy problems in the braid groups. Adv. Math. 139, 322-353 (1998). · Zbl 0937.20016 · doi:10.1006/aima.1998.1761
[6] CRyptography And Groups (CRAG) C++ Library. Available at https://github.com/stevens-crag/crag.
[7] Dehornoy P.: A fast method for comparing braids. Adv. Math. 125, 200-235 (1997). · Zbl 0882.20021 · doi:10.1006/aima.1997.1605
[8] Epstein D.B.A., Cannon J.W., Holt D.F., Levy S.V.F., Paterson M.S., Thurston W.P.: Word Processing in Groups. Jones and Bartlett Publishers, Burlington (1992). · Zbl 0764.20017 · doi:10.1201/9781439865699
[9] Gebhardt V.: A new approach to the conjugacy problem in garside groups. J. Algebra 292, 282-302 (2005). · Zbl 1105.20032 · doi:10.1016/j.jalgebra.2005.02.002
[10] Hart D., Kim D., Micheli G., Perez G.P., Petit C., Quek Y.: A practical cryptanalysis of WalnutDSA. In: Public-key cryptography—PKC 2018, pp. 381-406. Springer, New York (2018). · Zbl 1385.94043
[11] Kapovich I.E., Miasnikov A.G., Schupp P.E., Shpilrain V.E.: Generic-case complexity, decision problems in group theory and random walks. J. Algebra 264, 665-694 (2003). · Zbl 1041.20021 · doi:10.1016/S0021-8693(03)00167-4
[12] Kotov M.V., Menshov A.V., Ushakov A.V.: Attack on Kayawood protocol: uncloaking private keys. Preprint. Available at https://eprint.iacr.org/2018/604 (version: 18-Jun-2018) (2018). · Zbl 1466.94032
[13] NIST PQC forum. Available at https://groups.google.com/a/list.nist.gov/forum/#!forum/pqc-forum, accessed April 4 2018 (2018).
[14] Miasnikov A.G., Shpilrain V.E., Ushakov A.V.: A practical attack on some braid group based cryptographic protocols. In: Advances in Cryptology—CRYPTO 2005, volume 3621 of Lecture Notes on Computer Science, pp. 86-96. Springer, Berlin (2005). · Zbl 1145.94448
[15] Miasnikov A.G., Shpilrain V.E., Ushakov A.V.: Random subgroups of braid groups: an approach to cryptanalysis of a braid group based cryptographic protocol. In: Advances in Cryptology—PKC 2006, volume 3958 of Lecture Notes on Computer Science, pp. 302-314. Springer, Berlin (2006). · Zbl 1151.94554
[16] Miasnikov A.G., Shpilrain V.E., Ushakov A.V.: Non-commutative Cryptography and Complexity of Group-Theoretic Problems. Mathematical Surveys and Monographs. AMS, Providence (2011). · Zbl 1248.94006
[17] Paterson M.S., Razborov A.A.: The set of minimal braids is co-NP-complete. J. Algorithms 12, 393-408 (1991). · Zbl 0726.68047 · doi:10.1016/0196-6774(91)90011-M
[18] Wang, J.: Average-case completeness of a word problem for groups. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’95, pp. 325-334. ACM (1995). · Zbl 0968.68535
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.