TY - CHAP
T1 - Cryptanalysis of the countermeasures using randomized binary signed digits
AU - Han, Dong Guk
AU - Okeya, Katsuyuki
AU - Kim, Tae Hyun
AU - Hwang, Yoon Sung
AU - Park, Young Ho
AU - Jung, Souhwan
PY - 2004
Y1 - 2004
N2 - 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.
AB - 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.
KW - Agagliate's Countermeasure
KW - BSD Representation
KW - DPA
KW - Ebeid-Hasan's Countermeasure
KW - Elliptic Curve Cryptosystem
KW - Ha-Moon's Countermeasure
KW - SPA
KW - Side Channel Attacks
UR - http://www.scopus.com/inward/record.url?scp=33646776521&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-24852-1_29
DO - 10.1007/978-3-540-24852-1_29
M3 - Chapter
AN - SCOPUS:33646776521
SN - 3540222170
SN - 9783540222170
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 398
EP - 413
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Jakobsson, Markus
A2 - Yung, Moti
A2 - Zhou, Jianying
PB - Springer Verlag
ER -