Paper 2005/316

Collision Attack on XTR and a Countermeasure with a Fixed Pattern

Dong-Guk Han, Tsuyoshi Takagi, Tae Hyun Kim, Ho Won Kim, and Kyo Il Chung

Abstract

Public-key cryptosystem (PKC) is one of inevitable key technologies in order to accomplish fruitful security applications in ubiquitous computing systems. The ubiquitous computer only has scarce computational resources (like Smart cards, RFID, Sensor Network), however, so that the light weight PKC is necessary for those miniaturized low-power devices. Recently, XTR is considered as one of good candidates for more energy efficient cryptosystems. Among XTR exponentiation algorithms, the most efficient one is the Improved XTR Single Exponentiation (XTR-ISE) proposed by Stam-Lenstra. Thus among the family of XTR algorithms, XTR-ISE is the most efficient one suitable for ubiquitous computer. Even though the security of such devices against side channel attacks is very dangerous, there are few works on side channel attacks against XTR-ISE. In this paper we propose a new collision attack on XTR-ISE, derived from the structural properties of XTR-ISE. The analysis complexity of the proposed one is about 2^{40} where the key size is 160-bit, which is 55% improvement from the previously best known analysis of Page-Stam. We also propose a novel countermeasure using a fixed pattern which is secure against SPA. We deploy a variant of Euclidean algorithm whose one of the registers is a monotone decreasing function with odd value. From our estimation of the efficiency of the proposed method, XTR exponentiation, computing Tr(g^n) with Tr(g) and n, takes 11.2log_2n multiplications in F_{p^2}. In the sense of both efficiency and security the proposed countermeasure is the best one among the previous countermeasures- it is about 30% faster.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. This is a ``full" version of a paper that will be published in SecUbiq 2005.
Keywords
Side Channel AttacksXTR public key system
Contact author(s)
christa @ fun ac jp
History
2005-09-12: received
Short URL
https://ia.cr/2005/316
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/316,
      author = {Dong-Guk Han and Tsuyoshi Takagi and Tae Hyun Kim and Ho Won Kim and Kyo Il Chung},
      title = {Collision Attack on {XTR} and a Countermeasure with a Fixed Pattern},
      howpublished = {Cryptology {ePrint} Archive, Paper 2005/316},
      year = {2005},
      url = {https://eprint.iacr.org/2005/316}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.