[논문]마스킹 기법이 적용된 SEED 알고리즘에 대한 취약점 분석

김태원; 장남수

doi:10.13089/jkiisc.2015.25.4.739

마스킹 기법이 적용된 SEED 알고리즘에 대한 취약점 분석
Analysis on Vulnerability of Masked SEED Algorithm 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.25 no.4, 2015년, pp.739 - 747

김태원 (고려대학교) , 장남수 (세종사이버대학교)

초록
AI-Helper

전력분석의 대응기법으로 가장 널리 알려진 마스킹 기법은 암호 알고리즘 수행 도중 비밀 중간 값을 노출시키지 않게 함으로써 공격자가 필요한 정보를 얻지 못하도록 한다. 마스킹 기법은 대칭키 암호 알고리즘에 적용되어 많은 연구가 진행되었다. 국제표준 알고리즘인 SEED 알고리즘에 대해 마스킹 대응기법 연구가 진행되었다. Cho 등이 제안한 Masked SEED 알고리즘은 1차 전력분석에 안전할 뿐만 아니라 Arithmetic to Boolean 변형 함수의 호출을 줄임으로써 효율성까지 만족시켰다. 본 논문에서는 Cho 등이 제안한 Masked SEED에 대한 취약점을 분석하였다. 효율적인 연산을 위해 추가로 수행되는 사전연산에 의해 마스크 값이 노출되고 이를 이용하여 1차 전력분석 공격으로 비밀키를 복원하였다. 우리는 이론적인 측면과 실험적인 측면을 모두 고려하여 취약점을 분석하였으며 제안한 공격기법은 Cho 등이 제안한 알고리즘이 탑재된 모든 디바이스에서 공통적으로 적용될 수 있음을 예상한다.

Abstract ▼ AI-Helper

Masking technique that is most widely known as countermeasure against power analysis attack prevents leakage for sensitive information during the implementations of cryptography algorithm. it have been studied extensively until now applied on block cipher algorithms. Masking countermeasure have been applied to international standard SEED algorithm. Masked SEED algorithm proposed by Cho et al, not only protects against first order power analysis attacks but also efficient by reducing the execution of Arithmetic to Boolean converting function. In this paper, we analyze the vulnerability of Cho's algorithm against first order power analysis attacks. We targeted additional pre-computation to improve the efficiency in order to recover the random mask value being exploited in first order power analysis attacks. We describe weakness by considering both theoretical and practical aspects and are expecting to apply on every device equipped with cho's algorithm using the proposed attack method.

주제어

AI 본문요약
AI-Helper

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

문제 정의

2장에서 분석 대상 알고리즘을 소개한다. 따라서 SEED 알고리즘과 1차 전력분석에 안전한 Cho 등의 Masked SEED 알고리즘에 대해 서술한다. 3장은 Cho 등의 알고리즘에 대해 취약점을 분석한다.
본 논문에서는 Cho 등이 제안한 Masked SEED 알고리즘에 대한 취약점을 분석한다. 제안하는 공격은 SEED 알고리즘이 동작하기 전에 수행되는 사전연산을 공격목표로 한다.
우리는 2장에서 Cho 등이 제안한 1차 전력분석 안전한 효율적인 Masked SEED에 대해 살펴보았다. 효율적인 Masked SEED 수행을 위해 AtoB 연산을 줄였고 이로 인해 Carry 테이블 생성 함수와 Carry 제어 함수를 추가적으로 수행하였다.

가설 설정

본 논문에서 제안한 분석기법은 실험에 사용된 MSP430칩에 한정되지 않는다. 각 디바이스 마다[Alg.2] 수행에 대한 전력파형은 조금씩 다를 것이다. 하지만 마스크 값에 의하여 연산 차이가 발생한다는 사실은 모두 공통적으로 적용된다.
공격자는 Cho 등이 제안한 Masked SEED 알고리즘이 동작했을 때 소모한 전력파형을 n개 수집했다고 가정하자. 그러면 공격자는 다음과 같은 과정을 통해 분석을 진행한다.

제안 방법

1]은 알고리즘이 동작하기 전, 생성된 난수 m, m′을 이용하여 Masked S-box을 사전 연산한다. Arithmetic 마스크 형태를 그대로 사용하기 위해 기존의 XOR 연산을 모듈러 덧셈연산으로 대체하였고 Masked S-box의 출력 값은 S-box연산 후 진행된 Boolean 연산을 위해 Boolean 형태가 되도록 설계하였다.
키 스케쥴링 함수는 128-bit 키를 이용하여 64-bit의 16라운드 키를 생성한다. SEED 알고리즘에 대한 전체 구조도는 [Fig. 1]을 통해 도식화 하였다. 128-bit 평문이 2개의 64-bit 블록(L₀,R₀)으로 나누어진 뒤 16라운드를 거쳐 암호문 (L₁₆,R₁₆)으로 변환되는 구조를 보여준다.
5]과 같이 16개의 seg로 분리시켜야 한다. 각 16개의 분기문의 시작과 끝 부분에서 전력소모량이 급격히 떨어지는 부분을 관찰할 수 있으므로 이에 대한 주기를 기준으로 분리작업을 수행할 수 있다.
공격자는 n번의 암호 알고리즘 동작에서 사용된 각 마스크 값 mi, (i=1,···,n) 을 복원한 후 알고있는 평문정보를 이용하여 키를 추측한 후 비밀 중간 값에 대해 1차 상관계수 전력분석을 수행한다.
5]파형의 경우 M_l에 대한 특징은 각각의 seg대한 최대피크 크기이다. 따라서 공격자는 seg1부터 seg8까지 각 seg에서 가장 큰 값을 추출한 후 이 값들에 대한 평균을 계산한다. 또한 seg9부터 seg16에 대해서도 동일한 작업을 수행한다.
2]-Step2에서 분기가 처리되어 테이블에 λ+1을 저장한다. 또한 i값이 m_h와 크기가 같다면 [Alg. 2]-Step 2의 분기에서 조건을 비교한 후 Step 3로 분기가 처리되어 총 2번의 조건 비교를 수행한다. 조건에 맞는 분기처리를 위해 수행하는 조건비교 연산이 m_h값에 따라 1번 또는 2번이다.
이런 차이로 인해 마스크 값을 복원할 수 있음을 이론적으로 분석하였다. 또한 각각의 차이점을 파형을 통해 확인함으로써 실제적인 공격 가능성을 확인하였다. 분석결과 단순한 시각적인 관찰만으로도 차이점을 확인할 수 있으며, 이를 특징화 시켜 모든 파형에 실시간으로 적용시켜 마스크 값 복원이 가능했다.
본 장에서는 위에서 소개한 추가적인 연산에서 발생하는 취약점을 분석하였다. SEED 알고리즘 연산 전 수행하는 Carry 테이블 생성연산은 마스크 값에 의존함을 확인하였고 이 정보를 통해 마스크 정보를 복원할 수 있었다.
본 절은 마스크 값에 의한 연산의 차이가 전력 소모량의 차이로 나타나, 8-bit 마스크 값 정보를 단순한 시각적인 검사로 구별할 수 있음을 실제적인 실험을 통하여 확인한다. 검증을 위해 KLA-SCARF 시스템의 MSP430 부채널 분석 보드를 이용하였다[11].
이러한 작업은 단순한 시각적인 분석을 통해 가능하였다. 수집된 파형에 대해 마스크 값을 실시간으로 복원한 후 알고 있는 평문정보와 키 추측으로 1차 전력분석 공격을 수행한다. 최종적으로 공격자는 1차 전력분석에 안전한 알고리즘에 대해 마스크 복원 공격을 통한 1차 전력분석 공격으로 비밀키를 얻는다.
앞에서 소개한 취약점을 이용하여 SEED 알고리즘에서 사용된 비밀정보를 복원하는 방법을 서술한다. 1차 전력분석에 안전한 마스킹 기법을 사용했지만 마스크 값 복원을 통해 1차 전력분석으로 비밀키를 찾을 수 있다.
2]가 수행된 부분을 찾아내야한다. 우선 SEED 알고리즘은 16라운드로 구성 되었으므로 16개의 동일한 패턴을 관찰하여 16라운드동작 부분을 확인한다. 따라서 16라운드 함수 전에 나타나는 파형을 관찰하면 사전연산이 동작되며 소모된 전력소모량을 확인할 수 있다.
마스크 값에 의한 전력소모량 차이를 확인하기 위하여 알고 있는 마스크 정보 0x58를 이용한다. 우선 상위 마스크 값 M_h=5에 대해 반복문 i=0부터 4까지의 전력파형(seg1 - seg5)과 이 후의 파형(seg6 - seg16)의 차이를 살펴본다.
SEED 알고리즘 연산 전 수행하는 Carry 테이블 생성연산은 마스크 값에 의존함을 확인하였고 이 정보를 통해 마스크 정보를 복원할 수 있었다. 이러한 취약점에 대해 이론적인 분석뿐만 아니라 실제적인 실험을 통해 이를 검증하였다.
3장은 Cho 등의 알고리즘에 대해 취약점을 분석한다. 이론적인 분석뿐만 아니라 실험적인 검증까지도 수행하였다. 3장의 분석내용을 바탕으로 비밀키를 복원하는 방법을 4장에서 제안하고 5장에서 결론을 맺는다.
본 논문에서는 Cho 등이 제안한 Masked SEED 알고리즘에 대한 취약점을 분석한다. 제안하는 공격은 SEED 알고리즘이 동작하기 전에 수행되는 사전연산을 공격목표로 한다. 마스크 값에 의존하여 연산의 차이가 발생하는 취약점을 이용하여, 전력파형에서 이들의 차이를 확인함으로써 마스크 값을 복원한다.
Cho 등의 마스킹스킴은 Carry 테이블 생성, 마스킹 S-box 생성, 키스케쥴링, 랜덤수 선택과 같은 사전연산이 있다. 최종적으로 공격자는 16번의 반복문이 수행되는 Carry 테이블 생성 부분을 추출하기 위해 16개의 비슷한 패턴이 관찰되는 구간을 선택한다. 이 모든 작업은 단순히 시각적인 분석을 통해 가능하다.
하위 4-bit 마스크 값 M_l=8에 의한 전력소모량차이를 확인하기 위하여 [Fig.7]와 같이 i=7(seg8)과 i=8(seg9)의 반복문에 대한 전력소모량을 비교하였다. 각 seg를 살펴보면 확연한 차이를 나타내는 2개의 피크([Fig.
우리는 2장에서 Cho 등이 제안한 1차 전력분석 안전한 효율적인 Masked SEED에 대해 살펴보았다. 효율적인 Masked SEED 수행을 위해 AtoB 연산을 줄였고 이로 인해 Carry 테이블 생성 함수와 Carry 제어 함수를 추가적으로 수행하였다.

대상 데이터

본 절은 마스크 값에 의한 연산의 차이가 전력 소모량의 차이로 나타나, 8-bit 마스크 값 정보를 단순한 시각적인 검사로 구별할 수 있음을 실제적인 실험을 통하여 확인한다. 검증을 위해 KLA-SCARF 시스템의 MSP430 부채널 분석 보드를 이용하였다[11].

이론/모형

마스킹으로 변환하는 함수의 호출 횟수를 줄였다. 이것을 가능하게 하기 위해 Arithmetic 마스킹 형태의 모듈러 덧셈 결과 값에 대해 캐리 조절 함수와 새롭게 구성된 Masked S-box table을 사용하였다.

성능/효과

1차 전력분석에 안전하게 설계된 알고리즘이라도 구현상에서 발생할 수 있는 취약점을 이용하여 1차 전력분석으로 비밀 키를 복원할 수 있음을 확인하였다.
Carry 테이블을 생성 시 i=0부터 15까지, 16번의 반복문이 동작하면서 마스크 값 m에 상위/하위4-bit 값에 따라 연산의 차이가 발생함을 확인하였다.
2010년 Cho 등은 기존의 방법보다 효율적인 Masked SEED 알고리즘을 제안하였다. Masking 연산 시 많은 연산량을 차지하는 Arithmetic to Boolean 변환연산을 줄임으로서 알고리즘의 효율성을 향상시켰다.
본 장에서는 위에서 소개한 추가적인 연산에서 발생하는 취약점을 분석하였다. SEED 알고리즘 연산 전 수행하는 Carry 테이블 생성연산은 마스크 값에 의존함을 확인하였고 이 정보를 통해 마스크 정보를 복원할 수 있었다. 이러한 취약점에 대해 이론적인 분석뿐만 아니라 실제적인 실험을 통해 이를 검증하였다.
또한 각각의 차이점을 파형을 통해 확인함으로써 실제적인 공격 가능성을 확인하였다. 분석결과 단순한 시각적인 관찰만으로도 차이점을 확인할 수 있으며, 이를 특징화 시켜 모든 파형에 실시간으로 적용시켜 마스크 값 복원이 가능했다.

후속연구

하지만 마스크 값에 의하여 연산 차이가 발생한다는 사실은 모두 공통적으로 적용된다. 따라서 각 디바이스에 알맞은 특징화를 통해 제안한 공격과정을 수행한다면 비밀키 정보를 얻을 수 있을 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	부채널 공격에는 어떤 것들이 있는가?	이론적으로 안전한 암호 알고리즘도 실제 구현 단계에서 암호 설계자가 고려하지 못한 부가적인 정보의 노출로 인해 비밀 정보가 노출될 수 있음이 알려졌다. 부채널 공격 (side channel attack)[1]은 오류 주입 공격 (fault injection attack)[2,3], 시간차 공격 (timing attack)[1,4], 전력분석 공격 (power analysis attack)[5-7] 등이 있다.
	마스킹 기법의 장점은 무엇인가?	마스킹 기법은 랜덤 마스크 값을 이용하여 전력소모량과 비밀 중간 값과의 상관관계를 제거한다. 이것은 저렴한 비용과 기존 알고리즘에 쉽게 적용시킬 수 있는 장점을 가지고 있다.
	마스킹 기법은 랜덤 마스크 값을 이용하여 무엇을 제거하는가?	이 중 가장 널리 사용되고 있는 것은 마스킹(Masking)기법이다[13-18]. 마스킹 기법은 랜덤 마스크 값을 이용하여 전력소모량과 비밀 중간 값과의 상관관계를 제거한다. 이것은 저렴한 비용과 기존 알고리즘에 쉽게 적용시킬 수 있는 장점을 가지고 있다.

참고문헌 (22)

P. Kocher, J. Jaffe, and B. Jun, "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS,and Others Systems," CRYPTO '96, LNCS 1109, pp. 104-113, Aug. 1996.
E. Biham, A. Shamir, "Differential Fault Analysis of Secret Key Cryptosystems," CRYPTO '97, LNCS 1294, pp. 513-525, Aug. 1997.
D. Boneh, R. A. DeMillo and R. J. Lipton, "On the Importance of Checking Cryptographic Protocols for Faults," EUROCRYPT '97, LNCS 1233, pp. 37-51, May. 1997.
P. Kocher, J. Jaffe, and B. Jun, "Introduction to differential power analysis and related attacks," White Paper, Cryptography Research, 1998.
P. Kocher, J. Jaffe, and B. Jun, "Differential power analysis," CRYPTO '99, LNCS 1666, pp. 388-397, Aug. 1999.
S. Chari, J.R. Rao, and P. Rohatgi. "Template Attacks," CHES 2002, LNCS 2523, pp. 13-28, Aug. 2002.
E. Brier, C. Clavier, and F. Olivier, "Correlation power analysis with a leakage model," CHES, LNCS vol. 3156, pp. 16-29, Aug. 2004.
Korea Information & Security Agency, "Block Cipher Algorithm SEED," Available at http://www.kisa.or.kr
"Information Technology - Security Techniques - Encryption Algorithms - Part 3: Block Ciphers," ISO/IEC 18033-3:2005, 2005.
YoungIn Cho, HeeSeok Kim, Dooho Choi, Dong-Guk Han, Seokhie Hong, and Okyeon Yi, "Efficient Masking Method to Protect SEED Against Power Analysis Attack," Korea Information Processing Society, 17-C(3), pp. 233-242, Jun. 2010.
YongJe Choi, DooHo Cho, and JaeCheol Ryou, "Implementing Side Channel Analysis Evaluation Boards of KLA-SCARF system," Journal of The Korea Institude of Information Security & Cryptology, 24(1), pp. 229-240, Feb. 2014.

원문보기 상세보기
Y.Lu, K.-H. Boey, P.Hodgers, and M.O'Neill. "SEED Masking Implementations against Power Analysis Attacks," IEEE Asia Pacific Conference on Circuit and Systems, pp.1199-1202, Dec. 2010.
S. Mangard, E. Oswald, and T. Popp, Power Analysis Attacks: Revealing the Secrets of Smart Cards., (Advances in Information Security), Springer, 2007.
S. Chari, C. Jutla, J. Rao, and P. Rohatgi, "Towards Sound Approaches to Counteract Power-Analysis Attacks," CPYPTO '99, LNCS 1666, pp. 398-412, Aug. 1999.
L. Goubin and J. Patarin, "DES and Differential Power Analysis - The "Duplication" Method," CHES 1999, LNCS 1717, pp. 158-172, Aug. 1999.
T. Messerges, "Power Analysis Attacks and Countermeasures for Cryptographic Algorithms," Ph.D. Thesis, University of Illinois, Oct. 2000.
J-S. Coron and L. Goubin, "On boolean and arithmetic masking against differential power analysis," CHES 2000. LNCS 1965, pp. 231-237. Aug. 2000.
M. Nassar, Y. Souissi, S. Guilley, and J-L, Danger, "RSM: a small and fast countermeasure for AES, secure against 1st and 2nd-order Zero-Offset SCAs," Design, Automation & Test in Europe Conference & Exhibition (DATE) 2012, IEEE, pp. 1173-1178, Mar. 2012.
L. Goubin, "A sound method for switching between boolean and arithmetic masking," CHES 2001, LNCS 2162, pp. 3-15, May. 2001.
J-S. Coron and A. Tchulkine, "A new algorithm for switching from arithmetic to boolean masking," CHES 2003, LNCS 2779, pp. 89-97, Sep. 2003.
O. Neibe and J. Pulkus, "Switching blindings with a view towards idea," CHES 2004, LNCS 3156, pp. 230-239, Aug. 2004.
J-S. Coron, J. Groschadl, and PK. Vadnala, "Secure conversion between boolean and arithmetic masking of any order," CHES 2014, LNCS 3156 pp. 188-205, Sep. 2014.

저자의 다른 논문 :

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

연합인증