logo

SCIENCE CHINA Information Sciences, Volume 60, Issue 5: 052108(2017) https://doi.org/10.1007/s11432-015-5487-3

Cryptanalysis of full PRIDE block cipher

More info
  • ReceivedOct 6, 2015
  • AcceptedDec 18, 2015
  • PublishedSep 13, 2016

Abstract

PRIDE is a lightweight block cipher proposed at CRYPTO 2014 by Albrecht et al., who claimed that the construction of linear layers is efficient and secure. In this paper, we investigate the key schedule and find eight 2-round iterative related-key differential characteristics, which can be used to construct 18-round related-key differentials. A study of the first subkey derivation function reveals that there exist three weak-key classes, as a result of which all the differences of subkeys for each round are identical. For the weak-key classes, we also find eight 2-round iterative related-key differential characteristics. Based on one of the related-key differentials, we launch an attack on the full PRIDE block cipher. The data and time complexity are $2^{39}$ chosen plaintexts and $2^{92}$ encryptions, respectively. Moreover, by using multiple related-key differentials, we improve the cryptanalysis, which then requires $2^{41.6}$ chosen plaintexts and $2^{42.7}$ encryptions, respectively. Finally, we use two 17-round related-key differentials to analyze full PRIDE, which requires $2^{35}$ plaintexts and $2^{54.7}$ encryptions. These are the first results on full PRIDE, and show that the PRIDE block cipher is not secure against related-key differential attack.


Funded by

Foundation of Science and Technology on Information Assurance Laboratory(KJ-13-010)


Acknowledgment

Acknowledgments

This work was supported by Foundation of Science and Technology on Information Assurance Laboratory (Grant No. KJ-13-010).


References

[1] Bogdanov A, Knudsen L R, Leader G, et al. PRESENT: an ultra-lightweight block cipher. In: Proceedings of Cryptographic Hardware and Embedded Systems. Berlin/Heidelberg: Springer-Verlag, 2007. 450--466. Google Scholar

[2] Knudsen L R, Leander G, Poschmann A, et al. PRINTcipher: a block cipher for IC printing. In: Proceedings of Cryptographic Hardware and Embedded Systems. Berlin/Heidelberg: Springer-Verlag, 2010. 16--32. Google Scholar

[3] Guo L, Peyrin T, Poschmann A, et al. The LED block cipher. In: Proceedings of Cryptographic Hardware and Embedded Systems. Berlin/Heidelberg: Springer-Verlag, 2011. 326--341. Google Scholar

[4] Wu W L, Zhang L. LBlock: a lightweight block cipher. In: Proceedings of Applied Cryptography and Network Security. Berlin/Heidelberg: Springer-Verlag, 2011. 327--344. Google Scholar

[5] Borghoff J, Canteaut A, G$\ddot{\rm u}$neysu T, et al. PRINCE--a low-latency block cihper for pervasive computing applications-extended abstract. In: Proceedings of ASIACRYPT. Berlin/Heidelberg: Springer-Verlag, 2012. 208--225. Google Scholar

[6] Beaulieuand R, Shors D, Smith J, et al. Performance of the SIMON and SPECK Family of Lightweight Block Ciphers. Technical Peport, National Security Agency, 2014. Google Scholar

[7] Albrecht M R, Driessen B, Kavun E B, et al. Block ciphers--focus on the linear layer (feat. PRIDE). In: Proceedings of CRYPTO. Berlin/Heidelberg: Springer-Verlag, 2014. 57--76. Google Scholar

[8] Zhao J Y, Wang X Y, Wang M Q, et al. Differential analysis on block cipher PRIDE. Cryptology ePrint Archive, 2014, 2014: 525 Google Scholar

[9] Yang Q Q, Hu L, Sun S W, et al. Improved differential analysis of block cipher PRIDE. In: Proceedings of IPSEC. Berlin/Heidelberg: Springer-Verlag, 2015. 209--219. Google Scholar

[10] Dinur I. Cryptanalytic time-memory-data tradeoffs for FX-constructions with applications to PRINCE and PRIDE. In: Proceedings of EUROCRYPT. Berlin/Heidelberg: Springer-Verlag, 2015. 231--253. Google Scholar

[11] Biham E. New types of cryptanalytic attacks using related keys. J Cryptology, 1994, 7: 229-246 Google Scholar

[12] Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems. J Cryptology, 1991, 4: 3-72 CrossRef Google Scholar

[13] Kelsey J, Schneier B, Wagner D. Key schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES. In: Proceedings of CRYPTO. Berlin/Heidelberg: Springer-Verlag, 1996. 237--251. Google Scholar

[14] Biryukov A, Dunkelman O, Keller N, et al. Key recovery attacks of practical complexity on AES-256 variants with up to 10 rounds. In: Proceedings of EUROCRYPT. Berlin/Heidelberg: Springer-Verlag, 2010. 299--319. Google Scholar

[15] Biryukov A, Khovratovich D. Related-key cryptanalysis of the full AES-192 and AES-256. In: Proceedings of ASIACRYPT. Berlin/Heidelberg: Springer-Verlag, 2009. 1--18. Google Scholar

[16] Dunkelman O, Keller N, Shamir A. A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony. In: Proceedings of CRYPTO. Berlin/Heidelberg: Springer-Verlag, 2010. 393--410. Google Scholar

[17] Huang J L, Lai X J. What is the effective key length for a block cipher: an attack on every practical block cipher. Sci China Inf Sci, 2014, 57: 072110-72 Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号