Square Always 멱승 알고리듬에 대한 부채널 공격
Side-Channel Attacks on Square Always Exponentiation Algorithm
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
정보보호를 위한 암호 시스템을 임베디드 장치에서 개발할 경우 발생할 수 있는 구현상의 문제점을 이용하여 비밀키를 추출하기 위한 여러 부채널 공격들이 시도되어 왔다. 특히, 공개 키 암호 시스템에서 사용하는 멱승(exponentiation) 연산은 기본적으로 곱셈과 자승으로 구현되어 왔으나, 최근 부채널 공격에 대응하기 위한 방법으로 곱셈을 자승 연산으로 대체하는 새로운 Square Always 멱승 알고리듬이 제안되었다. 본 논문에서는 현재까지 부채널 공격에 안전하다고 알려진 Right-to-Left형태의 Square Always 멱승 알고리듬을 공격할 수 있는 기지 전력충돌 분석(Known Power Collision Analysis) 공격과 변형된 Doubling 공격을 제안한다. 또한, 오류 주입 공격후 충돌 쌍을 찾아내는 전력 분석 기법을 이용하여 비밀 키를 찾아낼 수 있는 충돌 기반의 조합 공격(Collision-basedCombined Attack)을 제안한다. 그리고 Square Always 멱승 알고리듬이 제안한 부채널 공격들에 의해 취약한 특성을 가지고 있음을 컴퓨터 시뮬레이션을 통해 확인하였다.
Abstract
Based on some flaws occurred for implementing a public key cryptosystem in the embeddedsecurity device, many side-channel attacks to extract the secret private key have been tried. Inspite of the fact that the cryptographic exponentiation is basically composed of a sequence ofmultiplications and squarings, a new Square Always exponentiation algorithm was recentlypresented as a countermeasure against side-channel attacks based on trading multiplications forsquarings. In this paper, we propose Known Power Collision Analysis and modified Doublingattacks to break the Right-to-Left Square Always exponentiation algorithm which is knownresistant to the existing side-channel attacks. And we also present a Collision-based CombinedAttack which is a combinational method of fault attack and power collision analysis. Furthermore, we verify that the Square Always algorithm is vulnerable to the proposedside-channel attacks using computer simulation.
참고문헌 (21)
- R. Rivest, "A method for obtaining digital signature and public-key cryptosystems", Comm. of the ACM, 21(2), pp.120~126 (1978)
- W. Diffie, "New directions in cryptography", Transactions on Information Theory, IT-22(6), pp.644~654 (1976)
- D. Gordon, "A survey of fast exponentiation methods", Journal of Algorithms, 27, pp.129~146 (1998)
- P. Kocher, ""Timing Attacks on Implementation of Diffie-Hellman, RSA, DSS, and Other Systems," CRYPTO'96", LNCS, 1109, pp.104~113 (1996)
- P. Kocher, "“Differential power analysis," CRYPTO'99", LNCS, 1666, pp.388~397 (1999)
- D. Boneh, "“On the Importance of Checking Cryptographic Protocols for Faults,"EUROCRYPTO'97", LNCS, 1233, pp.37~51 (1997)
- M. Joye, "“RSA-type signatures in the presence of transient faults,"Cryptography and Coding", LNCS, 1355, pp.109~121 (1997)
- M. Witteman, "Defeating RSA Multiply-Always and Message Blinding Countermeasures", LNCS, 6558, pp.77~88 (2011)
- P. Fouque, "The doubling attack- why upwards is better than downwards", LNCS, 2779, pp.269~280 (2003)
- S. Yen, "Relative doubling attack against Montgomery ladder", LNCS, 3935, pp.117~128 (2005)
- S. Yen, "A countermeasure against one physical cryptanalysis may benefit another attack", LNCS, 2288, pp.414~427 (2002)
- F. Amiel, "Passive and Active Combined Attacks: Combining fault attacks and side channel analysis", FDTC'07, IEEE-CS, 92(102), pp.92~102 (2007)
- 김형동, "BNP 멱승 알고리듬에 대한 물리적인 조합 공격 및 대응책", 정보보호학회논문지, 23(4), pp.585~591 (2013), 한국정보보호학회[DOI]
- C. Clavier, "“Square Always exponentiation,” INDOCRYPT’11", LNCS, 7107, pp.40~57 (2011)
- J. Coron, "“Resistance against differential power analysis for elliptic curve cryptosystems,”CHES'99", LNCS, 1717, pp.292~302 (1999)
- M. Joye, ""The Montgomery Powering Ladder," CHES'02", LNCS, 2523, pp.291~302 (2002)
- B. Chevallier-Mames, "Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity", IEEE Trans. on Computers, 53(6), pp.760~768 (2004)
- F. Amiel, ""Distinguishing Multiplications from Squaring Operations," SAC'08", LNCS, 5381, pp.346~360 (2009)
- C. Couvreur, "Fast decipherment algorithm for RSA public-key cryptosystem", Electronics Letters, 18(21), pp.905~907 (1982)
- A. Boscher, ""CRT-RSA Algorithm Protected Against Fault Attacks," WISTP'07", LNCS, 4462, pp.237~252 (2007)