Software-Induced Fault Attacks on Post-Quantum Signature Schemes

Islam, Saad

Etd

Software-Induced Fault Attacks on Post-Quantum Signature Schemes

Public

A digital signature is a digital equivalent of a handwritten signature or stamp which is used to validate the authenticity and integrity in digital communications like an email, a credit card transaction or a digital document. Digital signatures are mathematical schemes whose security is based on conjectured hard problems like discrete log or RSA moduli factorization. Unfortunately, these public-key cryptosystems are not quantum secure and large scale quantum computers will be able to solve the underlying hard problems. In 2021, IBM has released "Eagle", a 127-qubit quantum processor and has a roadmap of 1K-1M+ qubits beyond 2024. NIST has already realized the quantum threat and announced a competition for Post-Quantum Cryptography Standardization Process in 2016. It is currently in round 3 and expected to be finalized with the announcement of KEM and Digital Signature standards by the end of 2022. Apart from algorithmic security, significant attention has been given to implementation attacks such as side-channel and fault attacks. To counter classical Differential Fault Attacks (DFA), which only work for deterministic schemes, the schemes are now offering randomized versions. The goal of this dissertation is to investigate these randomized postquantum signature schemes against fault attacks. The study has identified a number of vulnerabilities in several post-quantum schemes in the NIST competition. We are able to recover the entire key of the LUOV (round 2 finalist) signature scheme in less than 4 hours of Rowhammer attack, followed by our novel bit-tracing algorithm and divide and conquer attack. We have named this hybrid attack QuantumHammer. More recently, we have proposed the "Signature Correction Attack" on the Dilithium signature scheme (round 3 finalist) and successfully reduced its security strength from 128-bit to 81-bit. Rowhammer attack does not require physical access and poses a significant threat to shared cloud servers. The identified vulnerabilities are however generic and can work as long as required faulty signatures are collected using any fault mechanism. The main idea of both bit-tracing and signature correction is to utilize a single faulty signature to mathematically trace back to the fault, revealing the secret key bit. We achieve this by trying to correct a faulty signature for all possible faults in the secret key using the verification algorithm as an oracle. This technique does not need any correct signature counterpart as needed in traditional DFA attacks. In all of our Rowhammer experiments on post-quantum schemes, we have used SPOILER for finding contiguous memory required for double-sided Rowhammer. SPOILER is a hardware bug we discovered in all Intel generations, starting from 1st Gen (2008) of Intel core processors, stemming from the speculative load operations. SPOILER reveals critical physical address information to user space processes which boosts Rowhammer and cache attacks.

Creator