Paper 2017/806

May the Fourth Be With You: A Microarchitectural Side Channel Attack on Several Real-World Applications of Curve25519

Daniel Genkin, Luke Valenta, and Yuval Yarom

Abstract

In recent years, applications increasingly adopt security primitives designed with better countermeasures against side channel attacks. A concrete example is Libgcrypt's implementation of ECDH encryption with Curve25519. The implementation employs the Montgomery ladder scalar-by-point multiplication, uses the unified, branchless Montgomery double-and-add formula and implements a constant-time argument swap within the ladder. However, Libgcrypt's field arithmetic operations are not implemented in a constant-time side-channel-resistant fashion. Based on the secure design of Curve25519, users of the curve are advised that there is no need to perform validation of input points. In this work we demonstrate that when this recommendation is followed, the mathematical structure of Curve25519 facilitates the exploitation of side-channel weaknesses. We demonstrate the effect of this vulnerability on three software applications---encrypted git, email and messaging---that use Libgcrypt. In each case, we show how to craft malicious OpenPGP files that use the Curve25519 point of order 4 as a chosen ciphertext to the ECDH encryption scheme. We find that the resulting interactions of the point at infinity, order-2, and order-4 elements in the Montgomery ladder scalar-by-point multiplication routine create side channel leakage that allows us to recover the private key in as few as 11 attempts to access such malicious files.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. ACM Conference on Computer and Communications Security (CCS) 2017
DOI
10.1145/3133956.3134029
Keywords
Side Channel AttacksCurve25519Cache-AttacksFlush+ReloadOrder-4 Elements
Contact author(s)
danielg3 @ cis upenn edu
History
2017-08-28: received
Short URL
https://ia.cr/2017/806
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/806,
      author = {Daniel Genkin and Luke Valenta and Yuval Yarom},
      title = {May the Fourth Be With You: A Microarchitectural Side Channel Attack on Several Real-World Applications of Curve25519},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/806},
      year = {2017},
      doi = {10.1145/3133956.3134029},
      url = {https://eprint.iacr.org/2017/806}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.