Cryptanalysis of SFLASH

SFLASH [Spec] is a fast asymmetric signature scheme intended for low cost smart cards without cryptoprocessor. It belongs to the family of multivariate asymmetric schemes. It was submitted to the call for cryptographic primitives organised by the European project NESSIE, and successfully passed the first phase of the NESSIE selection process in September 2001. In this paper, we present a cryptanalysis of SFLASH which allows an adversary provided with an SFLASH public key to derive a valid signature of any message. The complexity of the attack is equivalent to less than 238 computations of the public function used for signature verification. The attack does not appear to be applicable to the FLASH companion algorithm of SFLASH and to the modified (more conservative) version of SFLASH proposed in October 2001 to the NESSIE project by the authors of SFLASH in replacement of [Spec].