Cryptology ePrint Archive: Report 2018/687

Assessing the Feasibility of Single Trace Power Analysis of Frodo

Joppe W. Bos and Simon Friedberger and Marco Martinoli and Elisabeth Oswald and Martijn Stam

Abstract: Lattice-based schemes are among the most promising post-quantum schemes, yet the effect of both parameter and implementation choices on their side-channel resilience is still poorly understood. Aysu et al. (HOST'18) recently investigated single-trace attacks against the core lattice operation, namely multiplication between a public matrix and a "small" secret vector, in the context of a hardware implementation. We complement this work by considering single-trace attacks against software implementations of "ring-less" LWE-based constructions. Specifically, we target Frodo, one of the submissions to the standardisation process of NIST, when implemented on an (emulated) ARM Cortex M0 processor. We confirm Aysu et al.'s observation that a standard divide-and-conquer attack is insufficient and instead we resort to a sequential, extend-and-prune approach. In contrast to Aysu et al. we find that, in our setting where the power model is far from being as clear as theirs, both profiling and less aggressive pruning are needed to obtain reasonable key recovery rates for SNRs of practical relevance. Our work drives home the message that parameter selection for LWE schemes is a double-edged sword: the schemes that are deemed most secure against (black-box) lattice attacks can provide the least security when considering side-channels. Finally, we suggest some easy countermeasures that thwart standard extend-and-prune attacks.

Category / Keywords: implementation / Side-channel analysis, LWE, Frodo, Template attacks, Lattices

Original Publication (with minor differences): Selected Areas in Cryptography (SAC) 2018

Date: received 17 Jul 2018

Contact author: marco martinoli at bristol ac uk

Available format(s): PDF | BibTeX Citation

Version: 20180717:140011 (All versions of this report)

Short URL: ia.cr/2018/687


[ Cryptology ePrint archive ]