경량 블록 암호 PIPO의 MILP-Aided 디비전 프로퍼티 분석 및 인테그랄 공격

국문 초록 (Abstract)

본 논문에서는 경량 블록 암호 PIPO에 대한 인테그랄 구별자(integral distinguisher)을 탐색한 결과를 통해 8-라운드 PIPO-64/128에 대한 키 복구 공격을 수행한다. ICISC 2020에서 제안된 경량 블록 암호 PIPO는 고차 마스킹 구현을 고려한 설계를 통해 부채널 공격에 대한 저항성을 갖는 효율적인 구현이 가능하다. 동시에 차분 분석, 선형 분석 등의 다양한 분석법을 적용하여 PIPO의 안전성을 보였다. 그러나 인테그랄 공격에 대해, 5-라운드 이상의 인테그랄 구별자가 존재하지 않을 것이라고 제안되었을 뿐 인테그랄 공격에 대한 안전성 분석은 현재까지 수행된 바 없다. 본 논문에서는 MILP 기반 Division Property를 통해 PIPO에 대한 인테그랄 구별자를 탐색하는 방법을 제시하고, 기존의 결과와 달리 6-라운드 인테그랄 구별자가 존재함을 보인다. 뿐만 아니라, PIPO의 라운드 함수 구조를 활용하여 입출력에 대한 선형 변환을 고려하는 인테그랄 구별자 탐색 방법을 통해 총 136개의 6-라운드 인테그랄 구별자를 제시한다. 마지막으로, 획득한 6-라운드 인테그랄 구별자 중 4개를 이용하여 2<SUP>124.5849</SUP>의 시간 복잡도와 2<SUP>93</SUP>의 메모리 복잡도를 가지는 8-라운드 PIPO-64/128 키 복구 공격을 제안한다.

다국어 초록 (Multilingual Abstract)

In this paper, we search integral distinguishers of lightweight block cipher PIPO and propose a key recovery attack on 8-round PIPO-64/128 with the obtained 6-round distinguishers. The lightweight block cipher PIPO proposed in ICISC 2020 is designed to provide the efficient implementation of high-order masking for side-channel attack resistance. In the proposal, various attacks such as differential and linear cryptanalyses were applied to show the sufficient security strength. However, the designers leave integral attack to be conducted and only show that it is unlikely for PIPO to have integral distinguishers longer than 5-round PIPO without further analysis on Division Property. In this paper, we search integral distinguishers of PIPO using a MILP-aided Division Property search method. Our search can show that there exist 6-round integral distinguishers, which is different from what the designers insist. We also consider linear operation on input and output of distinguisher, respectively, and manage to obtain totally 136 6-round integral distinguishers. Finally, we present an 8-round PIPO-64/128 key recovery attack with time complexity 2<SUP>124.5849</SUP> and memory complexity of 2<SUP>93</SUP> with four 6-round integral distinguishers among the entire obtained distinguishers.

목차 (Table of Contents)

• 요약
• ABSTRACT
• Ⅰ. 서론
• Ⅱ. 배경 지식
• Ⅲ. MILP Modeling for PIPO
• Ⅳ. 선형 변환을 고려한 디비전 프로퍼티 분석
• Ⅴ. Integral Distinguisher of PIPO
• Ⅵ. 결론
• References

참고문헌 (Reference)

1 Sun, Siwei, "Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of (related-key) differential and linear characteristics with predefined properties"

2 Daemen, Joan, "The block cipher Square" 149-165, 1997

3 Gilbert, Henri, "Super-Sbox cryptanalysis: Improved attacks for AES-like permutations" 365-383, 2010

4 Je-seong Kim, "Study on Division Property Analysis exploiting S-Box Construction" 488-491, 2021

5 Todo, Yosuke, "Structural evaluation by generalized integral property" 287-314, 2015

6 Kim, Hangi, "PIPO: A Lightweight Block Cipher with Efficient Higher-Order Masking Software Implementations" 99-122, 2020

7 Sasaki, Yu, "New impossible differential search tool from design and cryptanalysis aspects" 185-215, 2017

8 Tingting, Cui, "New automatic search tool for impossible differentials and zero-correlation linear approximations"

9 Derbez, Patrick, "Linearly equivalent S-boxes and the Division Property"

10 Knudsen, Lars, "Integral cryptanalysis" 112-127, 2002

11 Ferguson, Niels, "Improved cryptanalysis of Rijndael" 213-230, 2000

12 Boura, Christina, "Higher-order differential properties of Keccak and Luffa" 252-269, 2011

13 Mouha, Nicky, "Differential and linear cryptanalysis using mixed-integer linear programming" 57-76, 2011

14 Todo, Yosuke, "Bit-based division property and application to simon family" 357-377, 2016

15 Sun, Siwei, "Automatic security evaluation and (related-key)differential characteristic search:application to SIMON, PRESENT, LBlock, DES (L) and other bit-oriented block ciphers" 158-178, 2014

16 Xiang, Zejun, "Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers" 648-678, 2016

17 Kim, Hangi, "A New Method for Designing Lightweight S-boxes with High Differential and Linear Branch Numbers, and Its Application"