Paper 2021/1677

Improving Support-Minors rank attacks: applications to G$e$MSS and Rainbow

John Baena, Universidad Nacional de Colombia
Pierre Briaud, French Institute for Research in Computer Science and Automation
Daniel Cabarcas, Universidad Nacional de Colombia
Ray Perlner, National Institute of Standards and Technology
Daniel Smith-Tone, National Institute of Standards and Technology, University of Louisville
Javier Verbel, Technology Innovation Institute
Abstract

The Support-Minors (SM) method has opened new routes to attack multivariate schemes with rank properties that were previ- ously impossible to exploit, as shown by the recent attacks of Tao at al. (CRYPTO 2021) and Beullens (EUROCRYPT 2021) on the Round 3 NIST candidates GeMSS and Rainbow respectively. In this paper, we study this SM approach more in depth and we propose a greatly improved attack on GeMSS based on this Support-Minors method. Even though GeMSS was already affected by Tao's attack, our attack affects it even more and makes it completely unfeasible to repair the scheme by simply increasing the size of its parameters or even applying the recent projection technique from Øygarden et al. (PQCrypto 2021) whose purpose was to make GeMSS immune to Tao's attack. For instance, our attack on the GeMSS128 parameter set has estimated time complexity 2^72 , and repairing the scheme by applying projection would result in a signature with slower signing time by an impractical factor of 2^14 . Another contribution is to suggest optimizations that can reduce memory access costs for an XL strategy on a large SM system using the Block-Wiedemann algorithm as subroutine when these costs are a concern. In a memory cost model based on the one provided by Bernstein et al. (https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf), we show that the rectangular MinRank attack of Beullens may indeed reduce the security for all Round 3 Rainbow parameter sets below their targeted security strengths, contradicting the lower bound claimed by the Rainbow team using the same memory cost model (https://troll.iis.sinica.edu.tw/by-publ/recent/response-ward.pdf).

Note: Update (16/02/2022): we added a Section 7 containing Magma experiments for our GeMSS attack and some parts of Section 8 have been revised. Update (20/06/2022) : major change. Appendix B now contains a detailed analysis of some neglected costs in the model from Section 8. Long version of a paper presented at CRYPTO 2022.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. CRYPTO 2022
Keywords
Support-Minors GeMSS Rainbow multivariate cryptography
Contact author(s)
jbbaena @ unal edu co
pierre briaud @ inria fr
dcabarc @ unal edu co
ray perlner @ nist gov
dcs xmr @ gmail com
javier verbel @ tii ae
History
2022-06-21: last of 5 revisions
2021-12-21: received
See all versions
Short URL
https://ia.cr/2021/1677
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1677,
      author = {John Baena and Pierre Briaud and Daniel Cabarcas and Ray Perlner and Daniel Smith-Tone and Javier Verbel},
      title = {Improving Support-Minors rank attacks: applications to G$e${MSS} and Rainbow},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1677},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1677}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.