The prospect of large-scale quantum computers threatens currently used asymmetric cryptography -- Shor's algorithm could render commonly used cryptography unsafe. In 2022, the National Institute for Standards and Technology (NIST) announced several quantum-secure cryptographic algorithms for key exchanges and digital signatures for standardization, and three out of four are based on hard lattice problems. The main candidate for key exchanges is a key encapsulation mechanism called Kyber, which bases its security on the Module Learning with Errors problem. In contrast to quantum cryptography, these post-quantum algorithms run on classical computers and currently available hardware. Data that is encrypted now often needs to be secured for a long time. In addition, potentially vulnerable cryptography is present in many products, protocols, and use cases; therefore, deploying different algorithms is a difficult task that could take a substantial amount of time and effort. Clearly, migrating to quantum-safe cryptography cannot wait until large-scale quantum computers are available. Thus, and due to the imminent standardization, lattice-based cryptography is likely to run on a wide variety of devices in the near future. In this work, we present attack strategies against lattice-based cryptography. Our attack strategies combine chosen-ciphertext attacks with side-channel analysis as well as with fault attacks and target two major components of the decapsulation that process the secret key. Moreover, we present techniques to recover the secret key from the obtained information and show how to combine those methods with algebraic approaches. We first present an attack strategy on the number theoretic transform: A chosen ciphertext is pre-computed such that it cancels out values during the inverse number theoretic transform that processes the secret key. The reduced entropy allows for an improved subsequent side-channel analysis. Using our technique, the number theoretic transform can be targeted with highly increased noise tolerance. We take countermeasures into account and state techniques that enable the adaptation of belief-propagation-based attacks to protected settings. Then, we target the error correction and the Fujiskai-Okamoto transform. We show how a fault may turn the Fujisaki-Okamoto transform into a decryption failure oracle; this enables a chosen-ciphertext attack targeting the error correction. Our fault-enabled chosen-ciphertext attack requires an adversary to target only public data, may be administered in various locations, and allows the use of an unreliable fault. In addition, we show how belief propagation can be employed to recover the secret key from decryption failure information. We then propose using a combination of countermeasures to mitigate our attack strategy. Finally, we explain how to recover the secret key from decryption failure information in an error-resistant way that also allows for security estimates. We modify the belief-propagation-based approach to achieve error-resistance and explain how belief propagation may be combined with lattice reduction. Our method outperforms previous algorithms in terms of required information, is error-tolerant, and allows for security estimates in cases where the secret key cannot be fully recovered. These security estimates enable the design and evaluation of countermeasures and provide an assessment of the impact of several attacks that exploit decryption failures.    «

The prospect of large-scale quantum computers threatens currently used asymmetric cryptography -- Shor's algorithm could render commonly used cryptography unsafe. In 2022, the National Institute for Standards and Technology (NIST) announced several quantum-secure cryptographic algorithms for key exchanges and digital signatures for standardization, and three out of four are based on hard lattice problems. The main candidate for key exchanges is a key encapsulation mechanism called Kyber, whi...    »