Welcome to the resource topic for 2005/316
Title:
Collision Attack on XTR and a Countermeasure with a Fixed Pattern
Authors: Dong-Guk Han, Tsuyoshi Takagi, Tae Hyun Kim, Ho Won Kim, 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.
ePrint: https://eprint.iacr.org/2005/316
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .