Cryptology ePrint Archive: Report 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, and furthermore the first side-channel attack on cryptosystems leveraging P-256 constant-time scalar multiplication.

Category / Keywords: public-key cryptography / applied cryptography; elliptic curve cryptography; digital signatures; side-channel analysis; timing attacks; cache-timing attacks; performance degradation; ECDSA; modular inversion; binary extended Euclidean algorithm; lattice attacks; constant-time software; OpenSSL; NIST P-256; CVE-2016-7056

Date: received 31 Dec 2016, last revised 1 Jan 2017

Contact author: cesar pereidagarcia at tut fi

Available format(s): PDF | BibTeX Citation

Note: Appendix with fix added.

Version: 20170101:154002 (All versions of this report)

Short URL: ia.cr/2016/1195

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]