효율적인 MILP-Espresso 기반 차분 특성 자동 탐색 방법
MILP-Espresso-Based Automatic Searching Method for Differential Charactertistics
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문은 Sasaki 등이 2018년도에 제안한 차분 특성 자동화 탐색 방법을 개선하여 MILP Solver로 정확하고간편하게 S-box 기반 암호의 차분 특성을 탐색하는 방법을 제안한다[13]. Sasaki 등이 제안한 방식은 차분 특성에 대한 제약식 설계에 입력 차분과 출력 차분만을 변수로 포함하여 확률을 별도로 계산한 반면, 논문에서 제안하는탐색 방법은 입력 차분, 출력 차분, 확률 변수를 하나의 제약식으로 구성하여 한 번의 프로그램 실행으로 특성과 확률을 동시에 확인할 수 있도록 탐색 절차를 간소화 하였다. 또한 본 논문에서는 Sasaki 등이 활용했던 Espresso알고리즘과 Quine- McCluskey 알고리즘 중에서 제약식이 보다 대폭 축소되는 Espresso 알고리즘을 이용해 제약식을 간소화 하였다. 본 논문에서 제안하는 탐색 방법은 다양한 구조와 블록 사이즈에 적용 가능함을 입증하기 위해 블록암호 GIFT-64, GIFT-128, SKINNY-64에 적용하였다. 적용 결과, GIFT의 경우 기존의 제안 논문에서4라운드의 최적의 차분 특성이 5개의 활성 S-box를 가진다고 제시한 반면, 본 논문을 적용한 결과에서는 활성S-box의 개수는 6개이지만 기존보다 좋은 2^11.415의 확률을 갖는 최적의 차분 특성을 찾는 성과가 있었다. SKINNY-64의 경우 기존보다 개선된 결과는 아니지만 제안 논문에서의 분석과 동일한 활성 S-box를 갖는 차분특성을 찾을 수 있었다.
Abstract
In this paper, we propose an MILP-based method for Optimal Probability of Bit-based Differential Characteristic inSP(Substitution-permutation) ciphers based on Automatic Differential Characteristic Searching Method of Sasaki, et al[13]. In[13], they used input/output variables and probability variables seperatably, but we simplify searching procedure by puttingthem(variables) together into linear inequalities. Also, In order to decrease the more linear inequalities, we choose Espressoalgorithm among that used by Sasaki, et al(Quine-McCluskey algorithm & Espresso algorithm). Moreover, we apply ourmethod to GIFT-64, GIFT-128, SKINNY-64, and we obtained results in the GIFT(Active S-boxs : 6, Probabilities :2^11.415) compared with the existing one.(Active S-boxs : 5, Probabilities : unknown). In case of SKINNY-64, we can’tfind better result, but can find same result compared with the existing one.
참고문헌 (13)
- Eli Biham, "Differential cryptanalysis of DES-like cryptosystems", Journal of Cryptology, 4(1), pp.3~72 (1991), Springer Nature[DOI]
- Mouha, Nicky, "Differential and linear cryptanalysis using mixed-integer linear programming", International Conference on Information Security and Cryptology (2011)
- Sun, Siwei, "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 (2014), Springer
- Fu, Kai, "Milp-based automatic search algorithms for differential and linear trails for speck", International Conference on Fast Software Encryption (2016)
- Sasaki, Yu, "New impossible differential search tool from design and cryptanalysis aspects", Annual International Conference on the Theory and Applications of Cryptographic Techniques (2017)
- Xiang, Zejun, "Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers", International Conference on the Theory and Application of Cryptology and Information Security (2016)
- Banik, Subhadeep, "GIFT: a small PRESENT", International Conference on Cryptographic Hardware and Embedded Systems (2017)
- Sun, Siwei, "Analysis of AES, SKINNY, and others with constraint programming", IACR Transactions on Symmetric Cryptology (2017)
- Sun, Ling, "Automatic Search of Bit-Based Division Property for ARX Ciphers and Word-Based Division Property", International Conference on the Theory and Application of Cryptology and Information Security (2017)
- Beierle, Christof, "The SKINNY family of block ciphers and its low-latency variant MANTIS", Annual-Cryptology Conference (2016), Springer
- 이호창, "MILP를 이용한 ARX 기반 블록 암호의 불능 차분 특성 탐색", 정보보호학회논문지, 27(3), pp.427~437 (2017), 한국정보보호학회[DOI]
- "Fundamental digital electronics, Unit 17 Espresso minimization algorithm"[URL]
- Abdelkhalek, Ahmed, "MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics", IACR Transactions on Symmetric Cryptology, pp.99~129 (2017)