Paper 2016/1195

Constant-Time Callees with Variable-Time Callers

Cesar Pereida Garcïa and Billy Bob Brumley

Abstract

Side-channel attacks are a serious threat to security-critical software. To mitigate remote timing and cache-timing attacks, many ubiquitous cryptography software libraries feature constant-time implementations of cryptographic primitives. In this work, we disclose a vulnerability in OpenSSL 1.0.1u that recovers ECDSA private keys for the standardized elliptic curve P-256 despite the library featuring both constant-time curve operations and modular inversion with microarchitecture attack mitigations. Exploiting this defect, we target the errant modular inversion code path with a cache-timing and improved performance degradation attack, recovering the inversion state sequence. We propose a new approach of extracting a variable number of nonce bits from these sequences, and improve upon the best theoretical result to recover private keys in a lattice attack with as few as 50 signatures and corresponding traces. As far as we are aware, this is the first timing attack against OpenSSL ECDSA that does not target scalar multiplication, the first side-channel attack on cryptosystems leveraging P-256 constant-time scalar multiplication and furthermore, we extend our attack to TLS and SSH protocols, both linked to OpenSSL for P-256 ECDSA signing.

Note: As appears in USENIX Security 17

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. The 26th USENIX Security Symposium USENIX Security 17
Keywords
applied cryptographyelliptic curve cryptographydigital signaturesside-channel analysistiming attackscache-timing attacksperformance degradationECDSAmodular inversionbinary extended Euclidean algorithmlattice attacksconstant-time softwareOpenSSLNIST P-256CVE-2016-7056
Contact author(s)
cesar pereidagarcia @ tut fi
History
2017-08-29: last of 2 revisions
2017-01-01: received
See all versions
Short URL
https://ia.cr/2016/1195
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1195,
      author = {Cesar Pereida Garcïa and Billy Bob Brumley},
      title = {Constant-Time Callees with Variable-Time Callers},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1195},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1195}},
      url = {https://eprint.iacr.org/2016/1195}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.