[논문]블록 암호 HIGHT에 대한 차분 오류 공격

이유섭; 김종성; 홍석희

doi:10.13089/jkiisc.2012.22.3.485

블록 암호 HIGHT에 대한 차분 오류 공격
A Differential Fault Attack against Block Cipher HIGHT 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.22 no.3, 2012년, pp.485 - 494

초록
AI-Helper

HIGHT는 국내에서 개발된 초경량 블록 암호로서, 정보통신단체(TTA) 표준과 국제표준화기구(ISO/IEC) 18033-3 표준으로 제정되었다. 본 논문에서는 블록암호 HIGHT에 대한 차분 오류 주입 공격을 제안한다. 제안하는 공격에서 공격자는 암호화 과정에서 라운드 28의 입력값에 임의의 1-바이트 오류를 주입할 수 있다고 가정한다. 이러한 가정에서 오류 주입을 통해 얻어진 암호문과 정상적으로 얻어진 암호문의 차분 특성을 이용하여 비밀키를 복구한다. 12개의 오류를 주입할 경우에는 88%의 성공 확률, 7개의 오류를 주입하는 경우에는 51%의 성공 확률로 수초내에 HIGHT의 비밀키를 복구한다.

Abstract ▼ AI-Helper

The block cipher HIGHT is designed suitable for low-resource hardware implementation. It established as the TTA standard and ISO/IEC 18033-3 standard. In this paper, we propose a differentail fault attack against the block cipher HIGHT. In the proposed attack, we assume that an attacker is possible to inject a random byte fault in the input value of the 28-th round. This attack can recover the secret key by using the differential property between the original ciphertext and fault cipher text pairs. Using 7 and 12 error, our attack recover secret key within a few second with success probability 87% and 51%, respectively.

주제어

AI 본문요약
AI-Helper

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

문제 정의

하지만, HIGHT는 8 비트 기반 덧셈, XOR, 로테이션 연산을 사용하여 S-박스와 치환 함수를 사용하는 블록 암호에 비해 많은 수의 오류가 필요하기 때문에 차분 오류 공격을 적용하기에 어려움이 있었다. 본 논문에서는 HIGHT에 대한 차분 오류 공격을 최초로 제안한다. 본 논문에서 제안하는 차분 오류 공격은 7~12개의 오류 주입을 이용하여 수 초내에 HIGHT의 비밀키를 복구한다.
본 논문에서는 블록암호 HIGHT에 대한 차분 오류 주입 공격을 제안하였다. 제안한 공격은 라운드 28의 입력값에 임의의 1-바이트 오류를 주입하여 오류주입을 통해 얻어진 암호문과 정상적으로 얻어진 암호문의 차분 특성을 이용하여 비밀키를 복구하였다.
본 절에서는 공격에 사용하는 오류 주입 가정과 주입된 오류에 의한 차분 확산 특성을 소개한다.

가설 설정

본 논문에서는 공격자가 라운드 28의 입력 레지스터에 임의의 1-바이트 오류를 주입 할 수 있음을 가정한다. 이러한 가정에서 공격자는 선택한 평문에 대해 오류가 주입 되지 않은 정상적인 암호문 C와 오류가 주입된 암호문 C^∗를 얻을 수 있다.
본 장에서는 제안하는 공격에 대한 구현 결과를 소개한다. 실제 오류 주입의 공격 모델은 하드웨어 환경이지만, 소프트웨어 환경에서 오류 가입 가정을 이용하여 공격 과정을 구현하였다. 구현 환경은 Intel(R) Core(TM) i7 2.
일반적으로 차분 오류 공격에서 공격자는 선택한 평문에 대해 특정 라운드의 입력레지스터에 임의의 오류를 주입하여 암호문을 얻을 수 있다고 가정한다. 이때, 레지스터의 임의의 1-비트에 오류를 주입된다는 가정과 임의의 1-바이트에 오류가 주입된다는 가정을 주로 사용하였다. 실제적으로 오류가 주입될 때, 하나의 비트에만 오류가 발생하기 보다는 여러 비트에 동시에 오류가 발생하기 때문에 임의의 1-바이트 오류 주입 가정이 일반적으로 사용되고 있다.
이러한 가정에서 공격자는 선택한 평문에 대해 오류가 주입 되지 않은 정상적인 암호문 C와 오류가 주입된 암호문 C^∗를 얻을 수 있다. 임의의 1-비트 오류를 주입할 수 있다고 가정하여도 제안하는 공격은 동일하게 적용되지만, 일반적으로 사용되는 오류 주입 가정인 임의의 1-바이트 오류를 주입할 수 있음을 가정한다.
= 2(총 8개의 오류 주입)로 실험하였다. 즉, X_27,0 이나 X_27,1 에 오류가 주입된 2개의 암호문, X_27,2 이나 X_27,3, X_27,4 이나 X_27,5, X_27,6 이나 X_27,7 에 오류가 주입된 암호문을 각각 2개씩을 획득하여 총 8개의 오류 암호문쌍을 동시에 이용할 수 있다고 가정하여 공격을 수행하였다.

제안 방법

총 100회의 키 복구 공격을 수행하여 각 단계에서 추측하는 비밀키 후보의 수와 이전 단계에 남아있는 테이블에 남아있는 비밀키의 수를 통하여 각 단계에 필요한 연산량을 HIGHT 암호화 연산의 수로 측정하였고, 각 단계를 마친 후 저장하는 비밀키 후보의 수에 따라 생성되는 테이블의 크기를 측정하하여 필요한 메모리 복잡도를 계산하였다. 각 단계의 계산 복잡도와 메모리 복잡도를 합하여 전체 계산 복잡도와 메모리 복잡도를 계산하였다. [표 3]은 이러한 가정에서 100회 공격 결과에 대한 평균값이다.
두 번째 구현 결과는 본 논문에서 제안한 공격에서 가정했던 공격 모델로 오류가 주입되는 바이트 위치를 공격자가 선택할 수 없도록 하여 8개의 오류 주입을 이용한 공격을 100회 실험하였다. 결과적으로 62%의 성공확률을 보여 100회 중 38회가 공격에 실패하였다.
차분 오류 공격의 가장 일반적인 모델로는 블록 암호의 마지막 라운드에 오류를 주입하여 암호문의 차분으로부터 불가능한 차분을 가지는 비밀키 후보를 제거함으로서 마지막 라운드에 사용되는 라운드키를 복구한다. 마지막 라운드키를 복구하고, 이를 이용하여 마지막 두번째 라운드에 오류를 주입하여 라운드키를 복구한 후, 동일한 방법을 반복함으로서 전체 비밀키를 복구한다. 이러한 차분 오류 공격은 계산 복잡도는 매우 낮지만 공격에 필요한 오류 주입의 수가 많아지는 단점이 있다.
본 논문에서는 HIGHT에 대한 차분 오류 공격을 최초로 제안한다. 본 논문에서 제안하는 차분 오류 공격은 7~12개의 오류 주입을 이용하여 수 초내에 HIGHT의 비밀키를 복구한다.
세번째 구현 결과는 오률 주입의 수를 변화하면서 각각 100회의 공격 실험을 통해 공격의 성공 확률과 계산 복잡도를 측정하였다. 표 5는 이 결과를 나타낸다.
이러한 차분 오류 공격은 계산 복잡도는 매우 낮지만 공격에 필요한 오류 주입의 수가 많아지는 단점이 있다. 이를 극복하기 위해 일정 라운드 위에 차분을 주입하고 차분의 확산 특성을 분석하여 적은 수의 오류 주입을 사용하면서 실제적으로 공격이 가능한 복잡도를 가지는 형태의 차분 오류 공격이 제안되었다. 대표적으로 2009년 1개의 오류를 이용하여 2³²의 계산 복잡도를 가지는 AES에 대한 차분 오류 주입 공격을 제안되었다[11].
본 장에서는 블록 암호 HIGHT에 대한 차분 오류 공격을 소개한다. 제안하는 공격은 다수의 오류 주입 암호문쌍을 동시에 고려하여 비밀키를 복구한다. 제안하는 오류 주입 공격의 공격 과정은 다음과 같다.
본 논문에서는 블록암호 HIGHT에 대한 차분 오류 주입 공격을 제안하였다. 제안한 공격은 라운드 28의 입력값에 임의의 1-바이트 오류를 주입하여 오류주입을 통해 얻어진 암호문과 정상적으로 얻어진 암호문의 차분 특성을 이용하여 비밀키를 복구하였다. 12개의 오류를 주입하여 87.
첫 번째 실험은 실제 공격 가정과 달리 공격자가 오류를 주입할 수 있는 위치를 지정할 수 있도록 하여 t₀ = t₁ = t₂ = t₃ = 2(총 8개의 오류 주입)로 실험하였다. 즉, X_27,0 이나 X_27,1 에 오류가 주입된 2개의 암호문, X_27,2 이나 X_27,3, X_27,4 이나 X_27,5, X_27,6 이나 X_27,7 에 오류가 주입된 암호문을 각각 2개씩을 획득하여 총 8개의 오류 암호문쌍을 동시에 이용할 수 있다고 가정하여 공격을 수행하였다.
총 100회의 키 복구 공격을 수행하여 각 단계에서 추측하는 비밀키 후보의 수와 이전 단계에 남아있는 테이블에 남아있는 비밀키의 수를 통하여 각 단계에 필요한 연산량을 HIGHT 암호화 연산의 수로 측정하였고, 각 단계를 마친 후 저장하는 비밀키 후보의 수에 따라 생성되는 테이블의 크기를 측정하하여 필요한 메모리 복잡도를 계산하였다. 각 단계의 계산 복잡도와 메모리 복잡도를 합하여 전체 계산 복잡도와 메모리 복잡도를 계산하였다.

대상 데이터

국내에서 개발된 HIGHT는 2006년 정보통신단체(TTA) 표준으로 제정되었으며, 2010년에 국제표준화기구(ISO/IEC) 18033-3의 표준으로 제정되었다. HIGHT는 128-비트 비밀키를 사용하는 64-비트 블록 암호로서 32 라운드 8-branch type Ⅱ generalized Feistel 구조로 설계되었다. 라운드 함수는 2⁸ 위에서의 법덧셈, XOR 연산과 비트 단위 순환 이동 연산만을 이용하여 스마트폰, 스마트카드, RFID, 유비쿼터스센서네트워크(USN) 등 제한된 환경에 적합하다.
실제 오류 주입의 공격 모델은 하드웨어 환경이지만, 소프트웨어 환경에서 오류 가입 가정을 이용하여 공격 과정을 구현하였다. 구현 환경은 Intel(R) Core(TM) i7 2.80GHZ CPU, 6 GB Ram, Visual studio 2008이고, 테이블을 저장하는데 사용되는 메모리는 최대 2²⁷ 바이트로 설정하였다.
제안하는 공격의 데이터 복잡도는 t개의 선택 평문과 이에 대응되는 t개의 오류가 암호문이다. 계산 복잡도와 메모리 복잡도의 경우, 사용된 오류 주입 개수에 따라 달라진다.

성능/효과

제안한 공격은 라운드 28의 입력값에 임의의 1-바이트 오류를 주입하여 오류주입을 통해 얻어진 암호문과 정상적으로 얻어진 암호문의 차분 특성을 이용하여 비밀키를 복구하였다. 12개의 오류를 주입하여 87.5%의 성공 확률로 수초 내에 HIGHT의 비밀키를 복구할 수 있으며 7개의 오류룰 주입하여 51.3%의 성공 확률로 HIGHT의 비밀키를 복구하였다.
두 번째 구현 결과는 본 논문에서 제안한 공격에서 가정했던 공격 모델로 오류가 주입되는 바이트 위치를 공격자가 선택할 수 없도록 하여 8개의 오류 주입을 이용한 공격을 100회 실험하였다. 결과적으로 62%의 성공확률을 보여 100회 중 38회가 공격에 실패하였다. 공격이 실패 경우는 모두 t₀,t₁,t₂,t₃중 하나가 0이 되는 경우였다.
결론적으로 12개의 오류를 주입하면 성공 확률 88%의 성공 확률로 HIGHT의 비밀키를 수초내로 복구할 수 있으며, 7개의 오류를 주입하면 50%이상의 확률로 HIGHT의 비밀키를 수초내로 복구할 수 있을 것으로 예측된다.
실제로, 가능한 모든 값에 대한 전수조사를 통해 틀린키가 제거될 확률을 계산할 결과, ΔX31,3 = 0과 ΔX31,7 = 0의 경우, 틀린 키가 제거 되지 않을 확률은 2-3.59이었고, ΔX31,5 = 0과 ΔX31,1 = 0에 의해 틀린 키가 제거 되지 않을 확률은 2-5.78이었다.
이러한 구현 결과를 바탕으로 공격의 성공 확률은 t₀,t₁,t₂,t₃가 모두 0이 아닌 확률로 예상할 수 있다. 그러므로 오류 주입 개수에 대한 제안하는 공격의 이론적인 성공확률은 [표 6]과 같다.

후속연구

중 하나의 값이 0 인 경우에, 가능한 공격 방법과 보다 적은 수의 오류를 사용하면서도 성공 확률을 높이는 방법을 연구할 계획이다. 또한, 각 단계에서 각각의 식에 의해 틀린키가 필터링 되는 확률을 분석함으로서 공격 복잡도에 대한 이론적인 분석을 수행할 계획이다.
이에 따라, 5절에서 실험 결과를 바탕으로 계산 복잡도와 메모리 복잡도를 제시한다. 본 논문에서 제안하는 공격은 적은 수의 오류를 사용하여 실제로 구현 가능한 공격이므로 구현 결과를 바탕으로 한 계산 복잡도분석이 의미가 있을 것으로 생각된다.
이 후 연구 목표로는 t₀,t₁,t₂,t₃ 중 하나의 값이 0 인 경우에, 가능한 공격 방법과 보다 적은 수의 오류를 사용하면서도 성공 확률을 높이는 방법을 연구할 계획이다. 또한, 각 단계에서 각각의 식에 의해 틀린키가 필터링 되는 확률을 분석함으로서 공격 복잡도에 대한 이론적인 분석을 수행할 계획이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	HIGHT는 라운드 함수의 특징으로 인해 어떤 환경에 적합한가?	HIGHT는 128-비트 비밀키를 사용하는 64-비트 블록 암호로서 32 라운드 8-branch type Ⅱ generalized Feistel 구조로 설계되었다. 라운드 함수는 28 위에서의 법덧셈, XOR 연산과 비트 단위 순환 이동 연산만을 이용하여 스마트폰, 스마트카드, RFID, 유비쿼터스센서네트워크(USN) 등 제한된 환경에 적합하다.
	HIGHT란 무엇인가?	국내에서 개발된 HIGHT는 2006년 정보통신단체(TTA) 표준으로 제정되었으며, 2010년에 국제표준화기구(ISO/IEC) 18033-3의 표준으로 제정되었다. HIGHT는 128-비트 비밀키를 사용하는 64-비트 블록 암호로서 32 라운드 8-branch type Ⅱ generalized Feistel 구조로 설계되었다. 라운드 함수는 28 위에서의 법덧셈, XOR 연산과 비트 단위 순환 이동 연산만을 이용하여 스마트폰, 스마트카드, RFID, 유비쿼터스센서네트워크(USN) 등 제한된 환경에 적합하다.
	HIGHT는 어떤 구조로 설계되었는가?	국내에서 개발된 HIGHT는 2006년 정보통신단체(TTA) 표준으로 제정되었으며, 2010년에 국제표준화기구(ISO/IEC) 18033-3의 표준으로 제정되었다. HIGHT는 128-비트 비밀키를 사용하는 64-비트 블록 암호로서 32 라운드 8-branch type Ⅱ generalized Feistel 구조로 설계되었다. 라운드 함수는 28 위에서의 법덧셈, XOR 연산과 비트 단위 순환 이동 연산만을 이용하여 스마트폰, 스마트카드, RFID, 유비쿼터스센서네트워크(USN) 등 제한된 환경에 적합하다.

참고문헌 (16)

NIST, "Advanced Encryption Standard," FIPS-197, Nov. 2001,
Korea Information Security Agency, "SEE D Algorithm Specification". Available at http://seed.kisa.or.kr/seed/down/SEED_Specification_english.pdf.
D. Kwon, J. Kim, S. Park, S. Sung, Y. Sohn, J. Song, Y. Yeom, E. Yoon, S. Lee, J. Lee, S. Chee, D. Han and J. Hong, "New Block Cipher: ARIA," ICISC'03, LNCS 2971, pp. 443-456, Springer-Verlag, 2003.
D. Hong, J. Sung, S. Hong, J. Lim, S. Lee, B.S. Koo, C. Lee, D. Chang, J. Lee, K. Jeong, H. Kim, J. Kim and S. Chee, "HIGHT: a new block cipher suitable for low-resource device," CHES 2006, LNCS 4249, pp. 46-59, Springer-Verlag, 2006.
A. Bogdanov, L.R. Knudsen, G. Leander, C. Paar, A. Poschmann, M.J.B. Robshaw, Y. Seurin and C. Vikkelsoe "PRESENT: An Ultra-Lightweight Block Cipher," CHES 2007, LNCS 4727, pp. 450-466, Springer-Verlag, 2007.
C. Canniere, O. Dunkelman and M. Knezevic, "KATAN and KTANTAN - a family of small and efficient hardware-oriented block ciphers," CHES 2009, LNCS 5747, pp. 272-288, Springer-Verlag, 2009.
E. Biham and A. Shamir, "Differential Fault Analysis of Secret Key Cryptosystems," Crypto 1997, LNCS 1294, pp. 513-525, 1997.
J. Blomer and J.-P. Seifert. "Fault based cryptanalysis of the advanced encryption standard (AES)." In Financial Cryptography, FC 2003, LNCS 2742, pp. 162-181, 2003.
P. Dusart, G. Letourneux, and O. Vivolo, "Differential fault analysis on AES," ACNS 2003, LNCS 2846, pp. 293-306, 2003.
C. Giraud, "DFA on AES," 4th International Conference, AES 2004, LNCS 3373, pp. 27-41, 2005.
D. Mukhopadhyay, "An improved fault based attack of the advanced encryption standard," AFRICACRYPT 2009, LNCS 5580, pp. 421-434, 2009.
L. Hemme, "A differential fault analysis against early rounds of (Triple-) DES," CHES 2004, LNCS 3156, pp. 254-267, 2006.
H. Chen, W. Wu, and D. Feng, "Differential fault analysis on CLEFIA," ICICS 2007, LNCS 4861 pp. 284-295, 2007.
K. Jeong, Y. Lee, J. Sung, and S. Hong, "Differential fault analysis on block cipher SEED," Mathematical and Computer Modelling, Vol. 55, No. 1-2, pp. 26-34, Jan. 2012.

상세보기
W. Li, D. Gu and J. Li, "Differential fault analysis on the ARIA algorithm," Information Sciences, Vol. 178, No. 19, pp. 3727-3737, Oct. 2008.

상세보기
W. Li, D. Gu, and Y. Wang. "Dierential fault analysis on the contracting UFN structure, with application to SMS4 and Macguffin." Journal of Systems and Software, Vol. 82, No. 2, pp. 346-354, Feb. 2009.

상세보기

저자의 다른 논문 :

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

연합인증