[논문]경량 암호 알고리듬 CHAM에 대한 오류 주입 공격

권홍필; 하재철

doi:10.13089/jkiisc.2018.28.5.1071

경량 암호 알고리듬 CHAM에 대한 오류 주입 공격
Fault Injection Attack on Lightweight Block Cipher CHAM 원문보기

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

초록
AI-Helper

최근 가용 자원이 제한된 디바이스에서 사용할 수 있는 구현 성능이 효율적인 경량 블록 암호 알고리듬 CHAM이 제안되었다. CHAM은 키의 상태를 갱신하지 않는 스케줄링 기법을 사용함으로써 키 저장 공간을 획기적으로 감소시켰으며, ARX(Addition, Rotation, and XOR) 연산에 기반하여 설계함으로써 계산 성능을 크게 향상시켰다. 그럼에도 불구하고 본 논문에서는 CHAM은 오류 주입 공격에 의해 라운드 키가 노출될 가능성이 있으며 4개의 라운드 키로부터 마스터 비밀 키를 추출할 수 있음을 보이고자 한다. 제안된 오류 주입 기법을 사용하면 약 24개의 정상-오류 암호문 쌍을 이용하여 CHAM-128/128에 사용된 비밀 키를 찾을 수 있음을 컴퓨터 시뮬레이션을 통해 확인하였다.

Abstract ▼ AI-Helper

Recently, a family of lightweight block ciphers CHAM that has effective performance on resource-constrained devices is proposed. The CHAM uses a stateless-on-the-fly key schedule method which can reduce the key storage areas. Furthermore, the core design of CHAM is based on ARX(Addition, Rotation and XOR) operations which can enhance the computational performance. Nevertheless, we point out that the CHAM algorithm may be vulnerable to the fault injection attack which can reveal 4 round keys and derive the secret key from them. As a simulation result, the proposed fault injection attack can extract the secret key of CHAM-128/128 block cipher using about 24 correct-faulty cipher text pairs.

주제어

표/그림 (7)

그림 Fig. 1. Key schedule functions
그림 Fig. 2. Two round functions beginning with the even i-th round
그림 Fig. 3. Fault Injection attack model on CHAM
그림 Fig. 4. Candidates of intermediate cipher value
그림 Fig. 5. Secret key recovery from round key
그림 Fig. 6 The number of round key candidates using one or six correct-faulty cipher text pair(s)
표 Table 1. Number of round key candidates according to correct-faulty cipher text pairs

AI 본문요약
AI-Helper

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

문제 정의

CHAM-128/128에 대한 제안된 오류 주입 공격 방법을 이용하여 공격자가 약 24개의 오류 암호문을 획득하면 사용된 라운드 키를 찾을 수 있으며, 추출한 4개의 라운드 키로부터 마스터 비밀 키를 복구할 수 있다. 논문에서는 CHAM에 대한 랜덤 워드에 기반한 오류 주입 공격 모델이 논리적으로 타당함을 컴퓨터 시뮬레이션을 통해 확인하였다.
본 논문에서는 경량 블록 암호 알고리듬 CHAM이 오류 주입 공격에 대해 어떠한 취약성이 있는지 그리고 실제 라운드 키가 노출될 가능성은 있는지를 분석하고 그 공격 모델을 제안하고자 한다. CHAM-128/128에 대한 제안된 오류 주입 공격 방법을 이용하여 공격자가 약 24개의 오류 암호문을 획득하면 사용된 라운드 키를 찾을 수 있으며, 추출한 4개의 라운드 키로부터 마스터 비밀 키를 복구할 수 있다.
본 논문에서는 경량 암호 알고리듬 CHAM에 대한 오류 주입 공격에 대한 취약성과 공격 모델을 찾을 수 있었다. CHAM은 6개 정도의 정상-오류 암호문 쌍을 가지면 충분히 라운드 키를 찾아낼 수 있으며, 약 2⁴번의 검증 연산을 통해 4개의 라운드 키를 모두 찾을 수 있었다.
본 논문에서는 전탐색 기법을 사용하지 않고 라운드 키로부터 마스터 비밀 키를 구하는 방법을 제안하 고자 한다. 상기한 Fig.
본 절에서는 CHAM에 대한 오류 주입 공격 모델을 제안하고자 한다. 오류 주입 공격에서는 오류가 주입된 출력을 분석하여 비밀 키를 바로 분석하는 경우도 있지만 중간 결과 값을 추출한 후 최종적으로 라운드 키나 비밀 키를 추출하기도 한다.
본 절에서는 라운드 키를 알고 있는 공격자가 마스터 비밀 키를 추출하는 과정을 살펴보고자 한다. 라운드 키 생성 과정을 수식으로 정리하면 아래와 같은데 하나의 비밀 키워드로부터 두 개의 라운드 키를 계산한다.

가설 설정

제안하는 오류 주입 공격 모델에서 가장중요한 부분은 차분 오류를 구하기 위해 오류를 주입하는 위치와 오류 단위이다. CHAM에 대한 오류 공격 모델을 나타낸 것이 Fig. 3인데 여기서 오류위치는 암호 알고리듬의 마지막 라운드이며 오류 단위는 랜덤한 워드 오류(single random wordfault)가 주입되었음을 가정한다.

제안 방법

CHAM은 6개 정도의 정상-오류 암호문 쌍을 가지면 충분히 라운드 키를 찾아낼 수 있으며, 약 2⁴번의 검증 연산을 통해 4개의 라운드 키를 모두 찾을 수 있었다. 또한, 라운드 키를 알고 있을 경우 간단한 회전 이동 분석 공격을 통해 한 워드의 비밀 키를 찾을 수 있고 4개의 라운드 키로 마스터 비밀 키 전체를 찾을 수 있음을 컴퓨터 시뮬레이션을 통해 확인하였다.
오류 주입 공격을 타당성을 검증하기 위해 먼저 CHAM을 C언어로 구현하고 정상 암호문과 오류 주입을 가정한 오류 암호문을 수집하여 분석함으로써 비밀 키를 찾아낼 수 있음을 시뮬레이션하였다. 처음 시뮬레이션에서는 몇 개의 정상-오류 암호문 쌍을 가지고 하나의 라운드 키를 찾을 수 있는지 실험하였다.
이 암호 알고리듬에서는 키 상태를 갱신하지 않으면서 라운드 키를 생성하는 키 스케줄링 기법을 사용함으로써 키 저장 공간을 획기적으로 줄였으며 ARX(Addition, Rotation, and XOR)에 기반한 간단한 연산자를 사용하도록 설계함으로써 계산 성능을 향상시켰다,
본 논문에서 제안하는 오류 주입 공격은 정상 암호문과 오류 암호문을 차분하는 방식을 이용하여 중간 결과 값을 추출한 후 라운드 키를 계산하는 차분 오류 분석(Differential Fault Analysis, DFA) 기법이다. 제안하는 오류 주입 공격 모델에서 가장중요한 부분은 차분 오류를 구하기 위해 오류를 주입하는 위치와 오류 단위이다. CHAM에 대한 오류 공격 모델을 나타낸 것이 Fig.
오류 주입 공격을 타당성을 검증하기 위해 먼저 CHAM을 C언어로 구현하고 정상 암호문과 오류 주입을 가정한 오류 암호문을 수집하여 분석함으로써 비밀 키를 찾아낼 수 있음을 시뮬레이션하였다. 처음 시뮬레이션에서는 몇 개의 정상-오류 암호문 쌍을 가지고 하나의 라운드 키를 찾을 수 있는지 실험하였다. Table 1은 오류 주입 공격에 필요한 정상-오류 암호문 쌍 수와 가능한 라운드 키의 개수를 나타낸 것이다.
동일한 방법으로 4개의 정상-암호문 쌍을 이용하면 중간 암호문의 범위를 약 4개까지 축소시킬 수 있었다. 최종적으로 50%이상의 확률로 2개의 중간 암호 문(라운드 키)을 얻기 위해서는 6개의 정상-오류 암호문 쌍이 필요하였다. 마지막 라운드 키 후보는 최소 2개까지 줄일 수 있는데 그 이유는 암호화 연산 시 각 라운드에서 mod 2^w 에 대한 모듈러 덧셈 시 캐리(carry)가 발생해서 무시한 경우와 캐리가 발생하지 않는 경우 즉, 2가지 형태의 연산이 존재하기 때문이다.

성능/효과

본 논문에서는 경량 블록 암호 알고리듬 CHAM이 오류 주입 공격에 대해 어떠한 취약성이 있는지 그리고 실제 라운드 키가 노출될 가능성은 있는지를 분석하고 그 공격 모델을 제안하고자 한다. CHAM-128/128에 대한 제안된 오류 주입 공격 방법을 이용하여 공격자가 약 24개의 오류 암호문을 획득하면 사용된 라운드 키를 찾을 수 있으며, 추출한 4개의 라운드 키로부터 마스터 비밀 키를 복구할 수 있다. 논문에서는 CHAM에 대한 랜덤 워드에 기반한 오류 주입 공격 모델이 논리적으로 타당함을 컴퓨터 시뮬레이션을 통해 확인하였다.
본 논문에서는 경량 암호 알고리듬 CHAM에 대한 오류 주입 공격에 대한 취약성과 공격 모델을 찾을 수 있었다. CHAM은 6개 정도의 정상-오류 암호문 쌍을 가지면 충분히 라운드 키를 찾아낼 수 있으며, 약 2⁴번의 검증 연산을 통해 4개의 라운드 키를 모두 찾을 수 있었다. 또한, 라운드 키를 알고 있을 경우 간단한 회전 이동 분석 공격을 통해 한 워드의 비밀 키를 찾을 수 있고 4개의 라운드 키로 마스터 비밀 키 전체를 찾을 수 있음을 컴퓨터 시뮬레이션을 통해 확인하였다.
결론적으로 CHAM-128/128에서 오류 주입 공격에 의해 RK[4]~RK[7]까지 4개의 라운드 키를 추출한 공격자는 전탐색 공격을 하지 않더라도 4 × 211번의 비밀 키 복구 연산을 통해 128비트 마스터 비밀 키를 모두 추출할 수 있다.
개의 라운드 키 후보를 얻을 수 있게 된다. 결론적으로 CHAM-128/128에서는 하나의 정상 암호문과 약 24개의 오류 암호문을 이용하여 2⁴의 복잡도로 4개의 라운드 키를 찾을 수 있으며 이 라운드 키로부터 비밀 키를 완전히 복구할 수 있다.
또한, i번째 라운드에서 왼쪽 라운드 키(RK[0]~RK[3])는 각 비밀 키 워드를 왼쪽으로 1번 그리고 8번 회전 이동 후 원 비밀 키와 XOR 연산을 수행한 것이다. 따라서 제안 방법을 동일한 원리로 적용하면 하나의 라운드 키를 획득한 공격자는 2⁸의 복잡도로 하나의 비밀 키 워드를 추출할 수 있다.
의 복잡도로 8개의 라운드 키를 찾을 수 있다. 또한, 워드의 길이가 16비트인 CHAM-64/128을 공격할 경우에는 하나의 라운드 키를 추출하는데 5개를 이용하면 50%이상의 확률로 라운드 키를 2개까지 추출할 수 있었다. 따라서 약 40(5개씩 8라운드)개의 오류 암호문과 2⁸의 복잡도로 8개의 라운드 키를 찾을 수 있다.
여기서 RK[i mod 2k/w]는 각 라운드 키를 나타낸다. 본 논문에서 설명하는 CHAM-128/128을 기준으로 할 때 8개의 라운드 키는 80라운드를 수행하는 동안 10번 반복해서 사용된다.
실제 분석 결과, LEA는 300개의 선택적 오류 주입 암호문을 이용하여 235 의 시간 복잡도로 128비트 마스터 비밀 키 전체를 추출할 수 있음이 증명되었다[13].
이 시뮬레이션은 총 100번 수행하였는데 하나의 정상-오류 암호문 쌍을 이용할 경우 2⁹개 이상의 중간 암호문 후보(라운드 키 후보와 같은 의미로 볼 수 있음)를 얻을 수 있었으며, 어떤 정상-오류 암호문 쌍을 이용할 경우에는 가능한 중간 암호문 C의 개수가 2¹⁵개 이상 검출되기도 하였다. 예를 들면, 표에서 1개의 정상-오류문을 가지는 경우, 키 후보가 2⁹개를 가지는 경우도 있으며 많게는 2¹⁵개를 가지는 경우가 있었다.
제안한 공격 기법을 CHAM-128/256에 동일한 원리로 적용할 수 있는데, 약 48(6개씩 8라운드)개의 정상-오류 암호문 쌍과 2⁸의 복잡도로 8개의 라운드 키를 찾을 수 있다. 또한, 워드의 길이가 16비트인 CHAM-64/128을 공격할 경우에는 하나의 라운드 키를 추출하는데 5개를 이용하면 50%이상의 확률로 라운드 키를 2개까지 추출할 수 있었다.

질의응답

핵심어	질문	논문에서 추출한 답변
	오류 주입 공격은 어디에 쉽게 적용 가능한가?	실제로 오류 주입 공격은 AES 및 RSA와 같은 표준 블록 암호 혹은 상용 공개 키 암호 시스템 등에 쉽게 적용 가능하며 경량 암호 알고리듬인 LEA나 SIMON/SPECK에 대한 공격도 시도된 바 있다. 실제 분석 결과, LEA는 300개의 선택적 오류 주입 암호문을 이용하여 235 의 시간 복잡도로 128비트 마스터 비밀 키 전체를 추출할 수 있음이 증명되었다[13].
	CHAM는 무엇을 감소시켰는가?	최근 가용 자원이 제한된 디바이스에서 사용할 수 있는 구현 성능이 효율적인 경량 블록 암호 알고리듬 CHAM이 제안되었다. CHAM은 키의 상태를 갱신하지 않는 스케줄링 기법을 사용함으로써 키 저장 공간을 획기적으로 감소시켰으며, ARX(Addition, Rotation, and XOR) 연산에 기반하여 설계함으로써 계산 성능을 크게 향상시켰다. 그럼에도 불구하고 본 논문에서는 CHAM은 오류 주입 공격에 의해 라운드 키가 노출될 가능성이 있으며 4개의 라운드 키로부터 마스터 비밀 키를 추출할 수 있음을 보이고자 한다.
	가용 자원이 제한된 디바이스에서 사용할 수 있는 구현 성능이 효율적인 경량 블록 암호 알고리듬 CHAM이 제안된 오류 주입 기법을 사용해 무엇을 알 수 있는가?	그럼에도 불구하고 본 논문에서는 CHAM은 오류 주입 공격에 의해 라운드 키가 노출될 가능성이 있으며 4개의 라운드 키로부터 마스터 비밀 키를 추출할 수 있음을 보이고자 한다. 제안된 오류 주입 기법을 사용하면 약 24개의 정상-오류 암호문 쌍을 이용하여 CHAM-128/128에 사용된 비밀 키를 찾을 수 있음을 컴퓨터 시뮬레이션을 통해 확인하였다.

참고문헌 (14)

National Institute of Standards and Technology, "Advanced Encryption Standards," NIST FIPS PUB 197, 2001.
D. Hong, J. Lee, D. Kim, D. Kwon, K. Ryu, and D. Lee, "LEA, A 128-bit block cipher for fast encryption on common processors," WISA'13, LNCS 8267, pp. 3-27, 2014.
TTA, "128-bit lightweight block cipher LEA," TTAK.KO-12.0223, Dec, 2013.
D. Hong, J. Sung, S. Hong, J. Lim, S.Lee, B. 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'06, LNCS 4249, pp. 46-59, 2006.
R. Beaulieu, D. Shors, J. Smith, S. Treatman-Clark, B. Weeks, and L. Wingers, "The SIMON and SPECK lightweight block ciphers," In Design Automation Conference(DAC'15), pp. 1-6, 2015.
B. Koo, D. Roh, H. Kim, Y. Jung, D. Lee, and D. Kwon, "CHAM: A Family of lightweight block ciphers for resource-constrained devices," ICISC'17, LNCS 10779, pp. 3-25, 2017.
H. Seo, "Memory-efficient imple- mentation of ultra-lightweight block cipher algorithm CHAM on low-end 8-bit AVR processors," Journal of The Korea Institute of Information Security & Cryptology(JKIISC), Vol. 28, No. 3, pp. 545-550, 2018.
P. Kocher, "Timing Attacks on Implementation of Diffie-Hellman, RSA, DSS, and Other Systems," CRYPTO'96, LNCS 1109, pp. 104-113, 1996.
J. Coron, "Resistance against differential power analysis for elliptic curve cryptosystems," CHES'99, LNCS 1717, pp. 292-302, 1999.
T. Messerges, E. Dabbis, and R. Sloan, "Power analysis attacks of modular exponentiation in smartcard," CHES'99, LNCS 1717, pp. 144-157, 1999.
E. Biham and A. Shamir, "Differential fault analysis of secret key cryptosystems," CRYPTO'97. LNCS 1294, pp. 513-525, 1997.
D. Boneh, R. DeMillo, and R. Lipton, "On the Importance of Checking Cryptographic Protocols for Faults," EUROCRYPT'97, LNCS 1233, pp. 37-51, 1997
M. Park, J. Kim, "Differential Fault Analysis of the Block Cipher LEA", Journal of The Korea Institute of Information Security & Cryptology (JKIISC), Vol. 24 No. 6, pp. 1117-1126, 2014.

원문보기 상세보기
H. Tupsamudre, S. Bisht, and D. Mukhopadhyay, "Differential Fault Analysis on the Families of SIMON and SPECK Ciphers," In Workshop on Fault Diagnosis and Tolerance in Cryptography(FDTC'14), pp. 40-48, 2014.

저자의 다른 논문 :

표제어: 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

연합인증