From A to Z: Projective coordinates leakage in the wild

  • Alejandro Cabrera Aldaya Tampere University, Tampere, Finland
  • Cesar Pereida García Tampere University, Tampere, Finland
  • Billy Bob Brumley Tampere University, Tampere, Finland
Keywords: applied cryptography, projective coordinates leak, open source libraries, side-channel analysis, ECDSA, modular inversion, binary GCD, libgcrypt, CVE-2020-10932, CVE-2020-11735

Abstract

At EUROCRYPT 2004, Naccache et al. showed that the projective coordinates representation of the resulting point of an elliptic curve scalar multiplication potentially allows to recover some bits of the scalar. However, this attack has received little attention by the scientific community, and the status of deployed mitigations to prevent it in widely adopted cryptography libraries is unknown. In this paper, we aim to fill this gap, by analyzing several cryptography libraries in this context. To demonstrate the applicability of the attack, we use a side-channel attack to exploit this vulnerability within libgcrypt in the context of ECDSA. To the best of our knowledge, this is the first practical attack instance. It targets the insecure binary extended Euclidean algorithm implementation using a microarchitectural side-channel attack that allows recovering the projective representation of the output point of scalar multiplication during ECDSA signature generation. We captured 100k traces to estimate the number of traces an attacker would need to compromise the libgcrypt ECDSA implementation, resulting in less than 2k for commonly used elliptic curve secp256r1, demonstrating the attack feasibility. During exploitation, we found two additional vulnerabilities. However, we remark the purpose of this paper is not merely exploiting a library but about providing an analysis on the projective coordinates vulnerability status in widely deployed open-source libraries, filling a gap between its original description in the academic literature and the adoption of countermeasures to thwart it in real-world applications.

Published
2020-06-19
How to Cite
Cabrera Aldaya, A., Pereida García, C., & Brumley, B. B. (2020). From A to Z: Projective coordinates leakage in the wild. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(3), 428-453. https://doi.org/10.13154/tches.v2020.i3.428-453
Section
Articles