Cryptology ePrint Archive: Report 2020/055

When one vulnerable primitive turns viral: Novel single-trace attacks on ECDSA and RSA

Alejandro Cabrera Aldaya and Billy Bob Brumley

Abstract: Microarchitecture based side-channel attacks are common threats nowadays. Intel SGX technology provides a strong isolation from an adversarial OS, however, does not guarantee protection against side-channel attacks. In this paper, we analyze the security of the mbedTLS binary GCD algorithm, an implementation that offers interesting challenges when compared for example with OpenSSL, due to the usage of very tight loops in the former. Using practical experiments we demonstrate the mbedTLS binary GCD implementation is vulnerable to side-channel analysis using the SGX-Step framework against mbedTLS based SGX enclaves.

We analyze the security of some use cases of this algorithm in this library, resulting in the discovery of a new vulnerability in the ECDSA code path that allows a single-trace attack against this implementation. This vulnerability is three-fold interesting:

* It resides in the implementation of a countermeasure which makes it more dangerous due to the false state of security the countermeasure currently offers.

* It reduces mbedTLS ECDSA security to an integer factorization problem.

* An unexpected GCD call inside the ECDSA code path compromises the countermeasure.

We also cover an orthogonal use case, this time inside the mbedTLS RSA code path during the computation of a CRT parameter when loading a private key. The attack also exploits the binary GCD implementation threat, showing how a single vulnerable primitive leads to multiple vulnerabilities. We demonstrate both security threats with end-to-end attacks using 1000 trials each, showing in both cases single-trace attacks can be achieved with success rates very close to 100%.

Category / Keywords: implementation / side-channel analysis, vulnerable countermeasure, ECDSA, RSA, binary GCD, modular inversion, Intel SGX, mbedTLS, and CVE-2019-18222

Original Publication (in the same form): IACR-CHES-2020
DOI:
10.13154/tches.v2020.i2.196-221

Date: received 17 Jan 2020, last revised 20 Mar 2020

Contact author: aldaya at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200320:075851 (All versions of this report)

Short URL: ia.cr/2020/055


[ Cryptology ePrint archive ]