Paper 2018/367

Cache-Timing Attacks on RSA Key Generation

Alejandro Cabrera Aldaya, Cesar Pereida García, Luis Manuel Alvarez Tapia, and Billy Bob Brumley

Abstract

During the last decade, constant-time cryptographic software has quickly transitioned from an academic construct to a concrete security requirement for real-world libraries. Most of OpenSSL's constant-time code paths are driven by cryptosystem implementations enabling a dedicated flag at runtime. This process is perilous, with several examples emerging in the past few years of the flag either not being set or software defects directly mishandling the flag. In this work, we propose a methodology to analyze security-critical software for side-channel insecure code path traversal. Applying our methodology to OpenSSL, we identify three new code paths during RSA key generation that potentially leak critical algorithm state. Exploiting one of these leaks, we design, implement, and mount a single trace cache-timing attack on the GCD computation step. We overcome several hurdles in the process, including but not limited to: (1) granularity issues due to word-size operands to the GCD function; (2) bulk processing of desynchronized trace data; (3) non-trivial error rate during information extraction; and (4) limited high-confidence information on the modulus factors. Formulating lattice problem instances after obtaining and processing this limited information, our attack achieves roughly a 27% success rate for key recovery using the empirical data from 10K trials.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCHES 2019
DOI
10.13154/tches.v2019.i4.213-242
Keywords
applied cryptographypublic key cryptographyRSAside-channel analysistiming attackscache-timing attacksOpenSSLCVE-2018-0737
Contact author(s)
aldaya @ gmail com
History
2020-03-20: last of 2 revisions
2018-04-24: received
See all versions
Short URL
https://ia.cr/2018/367
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/367,
      author = {Alejandro Cabrera Aldaya and Cesar Pereida García and Luis Manuel Alvarez Tapia and Billy Bob Brumley},
      title = {Cache-Timing Attacks on RSA Key Generation},
      howpublished = {Cryptology ePrint Archive, Paper 2018/367},
      year = {2018},
      doi = {10.13154/tches.v2019.i4.213-242},
      note = {\url{https://eprint.iacr.org/2018/367}},
      url = {https://eprint.iacr.org/2018/367}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.