참조 테이블 기반 스칼라 곱 알고리즘에 대한 충돌 특성을 이용한 향상된 수평상관분석
An Improved Horizontal Correlation Analysis Using Collision Characteristics on Lookup Table Based Scalar Multiplication Algorithms
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
FBC(Fixed-Base Comb)는 사전계산된 참조 테이블을 활용하여 ECDSA(Elliptic Curve DigitalSignature Algorithm) 서명 생성의 핵심 연산인 스칼라 곱을 효율적으로 연산하는 방법이다. FBC는 비밀정보에의존하여 테이블을 참조하고 테이블의 값은 공개되어 있기 때문에 단일파형 부채널 공격 기법인 수평상관분석(HCA, Horizontal Correlation Analysis)에 의해 그 비밀정보가 드러날 수 있다. 그러나 HCA는 통계 분석의일종으로 하나의 스칼라 곱 파형으로부터 충분한 수의 단위 연산 파형을 얻을 수 있어야만 공격에 성공할 수 있다. ECDSA 서명 생성에 쓰이는 스칼라 곱의 경우 RSA 거듭제곱에 비해 HCA에 이용 가능한 단위 연산 파형의 수가현저히 적어 공격에 실패할 수 있다. 본 논문에서는 FBC와 같은 참조 테이블 기반 스칼라 곱에 대하여 향상된HCA를 제안한다. 제안하는 기법은 충돌 분석으로 중간값이 같은 단위 연산 파형을 식별함으로써 공격에 이용되는단위 연산 파형의 수를 증가시켜 HCA의 공격 성능을 향상시킨다. 제안하는 기법은 사용된 타원곡선 파라미터의 보안 강도가 높을수록 공격 성능이 향상하는 특징이 있다.
Abstract
The FBC(Fixed-Base Comb) is a method to efficiently operate scalar multiplication, a core operation for signaturegenerations of the ECDSA(Elliptic Curve Digital Signature Algorithm), utilizing precomputed lookup tables. Since the FBCrefers to the table depending on the secret information and the values of the table are publicly known, an adversary canperform HCA(Horizontal Correlation Analysis), one of the single trace side channel attacks, to reveal the secret. However,HCA is a statistical analysis that requires a sufficient number of unit operation traces extracted from one scalarmultiplication trace for a successful attack. In the case of the scalar multiplication for signature generations of ECDSA, thenumber of unit operation traces available for HCA is significantly fewer than the case of the RSA exponentiation, possiblyresulting in an unsuccessful attack. In this paper, we propose an improved HCA on lookup table based scalar multiplicationalgorithms such as FBC. The proposed attack improves HCA by increasing the number of unit operation traces bydetermining such traces for the same intermediate value through collision analysis. The performance of the proposed attackincreases as more secure elliptic curve parameters are used.
참고문헌 (17)
- National Institute of Standards and Technology, "Digital Signature Standard (DSS)", FIPS 186-4, ~ (2013)
- D. Hankerson, "Guide to elliptic curve cryptography", pp.75~186 (2004), Springer
- "openssl software library"[URL]
- "gnupg software library"[URL]
- "bitcoin core software library"[URL]
- E. Brier, "Correlation power analysis with a leakage model", LNCS, 3156, pp.16~29 (2004)
- K. Gandolfi, "Electromagnetic analysis: concrete results", LNCS, 2162, pp.251~261 (2001)
- T. Kim, "Breaking Korea transit card with side-channel attack – Unauthorized recharging", Blackhat Asia, ~ (2017)
- K. Kim, "AES wireless keyboard - template attack for Eavesdropping", Blackhat Asia, ~ (2018)
- P. Kocher, "Differential power analysis", LNCS, 1666, pp.388~397 (1999)
- C. Clavier, "Horizontal correlation analysis on exponentiation", LNCS, 6476, pp.46~61 (2010)
- N. Hanley, "Exploiting collisions in addition chain-based exponentiation algorithms using a single trace", LNCS, 9048, pp.431~448 (2015)
- H. M. Edwards, "A normal form for elliptic curves", Bulletin of the American Mathematical Society, 44(3), pp.393~422 (2007)
- A. Bauer, "Horizontal collision correlation attack on elliptic curves", Cryptography and Communications, 7(1), pp.91~119 (2015)
- J. S. Coron, "Resistance against differential power analysis for elliptic curve cryptosystems", LNCS, 1717, pp.292~302 (1999)
- M. Joye, "The Montgomery powering ladder", LNCS, 2523, pp.291~302 (2002)
- B. Gierlichs, "Templates vs. stochastic methods", LNCS, 4249, pp.15~29 (2006)