Paper 2022/1254

Protecting the most significant bits in scalar multiplication algorithms

Estuardo Alpirez Bock, Aalto University
Lukasz Chmielewski, Masaryk University, Radboud University Nijmegen
Konstantina Miteloudi, Radboud University Nijmegen
Abstract

The Montgomery Ladder is widely used for implementing the scalar multiplication in elliptic curve cryptographic designs. This algorithm is efficient and provides a natural robustness against (simple) side-channel attacks. Previous works however showed that implementations of the Montgomery Ladder using Lopez-Dahab projective coordinates easily leak the value of the most significant bits of the secret scalar, which led to a full key recovery in an attack known as LadderLeak. In light of such leakage, we analyse further popular methods for implementing the Montgomery Ladder. We first consider open source software implementations of the X25519 protocol which implement the Montgomery Ladder based on the ladderstep algorithm from Düll et al. [15]. We confirm via power measurements that these implementations also easily leak the most significant scalar bits, even when implementing Z-coordinate ran- domisations. We thus propose simple modifications of the algorithm and its handling of the most significant bits and show the effectiveness of our modifications via experimental results. Particularly, our re-designs of the algorithm do not incurring significant efficiency penalties. As a second case study, we consider open source hardware implementations of the Montgomery Ladder based on the complete addition formulas for prime order elliptic curves, where we observe the exact same leakage. As we explain, the most significant bits in implementations of the complete addition formulas can be protected in an analogous way as we do for Curve25519 in our first case study.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
ECC Montgomery Ladder Curve25519 Complete addition formulas Side-channel analysis
Contact author(s)
estuardo alpirezbock @ gmail com
chmiel @ fi muni cz
konstantina miteloudi @ ru nl
History
2022-09-26: approved
2022-09-21: received
See all versions
Short URL
https://ia.cr/2022/1254
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1254,
      author = {Estuardo Alpirez Bock and Lukasz Chmielewski and Konstantina Miteloudi},
      title = {Protecting the most significant bits in scalar multiplication algorithms},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1254},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1254}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.