Paper 2020/055

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

Alejandro Cabrera Aldaya and Billy Bob Brumley


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%.

Available format(s)
Publication info
Published by the IACR in TCHES 2020
side-channel analysisvulnerable countermeasureECDSARSAbinary GCDmodular inversionIntel SGXmbedTLSand CVE-2019-18222
Contact author(s)
aldaya @ gmail com
2020-03-20: revised
2020-01-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alejandro Cabrera Aldaya and Billy Bob Brumley},
      title = {When one vulnerable primitive turns viral: Novel single-trace attacks on ECDSA and RSA},
      howpublished = {Cryptology ePrint Archive, Paper 2020/055},
      year = {2020},
      doi = {10.13154/tches.v2020.i2.196-221},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.