Impeccable Keccak

Towards Fault Resilient SPHINCS+ Implementations

Abstract

The standardization of the hash-based digital signature scheme SPHINCS⁺ proceeds faster than initially expected. This development seems to be welcomed by practitioners who appreciate the high confidence in SPHINCS⁺’s security assumptions and its reliance on well-known hash functions. However, the implementation security of SPHINCS⁺ leaves many questions unanswered, due to its proneness to fault injection attacks. Previous works have shown, that even imprecise fault injections on the signature generation are sufficient for universal forgery. This led the SPHINCS⁺ team to promote the usage of hardware countermeasures against such attacks. Since the majority of operations in SPHINCS⁺ is dedicated to the computation of the Keccak function, we focus on its security. At the core, hardware countermeasures against fault injection attacks are almost exclusively based on redundancy. For hash functions such as Keccak, straightforward instance- or time-redundancy is expensive in terms of chip area or latency. Further, for applications that must withstand powerful fault adversaries, these simple forms of redundancy are not sufficient. To this end, we propose our impeccable Keccak design. It is based on the methodology presented in the original Impeccable Circuits paper by Aghaie et al. from 2018. On the way, we show potential pitfalls when designing impeccable circuits and how the concept of active security can be applied to impeccable circuits. To the best of our knowledge, we are the first to provide proofs of active security for impeccable circuits. Further, we show a novel way to implement non-linear functions without look-up tables. We use our findings to design an impeccable Keccak. Assuming an adversary with the ability to flip single bits, our design detects all attacks with three and less flipped bits. Attacks from adversaries who are able to flip four or more bits are still detected with a high probability. Thus, our design is one of the most resilient designs published so far and the only Keccak design that is provably secure within a bit-flip model. At an area overhead of factor 3.2, our design is competitive with state-of-the-art designs with less resilience.