International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: From A to Z: Projective coordinates leakage in the wild

Authors:
Alejandro Cabrera Aldaya , Tampere University, Tampere, Finland
Cesar Pereida García , Tampere University, Tampere, Finland
Billy Bob Brumley , Tampere University, Tampere, Finland
Download:
DOI: 10.13154/tches.v2020.i3.428-453
URL: https://tches.iacr.org/index.php/TCHES/article/view/8596
Search ePrint
Search Google
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.
Video from TCHES 2020
BibTeX
@article{tches-2020-30397,
  title={From A to Z: Projective coordinates leakage in the wild},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2020, Issue 3},
  pages={428-453},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8596},
  doi={10.13154/tches.v2020.i3.428-453},
  author={Alejandro Cabrera Aldaya and Cesar Pereida García and Billy Bob Brumley},
  year=2020
}