Cryptology ePrint Archive: Report 2018/102

Grafting Trees: a Fault Attack against the SPHINCS framework

Laurent Castelnovi and Ange Martinelli and Thomas Prest

Abstract: Because they require no assumption besides the preimage or collision resistance of hash functions, hash-based signatures are a unique and very attractive class of post-quantum primitives. Among them, the schemes of the SPHINCS family are arguably the most practical stateless schemes, and can be implemented on embedded devices such as FPGAs or smart cards. This naturally raises the question of their resistance to implementation attacks.

In this paper, we propose the first fault attack against the framework underlying SPHINCS, Gravity-SPHINCS and SPHINCS+. Our attack allows to forge any message signature at the cost of a single faulted message. Furthermore, the fault model is very reasonable and the faulted signatures remain valid, which renders our attack both stealthy and practical. As the attack involves a non-negligible computational cost, we propose a fine-grained trade-off allowing to lower this cost by slightly increasing the number of faulted messages. Our attack is generic in the sense that it does not depend on the underlying hash function(s) used.

Category / Keywords: SPHINCS; Fault attacks; Hash-based signatures

Original Publication (in the same form): PQCrypto 2018

Date: received 23 Jan 2018, last revised 13 Apr 2018

Contact author: thomas prest at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20180413:184852 (All versions of this report)

Short URL: ia.cr/2018/102


[ Cryptology ePrint archive ]