MILP를 이용한 ARX 기반 블록 암호의 불능 차분 특성 탐색
Searching for Impossible Differential Characteristics of ARX-Based Block Cipher Using MILP
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
불능 차분 특성은 해당 블록 암호를 랜덤 치환과 구별을 해주며, 키 복구 공격에도 사용될 수 있다. 최근 Cui 등이ARX 기반 블록 암호에 대해 Mixed-Integer Linear Programming(MILP)를 이용해서 자동화된 불능 차분 특성탐색 방법을 제안하였다. Cui 등이 제안한 방법을 개선하면 기존에 방법에 비해 더 적은 선형 제약식을 이용하여 기존방식으로 찾지 못하는 불능 차분 특성까지 추가 되어 더 많은 불능 차분 특성을 찾아 낼 수 있다. 수정한 방법을 이용하여 SPECK family와 LEA에 적용하였다. SPECK32, SPECK48, SPECK64, SPECK96에 대해 7-라운드, SPECK128에 대해 8-라운드 불능 차분 특성을 찾아내었다. 이 불능 차분 특성은 모두 새롭게 발견된 것이다. LEA에대해서는 기존의 10-라운드인 불능 차분 특성을 포함한 새로운 10-라운드 불능 차분 특성을 찾아내었다.
Abstract
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.
참고문헌 (21)
- Knudsen, Lars, "DEAL-a 128-bit block cipher", complexity, 258(2), pp.216~ (1998)
- Biham, Eli, "Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials", International Conference on the Theory and Applications of Cryptographic Techniques, pp.12~23 (1999), Springer Berlin Heidelberg
- Kim, J., "Impossible differential cryptanalysis for block cipher structures", International Conference on Cryptology in India Springer Berlin Heidelberg, pp.82~96 (2003)
- Luo, Y., "A unified method for finding impossible differentials of block cipher structures", Information Sciences, 263, pp.211~220 (2014)
- Wu, Shengbao, "Automatic search of truncated impossible differentials for word-oriented block ciphers", International Conference on Cryptology in India. Springer Berlin Heidelberg, pp.283~302 (2012)
- Mouha, N., "Differential and linear cryptanalysis using mixed-integer linear programming", International Conference on Information Security and Cryptology, pp.57~76 (2011), Springer Berlin Heidelberg
- Wu, Shengbao, "Security Evaluation against Differential Cryptanalysis for Block Cipher Structures", IACR Cryptology ePrint Archive, 2011, pp.551~ (2011)
- Sun, S., "Automatic security evaluation of block ciphers with S-bP structures against related-key differential attacks", International Conference on Information Security and Cryptology, pp.39~51 (2013), Springer International Publishing
- Fu, K., "Milp-based automatic search algorithms for differential and linear trails for speck", International Conference on Fast Software Encryption, pp.268~288 (2016), Springer Berlin Heidelberg
- New automatic search tool for impossible differentials and zero-correlation linear approximations, "Cui, T.", Cryptology ePrint Archive, ~ (2016)
- Sasaki, Yu, "New impossible differential search tool from design and cryptanalysis aspects", Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp.185~215 (2017)
- Xiang, Z., "Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers", Advances in Cryptology–ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, pp.648~678 (2016)
- Sun, Ling, "Milp-aided bit-based division property for primitives with non-bit-permutation linear layers", IACR Cryptology ePrint Archive, 811 (2016)
- Sun, Ling, "MILP-Aided Bit-Based Division Property for ARX-Based Block Cipher", IACR Cryptology ePrint Archive, 2016, pp.1101~ (2016)
- Lipmaa, Helger, "Efficient algorithms for computing differential properties of addition", International Workshop on Fast Software Encryption, pp.336~350 (2001), Springer Berlin Heidelberg
- Sun, S., "Automatic security evaluation and(related-key)differential characteristic search : application to SIMON, PRESENT, LBlock, DES(L)and other bit-oriented block ciphers", International Conference on the Theory and Application of Cryptology and Information Security, pp.158~178 (2014)
- Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of(related-key)differential and linear characteristics with predefined properties, "Sun, S.", Cryptology ePrint Archive, ~ (2014)
- Beaulieu, R., "The SIMON and SPECK lightweight block ciphers", Design Automation Conference (DAC), 52nd ACM, IEEE, pp.2015[DOI]
- Hong, D., "LEA: A 128-bit block cipher for fast encryption on common processors", International Workshop on Information Security Applications, pp.3~27 (2013), Springer International Publishing