모듈라 곱셈의 충돌 입력에 기반한 부채널 공격 및 대응책
Side-Channel Analysis Based on Input Collisions in Modular Multiplications and its Countermeasure
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
전력 분석 공격은 물리적 장치에 내장된 암호 알고리듬을 수행할 때 발생하는 부채널 전력 정보를 이용하여 사용자의비밀 키를 찾아내는 공격 기법이다. 특히, RSA와 같은 공개 키 암호 시스템에 사용되는 멱승은 수백 번의 모듈라 곱셈으로 이루어져 있는데 이 연산이 전력 분석 공격의 목표가 되어 왔다. 최근에는 동일한 입력을 가지는 두 개의 모듈라곱셈에서 발생한 전력의 상관 분석을 통해 비밀 키를 추출하는 공격이 제안되었다. 본 논문에서는 모듈라 곱셈의 입력충돌에 기반한 부채널 공격의 원리를 살펴보고 정규화 특성을 갖는 멱승 알고리듬에 대한 취약성을 분석하였다. 또한,충돌 입력쌍을 이용한 상관 전력 분석 공격을 포함한 기존 부채널 공격에 대응할 수 있는 효율적인 멱승 방법을 제안하고 안전성을 비교 분석하였다.
Abstract
The power analysis attack is a cryptanalytic technique to retrieve an user's secret key using the side-channel power leakageoccurred during the execution of cryptographic algorithm embedded on a physical device. Especially, many power analysisattacks have targeted on an exponentiation algorithm which is composed of hundreds of squarings and multiplications andadopted in public key cryptosystem such as RSA. Recently, a new correlation power attack, which is tried when two modularmultiplications have a same input, is proposed in order to recover secret key. In this paper, after reviewing the principle ofside-channel attack based on input collisions in modular multiplications, we analyze the vulnerability of some exponentiationalgorithms having regularity property. Furthermore, we present an improved exponentiation countermeasure to resist against theinput collision-based CPA(Correlation Power Analysis) attack and existing side channel attacks and compare its security withother countermeasures.
참고문헌 (22)
- 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)
- Advanced Encryption Standards, "National Institute of Standards", NIST, ~, pp.NIST FIPS PUB 197 (2001)
- R. Rivest, "A method for obtaining digital signature and public-key cryptosystems", Comm. of the ACM, 21, pp.120~126 (1978)
- W. Diffie, "New directions in cryptography", IEEE 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. Fouque, "“The doubling attack- why upwards is better than downwards,”CHES'03", LNCS, 2779, pp.269~280 (2003)
- E. Brier, "Correlation power analysis with a leakage model", LNCS, 3156, pp.135~152 (2004)
- S. Yen, "“A countermeasure against one physical cryptanalysis may benefit another attack,”ICISC’01", LNCS, 2288, pp.414~427 (2001)
- F. Amiel, "Passive and Active Combined Attacks: Combining fault attacks and side channel analysis", FDTC'07, IEEE-CS, pp.92~102 (2007)
- 김형동, "BNP 멱승 알고리듬에 대한 물리적인 조합 공격 및 대응책", 정보보호학회논문지, 23(4), pp.585~591 (2013), 한국정보보호학회[DOI]
- M. Witteman, "Defeating RSA Multiply-Always and Message Blinding Countermeasures", LNCS, 6558, pp.77~88 (2011)
- Side-channel analysis on blinded regular scalar multiplications, "B. Feix", Cryptology ePrint Archive, ~, pp.Cryptology ePrint Archive, Report 2014 (2014), 191
- D. Knuth, "The Art of Programming, Vol 2: Seminumerical Algorithms" (1981), Addison-Wesley
- S. Yen, "“Relative doubling attack against Montgomery ladder,” ICISC'05", LNCS, 3935, pp.117~128 (2005)
- C. Clavier, "“Square Always exponentiation,”INDOCRYPT’11", LNCS, 7107, pp.40~57 (2011)
- P. Montgomery, "Modular multipli cation without trial division", Math. of Comp., 44(170), pp.519~521 (1985)
- 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)
- A. Boscher, ""CRT-RSA Algorithm Protected Against Fault Attacks," WISTP'07", LNCS, 4462, pp.237~252 (2007)
- H. Kim, "A New Exponentiation Algorithm Resistant to Combined Side Channel Attack", Journal of Internet Services and Information Security, 3(3, pp.4) (2013), 17~27