Paper 2024/1297

Improved Cryptanalysis of SNOVA

Abstract

SNOVA is a multivariate signature scheme submitted to the NIST project for additional signature schemes by Cho, Ding, Kuan, Li, Tseng, Tseng, and Wang. With small key and signature sizes good performance, SNOVA is one of the more efficient schemes in the competition, which makes SNOVA an important target for cryptanalysis. In this paper, we observe that SNOVA implicitly uses a structured version of the ``whipping'' technique developed for the MAYO signature scheme. We show that the extra structure makes the construction vulnerable to new forgery attacks. Concretely, we formulate new attacks that reduce the security margin of the proposed SNOVA parameter sets by a factor between $2^{8}$ and $2^{39}$. Furthermore, we show that large fractions of public keys are vulnerable to more efficient versions of our attack. For example, for SNOVA-37-17-2, a parameter set targeting NIST's first security level, we show that roughly one out of every $500$ public keys is vulnerable to a universal forgery attack with bit complexity $2^{97}$, and roughly one out of every $143000$ public keys is even breakable in practice within a few minutes.

Note: 20/8/2024: Fix typo in affiliation.