Paper 2011/271

Practical Key-recovery For All Possible Parameters of SFLASH

Charles Bouillaguet, Pierre-Alain Fouque, and Gilles Macario-Rat

Abstract

In this paper we present a new practical key-recovery attack on the SFLASH signature scheme. SFLASH is a derivative of the older $C^*$ encryption and signature scheme that was broken in 1995 by Patarin. In SFLASH, the public key is truncated, and this simple countermeasure prevents Patarin's attack. The scheme is well-known for having been considered secure and selected in 2004 by the NESSIE project of the European Union to be standardized. However, SFLASH was practically broken in 2007 by Dubois, Fouque, Stern and Shamir. Their attack breaks the original (and most relevant) parameters, but does not apply when more than half of the public key is truncated. It is therefore possible to choose parameters such that SFLASH is not broken by the existing attacks, although it is less efficient. We show a key-recovery attack that breaks the full range of parameters in practice, as soon as the information-theoretically required amount of information is available from the public-key. The attack uses new cryptanalytic tools, most notably pencils of matrices and quadratic forms.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
SFLASHmultivariate cryptographypractical cryptanalysiskey-recovery
Contact author(s)
charles bouillaguet @ ens fr
History
2011-05-28: received
Short URL
https://ia.cr/2011/271
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/271,
      author = {Charles Bouillaguet and Pierre-Alain Fouque and Gilles Macario-Rat},
      title = {Practical Key-recovery For All Possible Parameters of SFLASH},
      howpublished = {Cryptology ePrint Archive, Paper 2011/271},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/271}},
      url = {https://eprint.iacr.org/2011/271}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.