Cryptology ePrint Archive: Report 2019/769

Exploiting Determinism in Lattice-based Signatures - Practical Fault Attacks on pqm4 Implementations of NIST candidates

Prasanna Ravi and Mahabir Prasad Jhanwar and James Howe and Anupam Chattopadhyay and Shivam Bhasin

Abstract: In this paper, we analyze the implementation level fault vulnerabilities of deterministic lattice-based signature schemes. In particular, we extend the practicality of skip-addition fault attacks through exploitation of determinism in certain variants of Dilithium (Deterministic variant) and qTESLA signature scheme (originally submitted deterministic version), which are two leading candidates for the NIST standardization of post-quantum cryptography. We show that single targeted faults injected in the signing procedure allow to recover an important portion of the secret key. Though faults injected in the signing procedure do not recover all the secret key elements, we propose a novel forgery algorithm that allows the attacker to sign any given message with only the extracted portion of the secret key. We perform experimental validation of our attack using Electromagnetic fault injection on reference implementations taken from the pqm4 library, a benchmarking and testing framework for post quantum cryptographic implementations for the ARM Cortex-M4 microcontroller. We also show that our attacks break two well known countermeasures known to protect against skip-addition fault attacks. We further propose an efficient mitigation strategy against our attack that exponentially increases the attacker's complexity at almost zero increase in computational complexity.

Category / Keywords: public-key cryptography / Deterministic Lattice Signatures, pqm4, Fault Attack, Lattice-based Cryptography, Dilithium, qTESLA

Original Publication (with minor differences): AsiaCCS-2019

Date: received 1 Jul 2019

Contact author: PRASANNA RAVI at ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20190702:143146 (All versions of this report)

Short URL: ia.cr/2019/769


[ Cryptology ePrint archive ]