Cryptology ePrint Archive: Report 2021/1222

Fault-enabled chosen-ciphertext attacks on Kyber

Julius Hermelink and Peter Pessl and Thomas Pöppelmann

Abstract: NIST's PQC standardization process is in the third round, and a first final choice between one of three remaining lattice-based key encapsulation mechanisms is expected by the end of 2021. This makes studying the implementation-security aspect of the candidates a pressing matter. However, while the development of side-channel attacks and corresponding countermeasures has seen continuous interest, fault attacks are still a vastly underdeveloped field.

In fact, a first practical fault attack on lattice-based KEMs was demonstrated just very recently by Pessl and Prokop. However, while their attack can bypass some standard fault countermeasures, it may be defeated using shuffling, and their use of skipping faults makes it also highly implementation dependent. Thus, the vulnerability of implementations against fault attacks and the concrete need for countermeasures is still not well understood.

In this work, we shine light on this problem and demonstrate new attack paths. Concretely, we show that the combination of fault injections with chosen-ciphertext attacks is a significant threat to implementations and can bypass several countermeasures. We state an attack on Kyber which combines ciphertext manipulation - flipping a single bit of an otherwise valid ciphertext - with a fault that "corrects" the ciphertext again during decapsulation. By then using the Fujisaki-Okamoto transform as an oracle, i.e., observing whether or not decapsulation fails, we derive inequalities involving secret data, from which we may recover the private key. Our attack is not defeated by many standard countermeasures such as shuffling in time or Boolean masking, and the fault may be introduced over a large execution-time interval at several places. In addition, we improve a known recovery technique to efficiently and practically recover the secret key from a smaller number of inequalities compared to the previous method.

Category / Keywords: public-key cryptography / Kyber, NTT, belief propagation, side-channel attack, CCA

Original Publication (in the same form): INDOCRYPT 2021

Date: received 17 Sep 2021, last revised 25 Oct 2021

Contact author: julius hermelink at unibw de, peter pessl at infineon com, thomas poeppelmann at infineon com

Available format(s): PDF | BibTeX Citation

Version: 20211025:085535 (All versions of this report)

Short URL: ia.cr/2021/1222


[ Cryptology ePrint archive ]