차분 오류 공격(DifferentialFault Analysis)은 블록 암호 알고리즘의 안전성 분석에 널리 사용되는 부채널 기법 중 하나이다. 차분 오류 공격은 대표적인 블록 암호인 DES, AES, ARIA, SEED와 경량 블록 암호인 PRESENT, HIGHT 등에 적용되었다[1,2,3,4,5,6]. 본 논문에서는 최근 주목 받고 있는 국내 경량 블록 암호 LEA(Lightweight Encryption Algorithm)에 대한 차분 오류 공격을 최초로 제안한다. 본 논문에서 제안하는 LEA에 대한 차분 오류 공격은 300개의 선택적 오류 주입 암호문을 이용하여 $2^{35}$의 시간 복잡도로 128 비트 마스터키 전체를 복구한다. 본 연구의 실험 결과, Intel Core i5 CPU, 메모리 8 GB의 일반 PC 환경에서 수집한 오류 주입 암호문을 이용하여, 평균 40분 이내에 마스터 키를 찾을 수 있음을 확인하였다.
차분 오류 공격(Differential Fault Analysis)은 블록 암호 알고리즘의 안전성 분석에 널리 사용되는 부채널 기법 중 하나이다. 차분 오류 공격은 대표적인 블록 암호인 DES, AES, ARIA, SEED와 경량 블록 암호인 PRESENT, HIGHT 등에 적용되었다[1,2,3,4,5,6]. 본 논문에서는 최근 주목 받고 있는 국내 경량 블록 암호 LEA(Lightweight Encryption Algorithm)에 대한 차분 오류 공격을 최초로 제안한다. 본 논문에서 제안하는 LEA에 대한 차분 오류 공격은 300개의 선택적 오류 주입 암호문을 이용하여 $2^{35}$의 시간 복잡도로 128 비트 마스터키 전체를 복구한다. 본 연구의 실험 결과, Intel Core i5 CPU, 메모리 8 GB의 일반 PC 환경에서 수집한 오류 주입 암호문을 이용하여, 평균 40분 이내에 마스터 키를 찾을 수 있음을 확인하였다.
Differential Fault Analysis(DFA) is widely known for one of the most powerful method for analyzing block cipher. it is applicable to block cipher such as DES, AES, ARIA, SEED, and lightweight block cipher such as PRESENT, HIGHT. In this paper, we introduce a differential fault analysis on the lightw...
Differential Fault Analysis(DFA) is widely known for one of the most powerful method for analyzing block cipher. it is applicable to block cipher such as DES, AES, ARIA, SEED, and lightweight block cipher such as PRESENT, HIGHT. In this paper, we introduce a differential fault analysis on the lightweight block cipher LEA for the first time. we use 300 chosen fault injection ciphertexts to recover 128-bit master key. As a result of our attack, we found a full master key within an average of 40 minutes on a standard PC environment.
Differential Fault Analysis(DFA) is widely known for one of the most powerful method for analyzing block cipher. it is applicable to block cipher such as DES, AES, ARIA, SEED, and lightweight block cipher such as PRESENT, HIGHT. In this paper, we introduce a differential fault analysis on the lightweight block cipher LEA for the first time. we use 300 chosen fault injection ciphertexts to recover 128-bit master key. As a result of our attack, we found a full master key within an average of 40 minutes on a standard PC environment.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 128 비트의 마스터 키를 사용하는 LEA에 대한 차분 오류 공격을 처음으로 제안하였다. 본 논문에서 제안하는 차분 오류 공격에서는 약 3300개의 오류 주입을 통해 공격에 필요한 오류 주입 암호문 300개를 선택적으로 획득하고, 이를 통해 시간 복잡도 235으로 마스터 키를 유일하게 복구할 수 있다.
본 논문에서는 블록 암호 LEA에 대한 차분 오류 공격을 제안하였다. 공격자는 24 라운드 입력 레지스터 32 비트에 랜덤한 1 비트 오류를 주입하여 얻어진 암호문과 정상적인 암호문의 차분 특성을 이용하여 24 라운드 키 후보를 구하고, 이를 통해 옳은 마스터 키를 복구가 가능함을 보였다.
본 절에서는 LEA-192, LEA-256에 대한 차분 오류 공격 방법과 복잡도에 대해 설명한다. 기본적인 공격 방법은 LEA-128과 동일하게 마지막 라운드 키에 대한 후보를 결정한 후 마스터 키를 복구한다.
가설 설정
본 논문에서 제안하는 LEA에 대한 차분 오류 공격에 사용되는 오류 주입은 32 비트 랜덤 오류 주입을 가정한다. 즉, 공격자는 원하는 라운드의 32 비트 입력 레지스터에 랜덤한 한 비트 오류를 주입할 수 있다.
제안 방법
본 절에서는 제안하는 LEA에 대한 차분 오류 공격을 실제 프로그램으로 작성하여 수행한 결과를 설명한다. 25개의 올바른 평문/암호문 쌍을 이용하여 X24[1], X24[2], X24[3]의 1, 8, 16, 24,번째 비트 위치에 오류가 주입된 암호문 각 25개씩 총 300개의 오류 주입 암호문 쌍을 사용하여 공격을 수행하였다. 특정 위치에 오류 주입된 암호문을 얻기 위해 3.
본 논문에서는 α, β, γ를 각각 2개로 구하여 총 235개의 24 라운드 후보로 마스터 키 추측을 수행하였으며, α, β, γ의 결정 방법은 4.3절에서 설명한다.
그 다음 얻은 라운드 키 후보와 Table 4. 의 알고리즘을 이용하여 마스터 키 복구를 수행하였다. 여기서 각 라운드 키 후보마다 옳은 키인지 확인하기 위해 역 키 스케줄 1회, LEA 암호화 1회를 수행한다.
효율적인 공격을 위해 오류 주입 수와 위치를 알맞게 결정하는 것이 중요하다. 제안하는 공격에서는 X24[1], X24[2], X24[3]의 위치에 오류 주입을 하며, 각 32 비트의 1, 8, 16, 24번째 비트에 오류가 주입된 암호문을 사용한다.
대상 데이터
공격자는 24 라운드 입력 레지스터 32 비트에 랜덤한 1 비트 오류를 주입하여 얻어진 암호문과 정상적인 암호문의 차분 특성을 이용하여 24 라운드 키 후보를 구하고, 이를 통해 옳은 마스터 키를 복구가 가능함을 보였다. 24 라운드 입력 레지스터의 특정 12 비트 위치에 오류를 주입하여 얻은 300개의 오류 주입 암호문을 이용하여 235의 시간 복잡도로 128 비트 마스터 키를 찾았다. 본 공격에 대한 기본적인 아이디어는 LEA-192, LEA-256에서 동일하게 적용 가능하며 28 라운드, 32 라운드 키 후보의 개수를 각각 299개로 구할 수 있다.
먼저 24 라운드의 키 정보에 대한 후보를 얻기 위해 올바른 평문/암호문 쌍 25개를 통해 수집한 300개의 오류 주입 암호문으로 1000회의 실험을 한 결과 100%의 확률로 rk24[0](2개), rk24[1]⊕rk24[2] (2개), rk24[3]⊕rk24[4](2개)의 후보를 획득하였다.
24 라운드 입력 레지스터의 특정 12 비트 위치에 오류를 주입하여 얻은 300개의 오류 주입 암호문을 이용하여 235의 시간 복잡도로 128 비트 마스터 키를 찾았다. 본 공격에 대한 기본적인 아이디어는 LEA-192, LEA-256에서 동일하게 적용 가능하며 28 라운드, 32 라운드 키 후보의 개수를 각각 299개로 구할 수 있다. 다만 키 스케줄의 차이로 LEA-192는 299의 시간 복잡도로 공격이 가능하지만, LEA-256은 2163의 시간 복잡도로 공격이 가능하다.
25개의 올바른 평문/암호문 쌍을 이용하여 X24[1], X24[2], X24[3]의 1, 8, 16, 24,번째 비트 위치에 오류가 주입된 암호문 각 25개씩 총 300개의 오류 주입 암호문 쌍을 사용하여 공격을 수행하였다. 특정 위치에 오류 주입된 암호문을 얻기 위해 3.2절의 내용을 이용하였고, 시뮬레이션을 통해 약 3300번의 오류 주입을 통해 약 85%의 확률로 원하는 오류 주입 암호문을 획득할 수 있었다. 실험 환경은 다음과 같다.
성능/효과
본 논문에서는 블록 암호 LEA에 대한 차분 오류 공격을 제안하였다. 공격자는 24 라운드 입력 레지스터 32 비트에 랜덤한 1 비트 오류를 주입하여 얻어진 암호문과 정상적인 암호문의 차분 특성을 이용하여 24 라운드 키 후보를 구하고, 이를 통해 옳은 마스터 키를 복구가 가능함을 보였다. 24 라운드 입력 레지스터의 특정 12 비트 위치에 오류를 주입하여 얻은 300개의 오류 주입 암호문을 이용하여 235의 시간 복잡도로 128 비트 마스터 키를 찾았다.
이를 실제 프로그램 상으로 1000회의 실험을 수행한 결과, 1100회 시행 이내에 특정 4 비트 위치 오류 주입 암호문을 각각 25개 이상 얻는 경우가 총 840~870회 발생하였다. 다시 말하면, 공격자가 원하는 특정 4 비트 위치의 오류 주입 암호문을 각각 25개 이상을 얻기 위해 32 비트 입력 레지스터에 랜덤한 오류 주입을 1100회 시도한다면, 약 84~87%의 확률로 필요한 오류 주입 암호문을 얻을 수 있다.
실제 LEA-128의 키 스케줄을 살펴보면, 마스터 키를 주입한 내부 변수T 와 상수 δ 값들에 대한 법덧셈, 비트순환이동의 반복적인 수행으로 라운드 키를 생성한다. 따라서 마지막 라운드인 24 라운드의 키를 입력하여 기존의 키 스케줄을 역으로 수행하면 모든 라운드 키를 복구할 수 있고, 마스터 키까지 모두 복구 가능하다. 이렇게 복구된 마스터 키가 옳은 키인지 확인하는 과정이 필요하다.
여기서 각 라운드 키 후보마다 옳은 키인지 확인하기 위해 역 키 스케줄 1회, LEA 암호화 1회를 수행한다. 마스터 키 검출 프로그램을 통한 모든 라운드 키 후보를 조사하는데 역 키 스케줄 235회, LEA 암호화 235회의 연산이 필요하며, 평균적으로 수행 시간 40분 이내에 옳은 마스터 키가 유일하게 복구되었다.
본 논문에서는 128 비트의 마스터 키를 사용하는 LEA에 대한 차분 오류 공격을 처음으로 제안하였다. 본 논문에서 제안하는 차분 오류 공격에서는 약 3300개의 오류 주입을 통해 공격에 필요한 오류 주입 암호문 300개를 선택적으로 획득하고, 이를 통해 시간 복잡도 235으로 마스터 키를 유일하게 복구할 수 있다. 또한, 192, 256 비트 마스터 키를 사용하는 LEA의 마스터 키를 복구하기 위해서는 동일한 오류 주입 암호문의 개수와 299, 2163의 시간 복잡도를 요구한다.
후속연구
다만 키 스케줄의 차이로 LEA-192는 299의 시간 복잡도로 공격이 가능하지만, LEA-256은 2163의 시간 복잡도로 공격이 가능하다. 향후 연구 과제로는 더 적은 수의 오류 주입과 암호문을 통한 최적화 LEA 차분 오류 공격과 대응 기법에 대해 추가적으로 연구할 예정이다.
질의응답
핵심어
질문
논문에서 추출한 답변
부채널 분석은 무엇인가?
부채널 분석(Side Channel Analysis)은 암호 알고리즘이 탑재된 보안 장비가 작동할 때 발생하는 전력신호, 전자파, 소리 등의 부가적인 정보를 이용하는 공격 방법이다. 대표적인 부채널 분석 방법은 전력 분석(Power Analysis), 시차 공격(Timing Attack), 오류 주입 공격(Fault Attack)이 있다.
차분 오류 공격은 무엇인가?
대표적인 부채널 분석 방법은 전력 분석(Power Analysis), 시차 공격(Timing Attack), 오류 주입 공격(Fault Attack)이 있다. 차분 오류 공격은 기존의 암호 알고리즘 안전성 분석 방법인 차분 공격에 부채널 분석 방법 중 하나인 오류 주입 공격을 결합한 공격 방법이다. 1997년 Biham과 Shamir는 최초로 블록 암호 DES에 차분 오류 공격을 적용하였다[1].
LEA 암호 알고리즘은 몇 비트의 마스터 키를 사용할 수 있는가?
LEA 암호 알고리즘은 128 비트 블록단위로 암·복호화하는 경량 블록 암호이다[7]. 128, 192, 256 비트의 마스터 키를 사용할 수 있으며, 각 마스터 키의 길이에 따라 LEA-128, LEA-192, LEA-256 으로 구분한다. LEA의 라운드 함수는 S-box를 사용하지 않고, 32 비트 단위의 법덧셈(⊞) 및 법뺄셈(⊟), 좌·우측 비트 순환이동(ROL, ROR), XOR(⊕) 연산만으로 구성되어 있어 경량 구현이 가능하다.
참고문헌 (14)
E. Biham and A. Shamir, "Differential Fault Analysis of Secret Key Cryptosystems," Proceedings of Crypto 1997, LNCS 1294, pp. 513-525, Aug. 1997.
J. Blomer and J.-P. Seifert, "Fault based cryptanalysis of the advanced encryption standard (AES)," Proceedings of FC 2003, LNCS 2742, pp. 162-181, Jan. 2003.
W Li. D Cu and J Li, "Differential fault analysis on the ARIA algorithm," Information Sciences, vol. 178, no. 19, pp. 3727-3739, Oct. 2008.
Kitae Jeong, Jaechul Sung, and Seokhie Hong, "A Differential Fault Attack on Block Cipher SEED," Journal of the Korea Institute of Information Security & Cryptology, 20(4), pp. 17-24, Aug. 2010.
Sehyun Park, Kitae Jeong, Yuseop Lee, Jaechul Sung and Seokhie Hong, "Improved Differential Fault Analysis on Block Cipher PRESENT-80/128," Jonornal of the Korea Institute of Information Security & Cryptology, 22(1), pp. 33-41, Feb. 2012
Yuseop Lee, Jongsung Kim and Seokhee Hong, "A Differential Fault Attack against Block Cipher HIGHT," Jonornal of the Korea Institute of Information Security & Cryptology, 22(3), pp. 485-494, Feb. 2012.
J. Park, D. Hong, D. Kim, D. Kwon and H. Park, "128-Bit Block Cipher LEA," TTAK.KO-12.0223, Dec. 2013.
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," Proceedings of ICISC 2003, LNCS 2971, pp. 443-456, Nov. 2003.
J. Park, S. Lee, J. Kim, and J. Lee, "The SEED Encryption Algorithm," RFC 4009, Dec. 2005.
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," Proceedings of CHES 2006, LNCS 4249, pp. 46-59, Oct. 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," Proceedings of CHES 2007, LNCS 4727, pp. 450-466, Sep. 2007.
C. Canniere, O. Dunkelman and M. Knezevic. "KATAN and KTANTAN - a family of small and efficient hardware- oriented block cipohers," Proceedings of CHES 2009, LNCS 5747, pp. 272-288, Sep. 2009.
Sehyun Park, Kitae Jeong, Yuseop Lee, Jaechul Sung, and Seokhie Hong, "Differential Fault Analysis on Block Cipher ARIA-128," Jonornal of the Korea Institute of Information Security & Cryptology, 21(5), pp. 15-25, Oct. 2011.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.