Generic cryptanalysis of combined countermeasures with randomized BSD representations

Tae Hyun Kim; Dong Guk Han; Katsuyuki Okeya; Jongin Lim

doi:10.1007/11733447_9

Generic cryptanalysis of combined countermeasures with randomized BSD representations

Tae Hyun Kim^*
, Dong Guk Han
, Katsuyuki Okeya
, Jongin Lim

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

In ICICS'04, Sim et al. proposed an attack against the full version of Ha-Moon's countermeasure which is one of enhanced counter-measures. The analysis technique is based on the fact that the probability for the appearance of an intermediate value is p = 1/2. By our simulations, however, it is proven to be not true. Thus sometimes the output of their attack might be wrong because there exists the case that the probability p is so small that they can make a wrong decision. In this paper we repair the above attack, and then propose a generic analytical technique applicable to all BSD type countermeasures combined with some simple power analysis countermeasures. In order to show that the proposed attack is as practical as the usual differential power analysis (DPA), we estimate the number of samples and computational cost. Furthermore, we enhance the proposed attack in two ways such that it works against right-to-left algorithm in a simpler and more efficient way, and also works against one combined with an extra DPA countermeasure.

Original language	English
Title of host publication	Smart Card Research and Advanced Applications - 7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006, Proceedings
Editors	Josep Domingo-Ferrer, Joachim Posegga, Daniel Schreckling
Publisher	Springer Verlag
Pages	119-134
Number of pages	16
ISBN (Print)	3540333118, 9783540333111
DOIs	https://doi.org/10.1007/11733447_9
Publication status	Published - 2006
Event	7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006 - Tarargona, Spain Duration: 2006 Apr 19 → 2006 Apr 21

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3928 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006
Country/Territory	Spain
City	Tarargona
Period	06/4/19 → 06/4/21

Keywords

Binary Signed Digit (BSD) Representation
Differential Power Analysis
Elliptic Curve Cryptosystems
Refined Power Analysis
Side Channel Attack

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11733447_9

Cite this

Kim, T. H., Han, D. G., Okeya, K., & Lim, J. (2006). Generic cryptanalysis of combined countermeasures with randomized BSD representations. In J. Domingo-Ferrer, J. Posegga, & D. Schreckling (Eds.), Smart Card Research and Advanced Applications - 7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006, Proceedings (pp. 119-134). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3928 LNCS). Springer Verlag. https://doi.org/10.1007/11733447_9

Generic cryptanalysis of combined countermeasures with randomized BSD representations. / Kim, Tae Hyun; Han, Dong Guk; Okeya, Katsuyuki et al.
Smart Card Research and Advanced Applications - 7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006, Proceedings. ed. / Josep Domingo-Ferrer; Joachim Posegga; Daniel Schreckling. Springer Verlag, 2006. p. 119-134 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3928 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kim, TH, Han, DG, Okeya, K & Lim, J 2006, Generic cryptanalysis of combined countermeasures with randomized BSD representations. in J Domingo-Ferrer, J Posegga & D Schreckling (eds), Smart Card Research and Advanced Applications - 7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3928 LNCS, Springer Verlag, pp. 119-134, 7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006, Tarargona, Spain, 06/4/19. https://doi.org/10.1007/11733447_9

Kim TH, Han DG, Okeya K, Lim J. Generic cryptanalysis of combined countermeasures with randomized BSD representations. In Domingo-Ferrer J, Posegga J, Schreckling D, editors, Smart Card Research and Advanced Applications - 7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006, Proceedings. Springer Verlag. 2006. p. 119-134. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11733447_9

Kim, Tae Hyun ; Han, Dong Guk ; Okeya, Katsuyuki et al. / Generic cryptanalysis of combined countermeasures with randomized BSD representations. Smart Card Research and Advanced Applications - 7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006, Proceedings. editor / Josep Domingo-Ferrer ; Joachim Posegga ; Daniel Schreckling. Springer Verlag, 2006. pp. 119-134 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8ac661a3171c43c1a5edb7a8d300c064,

title = "Generic cryptanalysis of combined countermeasures with randomized BSD representations",

abstract = "In ICICS'04, Sim et al. proposed an attack against the full version of Ha-Moon's countermeasure which is one of enhanced counter-measures. The analysis technique is based on the fact that the probability for the appearance of an intermediate value is p = 1/2. By our simulations, however, it is proven to be not true. Thus sometimes the output of their attack might be wrong because there exists the case that the probability p is so small that they can make a wrong decision. In this paper we repair the above attack, and then propose a generic analytical technique applicable to all BSD type countermeasures combined with some simple power analysis countermeasures. In order to show that the proposed attack is as practical as the usual differential power analysis (DPA), we estimate the number of samples and computational cost. Furthermore, we enhance the proposed attack in two ways such that it works against right-to-left algorithm in a simpler and more efficient way, and also works against one combined with an extra DPA countermeasure.",

keywords = "Binary Signed Digit (BSD) Representation, Differential Power Analysis, Elliptic Curve Cryptosystems, Refined Power Analysis, Side Channel Attack",

author = "Kim, \{Tae Hyun\} and Han, \{Dong Guk\} and Katsuyuki Okeya and Jongin Lim",

year = "2006",

doi = "10.1007/11733447\_9",

language = "English",

isbn = "3540333118",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "119--134",

editor = "Josep Domingo-Ferrer and Joachim Posegga and Daniel Schreckling",

booktitle = "Smart Card Research and Advanced Applications - 7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006, Proceedings",

}

TY - GEN

T1 - Generic cryptanalysis of combined countermeasures with randomized BSD representations

AU - Kim, Tae Hyun

AU - Han, Dong Guk

AU - Okeya, Katsuyuki

AU - Lim, Jongin

PY - 2006

Y1 - 2006

N2 - In ICICS'04, Sim et al. proposed an attack against the full version of Ha-Moon's countermeasure which is one of enhanced counter-measures. The analysis technique is based on the fact that the probability for the appearance of an intermediate value is p = 1/2. By our simulations, however, it is proven to be not true. Thus sometimes the output of their attack might be wrong because there exists the case that the probability p is so small that they can make a wrong decision. In this paper we repair the above attack, and then propose a generic analytical technique applicable to all BSD type countermeasures combined with some simple power analysis countermeasures. In order to show that the proposed attack is as practical as the usual differential power analysis (DPA), we estimate the number of samples and computational cost. Furthermore, we enhance the proposed attack in two ways such that it works against right-to-left algorithm in a simpler and more efficient way, and also works against one combined with an extra DPA countermeasure.

AB - In ICICS'04, Sim et al. proposed an attack against the full version of Ha-Moon's countermeasure which is one of enhanced counter-measures. The analysis technique is based on the fact that the probability for the appearance of an intermediate value is p = 1/2. By our simulations, however, it is proven to be not true. Thus sometimes the output of their attack might be wrong because there exists the case that the probability p is so small that they can make a wrong decision. In this paper we repair the above attack, and then propose a generic analytical technique applicable to all BSD type countermeasures combined with some simple power analysis countermeasures. In order to show that the proposed attack is as practical as the usual differential power analysis (DPA), we estimate the number of samples and computational cost. Furthermore, we enhance the proposed attack in two ways such that it works against right-to-left algorithm in a simpler and more efficient way, and also works against one combined with an extra DPA countermeasure.

KW - Binary Signed Digit (BSD) Representation

KW - Differential Power Analysis

KW - Elliptic Curve Cryptosystems

KW - Refined Power Analysis

KW - Side Channel Attack

UR - https://www.scopus.com/pages/publications/33745776291

U2 - 10.1007/11733447_9

DO - 10.1007/11733447_9

M3 - Conference contribution

AN - SCOPUS:33745776291

SN - 3540333118

SN - 9783540333111

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 119

EP - 134

BT - Smart Card Research and Advanced Applications - 7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006, Proceedings

A2 - Domingo-Ferrer, Josep

A2 - Posegga, Joachim

A2 - Schreckling, Daniel

PB - Springer Verlag

T2 - 7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006

Y2 - 19 April 2006 through 21 April 2006

ER -

Generic cryptanalysis of combined countermeasures with randomized BSD representations

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this