Paper 2016/231

Side-Channel Analysis of Weierstrass and Koblitz Curve ECDSA on Android Smartphones

Pierre Belgarric, Pierre-Alain Fouque, Gilles Macario-Rat, and Mehdi Tibouchi

Abstract

In this paper, we study the side-channel resistance of the implementation of the ECDSA signature scheme in Android's standard cryptographic library. We show that, for elliptic curves over prime fields, one can recover the secret key very efficiently on smartphones using electromagnetic side-channel and well-known lattice reduction techniques. We experimentally show that elliptic curve operations (doublings and additions) can be distinguished in a multi-core CPU clocking over the giga-hertz. We then extend the standard lattice attack on ECDSA over prime fields to binary Koblitz curves. This is the first time that such an attack is described on Koblitz curves. These curves, which are also available in Bouncy Castle, allow very efficient implementations using the Frobenius operation. This leads to signal processing challenges since the number of available points are reduced. We investigate practical side-channel, showing the concrete vulnerability of such implementations. In comparison to previous works targeting smartphones, the attacks presented in the paper benefits from discernible architectural features, like specific instructions computations or memory accesses.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Major revision. CT-RSA 2016
DOI
10.1007/978-3-319-29485-8_14
Keywords
Side-Channel AnalysisElliptic Curve CryptographySmartphonesLattice-Based Cryptanalysis
Contact author(s)
tibouchi mehdi @ lab ntt co jp
History
2016-03-02: received
Short URL
https://ia.cr/2016/231
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/231,
      author = {Pierre Belgarric and Pierre-Alain Fouque and Gilles Macario-Rat and Mehdi Tibouchi},
      title = {Side-Channel Analysis of Weierstrass and Koblitz Curve ECDSA on Android Smartphones},
      howpublished = {Cryptology ePrint Archive, Paper 2016/231},
      year = {2016},
      doi = {10.1007/978-3-319-29485-8_14},
      note = {\url{https://eprint.iacr.org/2016/231}},
      url = {https://eprint.iacr.org/2016/231}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.