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

심보연; 강준기; 한동국

doi:10.13089/jkiisc.2018.28.5.1079

부채널 분석에 안전한 하드웨어 이진 스칼라 곱셈 알고리즘에 대한 단일 파형 비밀 키 비트 종속 공격
Key Bit-dependent Attack on Side-Channel Analysis-Resistant Hardware Binary Scalar Multiplication Algorithm using a Single-Trace 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.28 no.5, 2018년, pp.1079 - 1087

심보연 (국민대학교) , 강준기 (ETRI 부설 국가보안기술연구소) , 한동국 (국민대학교)

초록
AI-Helper

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

Abstract ▼ AI-Helper

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{\acute{o}}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.

주제어

표/그림 (8)

그림 Fig. 1. Examples of regular algorithms for binary scalar multiplication
그림 Fig. 2. Power consumption trace of 10 iterations
그림 Fig. 3. One of the sub-traces(top) and SOST value between two sub-trace groups(bottom)
그림 Fig. 4. Classification according to hamming distance between k_i and k_i+1 (Power consumption trace)
그림 Fig. 5. Classification according to hamming distance between k_i and k_i+1 (Electromagnetic trace, LF-R 400)
그림 Fig. 6. Classification according to hammingdistance between k_i and k_i+1 (Electromagnetictrace, LF-R 400 with BLP-10.7-75+)
그림 Fig. 7. Initialized by random bit
그림 Fig. 8. Classification according to hamming distance between k_i and k_i+1 (Power consumption trace, countermeasure)

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

이는 기존의 부채널 대응기법을 무력화 시킬 수 있는 강력한 공격으로, 본 논문에서는 ECC 스칼라 곱셈 알고리즘에 초점을 맞추었지만 RSA 모듈러 지수승 알고리즘에도 적용이 가능하다. 따라서 대응 기법의 적용이 필수적임을 시사하며, 본 논문에서는 매 반복 연산 수행 전에 랜덤 값으로 초기화 하는 대응 기법을 제시하였다.
방출되는 전자파 패턴을 활용하는 전자기 분석 공격은 전력 분석 공격 방법과 유사하며, 사용하는 부채널 정보의 차이가 존재한다. 따라서 본 논문에서는 전력 분석 공격을 기준으로 설명한다.
이에 본 논문에서는 하드웨어로 구현된 이진 스칼라 곱셈 알고리즘에 대한 비밀 키 비트 종속 특성을 정의하고, 실제 이를 기반으로 공격을 수행하여 비밀 키를 찾을 수 있음을 보인다. 제안하는 비밀 키 비트 종속 공격은 단일 파형으로 공격이 가능하며, 중간 값에 대한 사전 정보가 필요하지 않다.

가설 설정

( 0≤ i ≤n-1) G1에 속한 pi는 ki+1=ki일때, 즉, 0과 연관된 누출이 발생하는 파형이고, G2에 속한 pi 는 ki+1≠ ki 일 때, 즉, 0이 아닌 값과 관련된 누출이 발생하는 파형이라고 가정한다.
따라서 공격자는 단일 파형을 이용한 비밀 키 비트 종속 공격을 수행해야 한다고 가정한다. 더불어 공격자는 수집된 파형에서 각 반복 연산을 식별할 수 있다고 가정한다. 공격 단계는 다음 4단계로 구성되어 있다.
본 논문에서는 차분 전력 분석 대응기법으로 스칼라 랜덤화 기법이 적용된 Montgomery-López-Da hab ladder 스칼라 곱셈 알고리즘을 대상으로 한다. 따라서 공격자는 단일 파형을 이용한 공격을 수행해야 한다고 가정한다. 비밀 키 비트는 224비트이며, 부채널 분석 검증 보드로는 SASEBO-GII FP GA 보드를 이용하여 2.
본 논문에서는 차분 전력 분석 대응기법으로 중간값 랜덤화 기법이 적용된 규칙적인 이진 스칼라 곱셈 알고리즘을 대상으로 한다. 따라서 공격자는 단일 파형을 이용한 비밀 키 비트 종속 공격을 수행해야 한다고 가정한다. 더불어 공격자는 수집된 파형에서 각 반복 연산을 식별할 수 있다고 가정한다.

제안 방법

단순 전력 분석 또는 K-평균 군집화 알고리즘을 이용하여 223개 공격 지접 p_i를 두 개의 그룹 G_1,G₂로 나눈다. 전력파형의 경우 Fig.
그러므로 단순 전력 분석을 통해 두 집합으로 완벽히 분류하는 것이 어렵다. 따라서 본 논문에서는 K-평균 군집화 알고리즘을 적용하여 두 집합으로 분류하였다. 노이즈를 제거하기 위한 전처리를 수행하지 않았음에도 하나의 전자파형을 이용하여 99.
본 논문에서 제시하는 단일 파형을 이용한 비밀 키 비트 종속 공격 대응 기법으로 Fig. 7.과 같이 각 반복 연산에서 비밀 키 비트 확인 연산을 수행하기 전에 ki 변수를 랜덤 값으로 초기화 하는 방법을 제안한다.

대상 데이터

본 논문에서는 차분 전력 분석 대응기법으로 중간값 랜덤화 기법이 적용된 규칙적인 이진 스칼라 곱셈 알고리즘을 대상으로 한다. 따라서 공격자는 단일 파형을 이용한 비밀 키 비트 종속 공격을 수행해야 한다고 가정한다.
따라서 공격자는 단일 파형을 이용한 공격을 수행해야 한다고 가정한다. 비밀 키 비트는 224비트이며, 부채널 분석 검증 보드로는 SASEBO-GII FP GA 보드를 이용하여 2.5 GS/s으로 전력 및 전자파형을 수집하였다. 전자파형 수집 시 사용한 프로브는 100 kHz~50 MHz 대역의 신호를 수집할 수 있는 Langer LF-R 400이다.
실험은 차분 전력 분석 대응 기법이 적용된 Montgomery-López-Dahab ladder 스칼라 곱셈 알고리즘[13]을 하드웨어로 구현한 것을 대상으로 한다.
5 GS/s으로 전력 및 전자파형을 수집하였다. 전자파형 수집 시 사용한 프로브는 100 kHz~50 MHz 대역의 신호를 수집할 수 있는 Langer LF-R 400이다.

이론/모형

단순 전력 분석 또는 K-평균 군집화(K-means C lustering), 퍼지 K-평균 군집화(fuzzy K-means Clustering), EM(Expectation Maximization) 등과 같은 군집 알고리즘[4]을 이용하여 n개의 하위 파형 O_i의 공격 지점 p_i를 두 개의 그룹 G_1,G₂로 나눈다. ( 0≤ i ≤n-1) G₁에 속한 p_i는 k_i+1=k_i일때, 즉, 0과 연관된 누출이 발생하는 파형이고, G₂에 속한 p_i 는 k_i+1≠ k_i 일 때, 즉, 0이 아닌 값과 관련된 누출이 발생하는 파형이라고 가정한다.
본 논문에서는 차분 전력 분석 대응기법으로 스칼라 랜덤화 기법이 적용된 Montgomery-López-Da hab ladder 스칼라 곱셈 알고리즘을 대상으로 한다.
실험은 차분 전력 분석 대응 기법이 적용된 Montgomery-López-Dahab ladder 스칼라 곱셈 알고리즘[13]을 하드웨어로 구현한 것을 대상으로 한다. 비밀 키는 단순 전력 분석 및 K-평균 군집화 알고리즘을 이용하여 추출한다. 실험 결과 전력 및 전자파형을 이용하여 100%의 성공률로 비밀 키 비트를 찾을 수 있음을 보인다.

성능/효과

따라서 본 논문에서는 K-평균 군집화 알고리즘을 적용하여 두 집합으로 분류하였다. 노이즈를 제거하기 위한 전처리를 수행하지 않았음에도 하나의 전자파형을 이용하여 99.50%의 성공률로 비밀 스칼라 비트를 추출할 수 있었다.
본 논문에서 제시하는 비밀 키 비트 종속 공격은 단일 파형을 이용하여 공격이 가능하며, 사전 전처리 없이 전력파형의 경우 100%, 전자파형의 경우 99.50%의 성공률로 비밀 스칼라 비트를 추출할 수 있었다.
비밀 키는 단순 전력 분석 및 K-평균 군집화 알고리즘을 이용하여 추출한다. 실험 결과 전력 및 전자파형을 이용하여 100%의 성공률로 비밀 키 비트를 찾을 수 있음을 보인다. 그리고 비밀 키 비트 종속 공격 대응 기법을 제시하고 이를 적용해야 함을 시사한다.
즉, 하나의 전력 또는 전자파형을 이용하여 비밀 키 비트 종속 공격으로 100%의 성공률로 비밀 키 획득이 가능하다. 이는 기존의 부채널 대응기법을 무력화 시킬 수 있는 강력한 공격으로, 본 논문에서는 ECC 스칼라 곱셈 알고리즘에 초점을 맞추었지만 RSA 모듈러 지수승 알고리즘에도 적용이 가능하다. 따라서 대응 기법의 적용이 필수적임을 시사하며, 본 논문에서는 매 반복 연산 수행 전에 랜덤 값으로 초기화 하는 대응 기법을 제시하였다.

질의응답

핵심어	질문	논문에서 추출한 답변
	블록체인 및 FIDO는 무엇을 사용하여 사용자를 인증하는가?	4차 산업 혁명을 이끄는 새로운 기술로 각광받고 있는 블록체인 및 FIDO(Fast Identity Online) 는 ECDSA 알고리즘을 활용하여 사용자를 인증한다. 그러나 ECDSA의 주요 연산인 스칼라 곱셈 알고리즘[5]은 부채널 분석(SCA, Side-Channel Attack)에 취약하다.
	부채널 분석은 언제 제안되었는가?	부채널 분석은 1996년 Paul Kocher에 의해 최초로 제안되었으며, 보안 디바이스가 동작하는 동안 소모되는 전력 패턴이나 방출되는 전자파 패턴과 같은 부가적인 정보의 누출을 기반으로 하는 공격이다 [20]. 따라서 수학적으로 안전성이 증명된 암호 알고리즘이라도, 구현 단계에서 고려되지 못한 부가적인 정보의 누출을 이용한 부채널 분석에 취약하다.
	수학적으로 안전성이 증명된 암호 알고리즘이라도, 구현 단계에서 고려되지 못한 부가적인 정보의 누출을 이용한 부채널 분석에 취약할 수 있는 이유는 부채널 분석의 어떤 공격 방식 때문인가?	부채널 분석은 1996년 Paul Kocher에 의해 최초로 제안되었으며, 보안 디바이스가 동작하는 동안 소모되는 전력 패턴이나 방출되는 전자파 패턴과 같은 부가적인 정보의 누출을 기반으로 하는 공격이다 [20]. 따라서 수학적으로 안전성이 증명된 암호 알고리즘이라도, 구현 단계에서 고려되지 못한 부가적인 정보의 누출을 이용한 부채널 분석에 취약하다.

참고문헌 (25)

B.-Y. Sim and D.-G. Han, "Key Bit-Dependent Attack on Protected PKC Using a Single Trace", ISPEC 2017, pp. 168-185, 2017.
C. Clavier, B. Feix, G. Gagnerot, M. Roussellet, and V. Verneuil, "Horezontal correlation analysis on exponentiation", ICISC 2010, pp. 46-61, 2010.
C.D. Walter, "Sliding windows succumbs to Big Mac attack", CHES 2001, pp. 286-299, 2001.
C.M. Bischop, Pattern recognition and Machine Learning, Information Science and Statistics, Springer, New York, 2007.
D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, ISBN 0-387-95273-X, 2003.
D. May, H.L. Muller, and N.P. Smart, "Random register renaming to foil DPA", CHES 2001, pp. 28-38, 2001.
G. Perin, L. Imbert, L. Torres, and P. Maurine, "Attacking randomized exponentiations using unsupervised learning", COSADE 2014, pp. 144-160, 2014.
G. Perin and L. Chmielewski, "A Semi-parametric approach for side-channel attacks on protected RSA implemtations", CARDIS 2015, pp. 34-53, 2016.
I. Diop, P.Y. Liardet, and P. Maurine, "Collision based attacks in practice", DSD 2015, pp. 367-374, 2015.
I. Diop, M. Carbone, S. Ordas, Y. Linge, P.Y. Liardet, and P. Maurine, "Collision for estimating SCA measurement quality and related applications", CARDIS 2015, pp. 143-157, 2015.
J. Heyszl, S. Mangard, B. Heinz, F. Stumpf, and G. Sigl, "Localized electromagnetic analysis of cryptographic implementations", CT-RSA 2012. pp. 231-244, 2012.
J. Heyszl, A. Ibing, S. Mangard, F. De Santis, G. Sigl, "Clustering algorithms for non-profiled single-execution attacks on exponentiations", CARDIS 2013, pp. 79-93, 2014.
J. Lopez, and R. Dahab, "Fast multiplication on elliptic curves over $GF(2^m)$ without precomputation", CHES 1999, pp. 316-327, 1999.
J.-S. Coron, "Resistance against differential power analysis for elliptic curve cryptosystems", CHES 1999, pp. 292-302, 1999.
M. Ciet, M. Joye, "(Virtually) free randomization techniques for elliptic curve cryptography", ICISC 2003, pp. 348-359, 2003.
M. Joye, and S.-M. Yen, "The montgomery powering ladder", CHES 2002, pp. 291-302, 2003.
M. Joye, "Highly regular right-to-left algorithms for scalar multiplication", CHES 2007, pp. 135-147, 2007.
N. Hanley, H.S. Kim, and M. Tunstall, "Exploiting collisions in addition chain-based exponentiation algorithms using a single trace", CT-RSA 2015, pp. 431-448, 2015.
N. Homma, A. Miyamoto, T. Aoki, A. Satoh, "Comparative power analysis of modular exponentiation algorithms", IEEE Trans, pp. 759-807, 2010.
P. Kocher, "Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems", CRYPTO 1996, pp. 104-113, 1996.
P. Kocher, J. Jaffe, and B. Jun, "Differential Power Analysis", CRYPTO 1999, pp. 388-397, 1999.
P. Montgomery, "Speeding the pollard and elliptic curve methods of factorization", Mathematics of Computation, pp. 243-264, 1987.
R. Specht, J. Heyszl, M. Kleinsteuber, and G. Sigl, "Improving non-profiled attacks on exponentiations based on clustering and extracting leakage from multi-channel high-resolution EM measurements", COSADE 2014, pp. 3-19, 2015.
T. Sugawara, D. Suzuki, and M. Saeki, "Internal collision attack on RSA under closed EM measurement", SCIS 2014.
T. Sugawar, D. Suzuki, and M. Saeki, "Tow operands of multipliers in side-channel attack", COSADE 2014, pp. 64-78, 2015.

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증