Horizontal Side-Channel Vulnerabilities of Post-Quantum Key Exchange and Encapsulation Protocols
Authors:
Open Access
- 18 October 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 20 (6) , 1-22
Abstract
Key exchange protocols and key encapsulation mechanisms establish secret keys to communicate digital information confidentially over public channels. Lattice-based cryptography variants of these protocols are promising alternatives given their quantum-cryptanalysis resistance and implementation efficiency. Although lattice cryptosystems can be mathematically secure, their implementations have shown side-channel vulnerabilities. But such attacks largely presume collecting multiple measurements under a fixed key, leaving the more dangerous single-trace attacks unexplored. This article demonstrates successful single-trace power side-channel attacks on lattice-based key exchange and encapsulation protocols. Our attack targets both hardware and software implementations of matrix multiplications used in lattice cryptosystems. The crux of our idea is to apply a horizontal attack that makes hypotheses on several intermediate values within a single execution all relating to the same secret, and to combine their correlations for accurately estimating the secret key. We illustrate that the design of protocols combined with the nature of lattice arithmetic enables our attack. Since a straightforward attack suffers from false positives, we demonstrate a novel extend-and-prune procedure to recover the key by following the sequence of intermediate updates during multiplication. We analyzed two protocols, Frodo and FrodoKEM , and reveal that they are vulnerable to our attack. We implement both stand-alone hardware and RISC-V based software realizations and test the effectiveness of the proposed attack by using concrete parameters of these protocols on physical platforms with real measurements. We show that the proposed attack can estimate secret keys from a single power measurement with over 99% success rate.Keywords
Funding Information
- National Science Foundation (#1453806, #1314709, #1527888, #1441484, #1850373, and CCF-1901446)
- Semiconductor Research Corporation
This publication has 40 references indexed in Scilit:
- A Masked Ring-LWE Implementation2015
- Horizontal Collision Correlation Attack on Elliptic Curves2014
- First-order collision attack on protected NTRU cryptosystemMicroprocessors and Microsystems, 2013
- Power Analysis Attacks and Countermeasures on NTRU-Based Wireless Body Area NetworksKSII Transactions on Internet and Information Systems, 2013
- Cross-VM side channels and their use to extract private keys2012
- Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware2012
- On lattices, learning with errors, random linear codes, and cryptographyJournal of the ACM, 2009
- Correlation Power Analysis with a Leakage Model2004
- The Doubling Attack – Why Upwards Is Better than Downwards2003
- Algorithms for quantum computation: discrete logarithms and factoring2002