충돌 전력 분석 공격에 높은 공격 복잡도를 갖는 RSA 알고리즘에 대한 취약점 분석 및 대응기법
Analysis and Countermeasure on RSA Algorithm Having High Attack Complexity in Collision-Based Power Analysis Attack
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
부채널 분석 중 전력 분석 공격은 가장 실용적이며 강력한 기법으로 알려져 있다. 전력 분석 공격 중 단일 파형공격은 단 하나의 파형을 이용하여 공개키 암호 시스템의 비밀정보를 복원하는 강력한 분석기법으로 최근에 활발히연구되고 있다. 가장 최근에 Sim 등은 이러한 공격에 높은 안전성을 갖는 새로운 지수승 알고리즘을 소개하였다. 본 논문에서 Sim 등이 제안한 단일 파형 공격에 높은 공격 복잡도를 갖는 알고리즘의 취약점을 분석한다. 메시지블라인딩과 지수 분할 기법에 윈도우 기법을 적용해 높은 공격 복잡도를 갖는 알고리즘을 제안하였지만 사전 연산과정에서 발생하는 정보를 이용하여 비밀정보를 복원할 수 있음을 확인하였다. 또한 취약점을 보완하여 단일파형 공격에 높은 공격 복잡도를 갖는 지수승 알고리즘을 새롭게 제안하였다. 설계된 알고리즘은 사전 연산 과정에서 실제지수 연산에 사용되는 값들의 재사용을 최소화 하여 충돌 공격에 대해 높은 안전성를 보장한다.
Abstract
It is known that power analysis is one of the most powerful attack in side channel analysis. Among power analysis single trace attack is widely studied recently since it uses one power consumption trace to recover secret key of public cryptosystem. Recently Sim et al. proposed new exponentiation algorithm for RSA cryptosystem with higher attack complexity to prevent single trace attack. In this paper we analyze the vulnerability of exponentiation algorithm described by Sim et al. Sim et al. applied message blinding and random exponentiation splitting method on 2^t-ary for higher attack complexity. However we can reveal private key using information exposed during pre-computation generation. Also we describe modified algorithm that provides higher attack complexity on collision attack. Proposed algorithm minimized the reuse of value that are used during exponentiation to provide security under single collision attack.
참고문헌 (16)
- P. Kocher, "“Differential power analysis,” CRYPTO ‘99", LNCS, 1666, pp.388~397 (1999)
- P.A. Fouque, "The doubling attack – why upwards is better thatn downwards,” CHES 2003", LNCS, 2779, pp.269~280 (2003)
- C. D. Walter, "Sliding windows succumbs to big mac attack", LNCS, pp.286~299 (2001)
- H, Kim, "Message Blinding Method Requiring No Multiplicative Inversion of RSA", ACM, 13(4) (2014)
- Bauer, A., "Horizontal collision correlation attack on elliptic curves", Selected Areas in Cryptography, 8282, pp.553~570 (2013)
- 심보연, "RSA 충돌 분석 공격 복잡도 향상을 위한 연구", 정보보호학회논문지, 25(2), pp.261~270 (2015), 한국정보보호학회[DOI]
- Clavier. C, "“Horizontal correlation analysis on exponentiation,”ICICS", Lecture Notes in Computer Science, 6917, pp.46~61 (2010)
- E. Brier, "“Correlation Power Analysis with a Leakage Model,” Cryptographic Hardware and Embedded Systems -CHES", Lecture Notes in Computer Science, 3156, pp.16~29 (2004)
- P. Kocher, "“Timing Attacks on Implemntations of Diffie-Hellman, RSA, DSS and Other Systems,” Proc. CRYPTO ‘96", LNCS, 1109, pp.104~113 (1996)
- I. Biehl, "Differential Fault Attacks on Elliptic Curve Cryptosystems", CRYPTO, 1880, pp.131~146 (2000)
- Coron, J. S, "Resistance against differential power analysis for elliptic curve cryptosystems:” ASIACRYPT ‘98", LNCS, 1514, pp.51~65 (1998)
- Marc F. Witterman, "“Defeating RSA multiply-always and message blinding countermeasure,”CT-RSA 2011", LNCS, 6558, pp.77~88 (2011)
- 김희석, "Practical Second-Order Correlation Power Analysis on the Message Blinding Method and Its Novel Countermeasure for RSA", ETRI Journal, 32(1), pp.102~111 (2010), 한국전자통신연구원
- N. Hanley, "“Exploiting Collision in Addition Chain-Based Exponentiation Algorithms Using a Single Trace,”CT-RSA", LNCS, 9048, pp.431~448 (2015)
- K. Itho, "“Address-Bit Differential Power Analysis of Cryptographic Schemes OK-ECDH and OK-ECDSA,” CHES 2002", LNCS, 2523, pp.129~143 (2003)
- A. Bauer, "Horizontal Collision Correlation Attack on Elliptic Curves", SAC 2013, pp.553~570 (2014)