[논문]MILP를 이용한 ARX 기반 블록 암호의 불능 차분 특성 탐색

이호창; 강형철; 홍득조; 성재철; 홍석희

doi:10.13089/jkiisc.2017.27.3.427

MILP를 이용한 ARX 기반 블록 암호의 불능 차분 특성 탐색
Searching for Impossible Differential Characteristics of ARX-Based Block Cipher Using MILP 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.27 no.3, 2017년, pp.427 - 437

이호창 (고려대학교) , 강형철 (고려대학교) , 홍득조 (전북대학교) , 성재철 (서울시립대학교) , 홍석희 (고려대학교)

초록
AI-Helper

불능 차분 특성은 해당 블록 암호를 랜덤 치환과 구별을 해주며, 키 복구 공격에도 사용될 수 있다. 최근 Cui 등이 ARX 기반 블록 암호에 대해 Mixed-Integer Linear Programming(MILP)를 이용해서 자동화된 불능 차분 특성 탐색 방법을 제안하였다. Cui 등이 제안한 방법을 개선하면 기존에 방법에 비해 더 적은 선형 제약식을 이용하여 기존 방식으로 찾지 못하는 불능 차분 특성까지 추가 되어 더 많은 불능 차분 특성을 찾아 낼 수 있다. 수정한 방법을 이용하여 SPECK family와 LEA에 적용하였다. SPECK32, SPECK48, SPECK64, SPECK96에 대해 7-라운드, SPECK128에 대해 8-라운드 불능 차분 특성을 찾아내었다. 이 불능 차분 특성은 모두 새롭게 발견된 것이다. LEA에 대해서는 기존의 10-라운드인 불능 차분 특성을 포함한 새로운 10-라운드 불능 차분 특성을 찾아내었다.

Abstract ▼ AI-Helper

Impossible differential characteristics distinguish the corresponding block cipher from random substitution and can also be used for key recovery attack. Recently Cui et al. proposed an automatic method for searching impossible differential characteristics of several ARX - based block ciphers using Mixed Integer Linear Programming(MILP). By optimizing the method proposed by Cui et al., It was possible to find new impossible differential characteristics which could not be founded by the method by using less linear constraint expression than the existing method. It was applied to the SPECK family and LEA using the modified method. We found 7-rounds for SPECK32, SPECK48, SPECK64, SPECK96 and 8-rounds impossible differential characteristics of SPECK128. These impossible differential characteristics are all newly found. We also found existing 10-rounds of impossible differential characteristic and new 10-rounds of impossible differential characteristics of LEA.

주제어

AI 본문요약
AI-Helper

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

문제 정의

MILP를 이용하여 차분 특성을 탐색하기 위해서는 목적 함수를 차분 특성의 확률을 나타내는 식으로 설정하고, 선형 제약식은 해당 암호 시스템을 구성하는 식으로 구성한다. 구성한 암호 시스템에 대해서 MILP 문제의 답으로 해당 암호 시스템을 구성하는 최적의 차분 특성 확률을 구하는 것이다.
본 논문에서는 Cui 등[10]이 제안한 ARX 기반 블록 암호에 대한 MILP를 이용한 자동화된 불능 차분 특성 탐색 방법을 최적화하는 방법을 제안하였다. 그 결과를 이용해 더 적은 선형 제약식을 이용하여 SPECK32, SPECK48, SPECK64, SPECK96에 대해 7-라운드 불능 차분 특성을 각각 1개, 1개, 21개, 426개, SPECK128에 대해서 8-라운드 불능 차분 특성 8개를 찾아내었다.
본 논문에서는 주어진 ARX 구조 블록 암호에 대해 가장 긴 불능 차분 특성을 최대한 효율적으로 찾는 방법을 연구한다. 그 목적을 위하여 Cui 등이 제안한 MILP 기반 이용한 ARX 구조 블록 암호 블록 암호 불능 차분 특성 자동 탐색법을 개선한다.
하지만 SPECK family와 LEA의 헤밍 무게를 1 또는 2로 제한하여 탐색한 불능 차분 특성을 1의 확률로 연장하여 헤밍 무게가 1 또는 2가 아닌 불능 차분 특성을 만들 수 있다. 본 절에서는 탐색 범위를 확장하지 않고, 헤밍 무게가 1 또는 2가 아닌 더 긴 라운드의 불능 차분 특성을 만드는 해당 조건과 연장된 불능 차분 특성을 소개한다.

제안 방법

법 덧셈: Lipmaa와 Moriai가 제안한 정리를 만족하는 점들을 이용해 벡터 (α[i],β[i],γ[i],(α[i+1],β[i+1],γ[i+1],-eq(α[i],β[i],γ[i])) 로 표현할 경우 56개의 벡터가 생긴다. 56개의 벡터만을 표현할 수 있는 13개의 선형 제 약식으로 법 덧셈의 성질을 표현하였다.
본 논문에서는 Cui 등[10]이 제안한 ARX 기반 블록 암호에 대한 MILP를 이용한 자동화된 불능 차분 특성 탐색 방법을 최적화하는 방법을 제안하였다. 그 결과를 이용해 더 적은 선형 제약식을 이용하여 SPECK32, SPECK48, SPECK64, SPECK96에 대해 7-라운드 불능 차분 특성을 각각 1개, 1개, 21개, 426개, SPECK128에 대해서 8-라운드 불능 차분 특성 8개를 찾아내었다. 이 불능 차분 특성은 모두 새롭게 발견된 것들이고 기존 결과에 비해 더 긴 라운드를 갖는다.
본 논문에서는 주어진 ARX 구조 블록 암호에 대해 가장 긴 불능 차분 특성을 최대한 효율적으로 찾는 방법을 연구한다. 그 목적을 위하여 Cui 등이 제안한 MILP 기반 이용한 ARX 구조 블록 암호 블록 암호 불능 차분 특성 자동 탐색법을 개선한다. 개선된 방법을 SPECK family와 LEA에 적용한 결과, SPECK32, SPECK48, SPECK96에 대해 7-라운드, SPECK128에 대해 8-라운드 불능 차분 특성이 발견되었다.
모든 입·출력 차분 범위는 탐색의 경우의 수가 계산 능력을 뛰어넘기 때문에 입·출력차분의 헤밍 무게를 각각 1또는 2로 제한하여 탐색 범위를 계산 가능한 범위로 설정하였다.
본 장에서는 3장의 방법을 이용해 ARX 기반 블록 암호인 SPECK family와 LEA에 적용한 방법과 불능 차분 특성을 소개한다.

이론/모형

목적 함수를 설정하기 위해서 Lipmaa와 Moriai가 제안한 두 가지 정리를 이용하였고, 그 정리는 다음과 같다.

성능/효과

따라서 MILP를 이용하여 찾은 SPECK family의 불능 차분 특성에 대해서 입력 차분이 해당 성질을 만족시킬 경우 한 라운드를 연장 시킬 수 있으며, 역시 불능 차분 특성을 만족한다. MILP를 이용해 찾은 SPECK32, SPECK48, SPECK64, SPECK128의 가장 긴 라운드 불능 차분 특성을 각각 1개, 1개, 21개, 7개를 한 라운드 연장 시킬 수 있었다. SPECK96의 경우 7-라운드 불능 차분 특성에서 연장 할 수 있는 특성은 존재하지 않았지만 6-라운드 불능 차분 특성에서 391개의 차분 특성을 한 라운드 연장 할 수 있었다.
그 목적을 위하여 Cui 등이 제안한 MILP 기반 이용한 ARX 구조 블록 암호 블록 암호 불능 차분 특성 자동 탐색법을 개선한다. 개선된 방법을 SPECK family와 LEA에 적용한 결과, SPECK32, SPECK48, SPECK96에 대해 7-라운드, SPECK128에 대해 8-라운드 불능 차분 특성이 발견되었다. 이것들은 모두 새롭게 발견된 것들이다.
본 논문에서는 불능 차분 특성 탐색에 최적화 함에 따라 목적 함수를 넣을 필요가 없어졌고, 따라서 mycallback 함수를 사용하지 않다도 된다. 그 결과 최적화한 선형 제약식과 mycallback 함수를 사용하지 않고 탐색하여 불능 차분 특성 탐색을 실행할 경우 기존 방법으로 찾지 못하는 불능 차분 특성을 탐색할 수 있다. 예를 들어 SPECK64의 경우 mycallback 함수로 152개의 불능 차분 특성을 찾을 수 있었다.
즉, 가능의 여부만 고려하면 되는 불능 차분 특성 탐색에 대한 최적의 방법이 아니다. 따라서 차분 확률 계산 부분을 고려하지 않는 방법으로 최적화하여 가능해를 하나라도 구하는 경우 불능 차분 특성이 아닌 것을 이용하는 방법으로 [10]에서 제안한 방법의 성능을 향상 시킬 수가 있다.
법 덧셈 차분 확률까지 고려하는 13개의 선형 제 약식에서 가능 여부만을 표현하는 8개의 선형 제약식으로 줄임으로써 [10]에서 사용되는 선형 제약식의 개수보다 약 30% 줄일 수 있다. 또한 확률 계산 부분을 제외하였으므로 기존 방법의 목적 함수 부분이 더 이상 필요 없으므로 null로 변경한다.
예를 들어 SPECK64의 경우 mycallback 함수로 152개의 불능 차분 특성을 찾을 수 있었다. 하지만 본 논문에서 최적화한 선형 제약식으로 콜백 함수 없이 실행할 경우 157개의 불능 차분 특성을 얻을 수 있었다.

후속연구

LEA에 대해서는 기존의 10-라운드 불능 차분 특성과 새로운 10-라운드 불능 차분 특성 2개를 찾아내었다. 발견된 불능 차분 특성을 이용하여 키 복구 공격에 적용을 차후 연구 계획 중이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	프로그래밍 문제란?	프로그래밍 문제(Programming Problem)는 주어진 조건을 만족하는 목적 함수(Objective Function)의 최댓값 또는 최솟값을 구하는 수학적 최적화 문제이다. Mixed-Integer Linear Programming(MILP)는 제약식이 선형이고 일부 변수가 정수인 프로그래밍 문제이다.
	Cui 등이 제안한 MILP를 이용해 불능 차분 특성을 탐색하는 방법의 장점은?	Cui 등이 제안한 MILP를 이용해 불능 차분 특성을 탐색하는 방법은 -method, UID-method와 같은 기존의 방법들과 달리 비선형 부분의 성질까지 고려하여 더 많은 불능 차분 특성을 찾을 수 있도록 도와준다. 하지만 Cui 등이 제안한 방법은 Fu등이 제안한 차분 확률 계산 방법을 응용한 것으로, 모델링 방법에서 불능 차분 특성 탐색에는 필요없는 차분 확률 계산 부분이 들어있다.
	불능 차분 특성을 찾기 위한 방법으로 -method, UID-method와 두 방법을 포함하는 확장 툴[5] 등 여러 불능 차분 특성 탐색 방법들이 존재하는데 이 방법들의 한계는?	불능 차분 특성을 찾기 위한 방법으로 -method[3], UID-method[4]와 두 방법을 포함하는 확장 툴[5] 등 여러 불능 차분 특성 탐색 방법들이 존재한다. 하지만 이러한 방법들은 비선형 부분의 성질을 고려하지 않았다는 한계가 있다

참고문헌 (21)

Knudsen, Lars. "DEAL-a 128-bit block cipher." complexity vol.258, no.2, pp. 216, 1998.
Biham, Eli, Alex Biryukov, and Adi Shamir. "Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials." International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, pp. 12-23, May. 1999.
Kim, J., Hong, S., Sung, J., Lee, S., Lim, J., & Sung, S. "Impossible differential cryptanalysis for block cipher structures." In International Conference on Cryptology in India Springer Berlin Heidelberg, pp. 82-96, Dec. 2003.
Luo, Y., Lai, X., Wu, Z., & Gong, G. "A unified method for finding impossible differentials of block cipher structures." Information Sciences, vol.263, pp. 211-220, 2014.

상세보기
Wu, Shengbao, and Mingsheng Wang. "Automatic search of truncated impossible differentials for word-oriented block ciphers." International Conference on Cryptology in India. Springer Berlin Heidelberg, pp. 283-302, Dec. 2012.
Mouha, N., Wang, Q., Gu, D., & Preneel, B. "Differential and linear cryptanalysis using mixed-integer linear programming." In International Conference on Information Security and Cryptology pp. 57-76, Springer Berlin Heidelberg. Nov. 2011.
Wu, Shengbao, and Mingsheng Wang. "Security Evaluation against Differential Cryptanalysis for Block Cipher Structures." IACR Cryptology ePrint Archive vol.2011, pp. 551, 2011.
Sun, S., Hu, L., Song, L., Xie, Y., & Wang, P. "Automatic security evaluation of block ciphers with S-bP structures against related-key differential attacks." In International Conference on Information Security and Cryptology. Springer International Publishing, pp. 39-51, Nov. 2013.
Fu, K., Wang, M., Guo, Y., Sun, S., & Hu, L. "Milp-based automatic search algorithms for differential and linear trails for speck." In International Conference on Fast Software Encryption. Springer Berlin Heidelberg, pp. 268-288, Mar. 2016.
Cui, T., Jia, K., Fu, K., Chen, S., & Wang, M. "New automatic search tool for impossible differentials and zero-correlation linear approximations." Cryptology ePrint Archive, Report 2016/689. 2016.
Sasaki, Yu, and Yosuke Todo. "New impossible differential search tool from design and cryptanalysis aspects." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, pp. 185-215, Apr. 2017.
Xiang, Z., Zhang, W., Bao, Z., & Lin, D. "Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers." In Advances in Cryptology-ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I 22. Springer Berlin Heidelberg, pp. 648-678, Dec. 2016.
Sun, Ling, Wei Wang, and Meiqin Wang. "Milp-aided bit-based division property for primitives with non-bit-permutation linear layers." IACR Cryptology ePrint Archive, 2016: 811, 2016.
Sun, Ling, et al. "MILP-Aided Bit-Based Division Property for ARX-Based Block Cipher." IACR Cryptology ePrint Archive vol.2016, pp. 1101, 2016.
Lipmaa, Helger, and Shiho Moriai. "Efficient algorithms for computing differential properties of addition." International Workshop on Fast Software Encryption. Springer Berlin Heidelberg, pp. 336-350, Apr. 2001.
http://www.gurobi.com/
Sun, S., Hu, L., Wang, P., Qiao, K., Ma, X., & Song, L. "Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES (L) and other bit-oriented block ciphers." In International Conference on the Theory and Application of Cryptology and Information Security. Springer Berlin Heidelberg, pp. 158-178, Dec. 2014.
http://www.sagemath.org/
Sun, S., Hu, L., Wang, M., Wang, P., Qiao, K., Ma, X.,& Fu, K.. "Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of (related-key) differential and linear characteristics with predefined properties." Cryptology ePrint Archive, Report 2014/747. 2014
Beaulieu, R., Treatman-Clark, S., Shors, D., Weeks, B., Smith, J., & Wingers, L. "The SIMON and SPECK lightweight block ciphers." In Design Automation Conference (DAC), 52nd ACM/EDAC/IEEE, pp. 1-6, IEEE. Jun. 2015.
Hong, D., Lee, J. K., Kim, D. C., Kwon, D., Ryu, K. H., & Lee, D. G. "LEA: A 128-bit block cipher for fast encryption on common processors." In International Workshop on Information Security Applications. Springer International Publishing, pp. 3-27, Aug. 2013.

저자의 다른 논문 :

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

연합인증