SAT 솔버를 이용한 ARX 구조 암호의 디퍼렌셜 확률 근사값 계산
Calculating the Approximate Probability of Differentials for ARX-Based Cipher Using SAT Solver
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 SAT 솔버를 이용하여 디퍼렌셜 확률의 근사값을 구하는 방법에 대해서 설명한다. SAT 솔버를 이용해서 이미 알려진 차분특성을 디퍼렌셜로 구성하여 확률을 높일 수 있다. 본 논문에서 제안하는 방법으로 SPECK32와 SPECK48의 디퍼렌셜을 구성하였다. SPECK32는 2^-30.39의 확률을 가지는 10-라운드 디퍼렌셜을 찾아냈고, SPECK48은 2^-46.8의 확률을 가지는 12-라운드 디퍼렌셜을 찾아냈다. 두 특성 모두 가장 길고 높은 확률을 가지는 새로운 디퍼렌셜이다. 본 논문에서 발견한 디퍼렌셜을 이용해서 SPECK32/64의 15 라운드 차분공격, SPECK48/72의 16 라운드 차분공격, SPECK48/96의 17 라운드 차분공격을 하여 이전 공격보다 각각 1 라운드 씩 개선하였다.
Abstract
In this paper, we explain a method of appproximating the differentials probability using a SAT solver. It is possible to increase the probability by constructing the differential characteristic which already known to differentials with a SAT solver. We apply our method to SPECK32 and SPECK48. As a result, we introduced a SPECK32’s 10-round differentials with a probability of 2^-30.39, and SPECK48’s 12-round differentials with probability of 2^-46.8. Both differentials are new and longer round and higher probability than previous ones. Using the differentials presented in this paper, we improved attacks of SPECK32/64 to 15 round, SPECK48/72 to 16 round, SPECK48/96 to 17 round, which attack 1 more rounds of previous works.
참고문헌 (18)
- Ray Beaulieu, "The SIMON and SPECK lightweight block ciphers", Design Automation Conference (DAC), 2015 52nd ACM, IEEE., pp.2015[DOI]
- Deukjo Hong, "LEA: A 128-bit block cipher for fast encryption on common preocessors", WISA 13: 14th, 8267, pp.3~27 (2014)
- Eli Biham, "Differential cryptanalysis of DES-like cryptosystems", CRYPTO'90, pp.2~21 (1991)
- Mitsuru Matsui, "Linear cryptoanalysis method for DES cipher", EUROCRYPT'93, pp.386~397 (1994)
- Alex Biryukov, "Automatic search for differential trails in ARX ciphers", CTRSA 2014, pp.227~250 (2014)
- Alex Biryukov, "Automatic search for related-key differential characteristics in byte-oriented block ciphers: Application to AES, Camellia", EUROCRYPT 2010, pp.322~344 (2010)
- Aleksandar Kircanski, "Analysis of boomerang differential trails via a SATbased constraint solver URSA", ACNS 15: 13th International Conference on Applied Cryptography and Network Security, pp.331~349 (2015)
- Automatic differential analysis of ARX block ciphers with application to SPECK and LEA, Cryptology ePrint Archive, Report 2016, "209", Ling Song, 2016
- Mohamed, "Improved algebraic side-channel attack on AES", Hardware-Oriented Security and Trust (HOST), 2012 IEEE International Symposium on. IEEE, pp.146~151 (2012)
- C. W. Barrett, "Satisability modulo theories. Handbook of satisability, vol. 185", pp.825~885 (2009)
- Helger Lipmaa, "Efficient algorithms for computing differential properties of addition", FSE 2001, pp.336~350 (2002)
- 김서진, "ARX 구조를 가지는 블록 암호에 대한 효율적인 차분 경로 자동 탐색 알고리즘", 정보보호학회논문지, 26(6), pp.1421~1430 (2016), 한국정보보호학회[DOI]
- Alex Biryukov, "Automatic search for the best trails in ARX: Application to block cipher speck", FSE 2016, pp.289~310 (2016)
- Itai Dinur, "Improved differential cryptanalysis of round-reduced Speck", SAC 2014: 21st Annual International Workshop on Selected Areas in Cryptography, pp.147~164 (2014)
- Abed, Farzaneh, "Differential cryptanalysis of round-reduced simon and speck", International Workshop on Fast Software Encryption, pp.525~545 (2014)
- Y. Liu, "Differential cryptanalysis of round-reduced simon and speck", IACR Trans. Symm. Cryptol., 2017(3), pp.24~36 (2017)
- G. D. Witte, "An Automated Tool for Rotational-XOR Cryptanalysis of ARX-based Primitives", 38th Symp. on Info. Theo. in the Benelux, pp.59~66 (2017)