Skip to main content
CSIRO Logo Data 61 logo

Sliding right into disaster: left-to-right sliding windows leak

Authors

Daniel J. Bernstein, Joachim Breitner, Daniel Genkin, Leon Groot Bruinderink, Nadia Heninger, Tanja Lange, Christine van Vredendaal and Yuval Yarom

Eindhoven Technical University

DATA61

University of Pennsylvania

University of Pennsylvania & University of Maryland

The University of Adelaide

Abstract

It is well known that constant-time implementations of modular exponentiation cannot use sliding windows. However, software libraries such as Libgcrypt, used by GnuPG, continue to use sliding windows. It is widely believed that, even if the complete pattern of squarings and multiplications is observed through a side-channel attack, the number of exponent bits leaked is not sufficient to carry out a full key-recovery attack against RSA. Specifically, 4-bit sliding windows leak only 40% of the bits, and 5-bit sliding windows leak only 33% of the bits. In this paper we demonstrate a complete break of RSA-1024 as implemented in Libgcrypt. Our attack makes essential use of the fact that Libgcrypt uses the left-to-right method for computing the sliding-window expansion. We show for the first time that the direction of the encoding matters: the pattern of squarings and multiplications in left-to-right sliding windows leaks significantly more information about the exponent than right-to-left. We show how to extend the Heninger-Shacham algorithm for partial key reconstruction to make use of this information and obtain a very efficient full key recovery for RSA-1024. For RSA-2048 our attack is efficient for 13% of keys

BibTeX Entry

  @inproceedings{Bernstein_BGGHLVY_17,
    year             = {2017},
    month            = sep,
    pages            = {555-576},
    publisher        = {Springer},
    paperurl         = {https://ts.data61.csiro.au/publications/csiro_full_text/Bernstein_BGGHLVY_17.pdf},
    booktitle        = {Workshop on Cryptographic Hardware and Embedded Systems},
    author           = {Bernstein, Daniel J. and Breitner, Joachim and Genkin, Daniel and Groot Bruinderink, Leon and
                        Heninger, Nadia and Lange, Tanja and van Vredendaal, Christine and Yarom, Yuval},
    address          = {Taipei, Taiwan},
    title            = {Sliding Right Into Disaster: Left-to-right sliding windows leak},
    date             = {2017-9-25}
  }

Download