Assessing the Feasibility of Single Trace Power Analysis of Frodo

Joppe W. Bos, Simon Friedberger, Marco Martinoli, 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.

Available format(s)
Category
Implementation
Publication info
Published elsewhere. MINOR revision.Selected Areas in Cryptography (SAC) 2018
Keywords
Side-channel analysisLWEFrodoTemplate attacksLattices
Contact author(s)
marco martinoli @ bristol ac uk
History
Short URL
https://ia.cr/2018/687

CC BY

BibTeX

@misc{cryptoeprint:2018/687,
author = {Joppe W.  Bos and Simon Friedberger and Marco Martinoli and Elisabeth Oswald and Martijn Stam},
title = {Assessing the Feasibility of Single Trace Power Analysis of Frodo},
howpublished = {Cryptology ePrint Archive, Paper 2018/687},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/687}},
url = {https://eprint.iacr.org/2018/687}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.