Cryptanalysis of the countermeasures using randomized binary signed digits

Dong Guk Han, Katsuyuki Okeya, Tae Hyun Kim, Yoon Sung Hwang, Young Ho Park, Souhwan Jung

Research output: Chapter in Book/Report/Conference proceedingChapter

3 Citations (Scopus)

Abstract

Recently, side channel attacks (SCA) have been recognized as menaces to public key cryptosystems. In SCA, an attacker observes side channel information during cryptographic operations, and reveals the secret scalar using the side channel information. On the other hand, elliptic curve cryptosystems (ECC) are suitable for implementing on smartcards. Since a scalar multiplication is a dominant step in ECC, we need to design an algorithm to compute scalar multiplication with the immunity to SCA. For this purpose, several scalar multiplication methods that utilize randomized binary-signed-digit (BSD) representations were proposed. This type of countermeasures includes Ha-Moon's countermeasure, Ebeid-Hasan's one, and Agagliate's one. In this paper we propose a novel general attack against "all" the countermeasures of this type. The proposed attack lists the candidates for the secret scalar, however straight-forward approach requires huge memory, thus it is infeasible. The proposed attack divides the table into small tables, which reduces the memory requirement. For example, the computational cost and the memory requirement of the proposed attack for revealing the 163-bit secret key are O(28) and O(223), respectively, using 20 observations on the scalar multiplication with Ha-Moon's countermeasure. The computational cost and the memory requirement are O(221) and O(212) for Ebeid-Hasan's one, and O(240) and O(26) for Agagliate's one. If 40 observations are used, computational cost for Agagliate's one is reduced to O(233). Whenever we utilize a countermeasure of BSD type, we should beware of the proposed attack. In other words, the security of BSD type is controversial.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsMarkus Jakobsson, Moti Yung, Jianying Zhou
PublisherSpringer Verlag
Pages398-413
Number of pages16
ISBN (Print)3540222170, 9783540222170
DOIs
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3089
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Agagliate's Countermeasure
  • BSD Representation
  • DPA
  • Ebeid-Hasan's Countermeasure
  • Elliptic Curve Cryptosystem
  • Ha-Moon's Countermeasure
  • SPA
  • Side Channel Attacks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Cryptanalysis of the countermeasures using randomized binary signed digits'. Together they form a unique fingerprint.

Cite this