부채널 분석에 안전한 하드웨어 이진 스칼라 곱셈 알고리즘에 대한 단일 파형 비밀 키 비트 종속 공격

국문 초록 (Abstract)

타원 곡선 암호 시스템의 주요 연산이 스칼라 곱셈 알고리즘[5]은 부채널 분석에 취약함이 보고되어 왔다. 특히 알고리즘이 수행되는 동안 소비되는 전력 패턴 및 방출되는 전자파 패턴을 활용하는 부채널 분석에 취약하다. 이에 다양한 대응 기법이 연구되어 왔으나 데이터 종속 분기 유형, 중간 값에 따른 통계 특성 또는 데이터 간의 상호 관계 기반 공격에 대한 대응 기법 등 주 연산에 대한 대응 기법만 연구되어 왔을 뿐 비밀 키 비트 확인 단계에 대한 대응 기법은 연구되지 않았다. 이에 본 논문에서는 하드웨어로 구현된 이진 스칼라 곱셈 알고리즘에 대한 단일 파형비밀 키 비트 종속 공격을 수행하여 전력 및 전자 파형을 이용하여 100% 성공률로 비밀 스칼라 비트를 찾을 수 있음을 보인다. 실험은 차분 전력 분석 대응 기법이 적용된 Montgomery-López-Dahab ladder 스칼라 곱셈 알고리즘[13]을 대상으로 한다. 정교한 사전 전처리가 필요하지 않고 단일 파형만으로도 공격이 가능한 강력한 공격으로 기존 대응 기법을 무력화 시킬 수 있다. 따라서 이에 대한 대응 기법을 제시하고 이를 적용해야 함을 시사한다.

다국어 초록 (Multilingual Abstract)

Binary scalar multiplication which is the main operation of elliptic curve cryptography is vulnerable to the side-channel analysis. Especially, it is vulnerable to the side-channel analysis which uses power consumption and electromagnetic emission patterns. Thus, various countermeasures have been studied. However, they have focused on eliminating patterns of data dependent branches, statistical characteristic according to intermediate values, or the interrelationships between data. No countermeasure have been taken into account for the secure design of the key bit check phase, although the secret scalar bits are directly loaded during that phase. Therefore, in this paper, we demonstrate that we can extract secret scalar bits with 100% success rate using a single power or a single electromagnetic trace by performing key bit-dependent attack on hardware implementation of binary scalar multiplication algorithm. Experiments are focused on the Montgomery-López-Dahab ladder algorithm protected by scalar randomization. Our attack does not require sophisticated pre-processing and can defeat existing countermeasures using a single-trace. As a result, we propose a countermeasure and suggest that it should be applied.

목차 (Table of Contents)

• 요약
• ABSTRACT
• I. 서론
• II. 사전연구
• III. 비밀 키 비트 종속 공격
• IV. 단일 파형을 이용한 비밀 키 비트 종속 공격 실험 결과
• V. 단일 파형을 이용한 비밀 키 비트 종속 공격 대응 기법
• VI. 결론
• References

참고문헌 (Reference)

1 M. Ciet, "Virtually) free randomization techniques for elliptic curve cryptography" 348-359, 2003

2 T. Sugawar, "Tow operands of multipliers in side-channel attack" 64-78, 2015

3 P. Kocher, "Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems" 104-113, 1996

4 M. Joye, "The montgomery powering ladder" 291-302, 2003

5 P. Montgomery, "Speeding the pollard and elliptic curve methods of factorization" 243-264, 1987

6 C. D. Walter, "Sliding windows succumbs to Big Mac attack" 286-299, 2001

7 J.-S. Coron, "Resistance against differential power analysis for elliptic curve cryptosystems" 292-302, 1999

8 D. May, "Random register renaming to foil DPA" 28-38, 2001

9 C.M. Bischop, "Pattern recognition and Machine Learning, Information Science and Statistics" Springer 2007

10 J. Heyszl, "Localized electromagnetic analysis of cryptographic implementations" 231-244, 2012

11 B.-Y. Sim, "Key Bit-Dependent Attack on Protected PKC Using a Single Trace" 168-185, 2017

12 T. Sugawara, "Internal collision attack on RSA under closed EM measurement" SCIS 2014

13 R. Specht, "Improving non-profiled attacks on exponentiations based on clustering and extracting leakage from multi-channel high-resolution EM measurements" 3-19, 2015

14 C. Clavier, "Horezontal correlation analysis on exponentiation" 46-61, 2010

15 M. Joye, "Highly regular right-to-left algorithms for scalar multiplication" 135-147, 2007

16 . Hankerson, "Guide to Elliptic Curve Cryptography" Springer 2003

17 J. López, "Fast multiplication on elliptic curves over without precomputation" 316-327, 1999

18 N. Hanley, "Exploiting collisions in addition chain-based exponentiation algorithms using a single trace" 431-448, 2015

19 P. Kocher, "Differential Power Analysis" 388-397, 1999

20 N. Homma, "Comparative power analysis of modular exponentiation algorithms" 759-807, 2010

21 I. Diop, "Collision for estimating SCA measurement quality and related applications" 143-157, 2015

22 I. Diop, "Collision based attacks in practice" 367-374, 2015

23 J. Heyszl, "Clustering algorithms for non-profiled single-execution attacks on exponentiations" 79-93, 2014

24 G. Perin, "Attacking randomized exponentiations using unsupervised learning" 144-160, 2014

25 G. Perin, "A Semi-parametric approach for side-channel attacks on protected RSA implemtations" 34-53, 2016