Meet-in-the-middle attacks and structural analysis of round-reduced PRINCE. (English) Zbl 1457.94119

Summary: NXP Semiconductors and its academic partners challenged the cryptographic community with finding practical attacks on the block cipher they designed, PRINCE. Instead of trying to attack as many rounds as possible using attacks which are usually impractical despite being faster than brute force, the challenge invites cryptographers to find practical attacks and encourages them to actually implement them. In this paper, we present new attacks on round-reduced PRINCE including the ones which won the challenge in the 4-, 6- and 8-round categories – the highest for which winners were identified. Our first attacks rely on a meet-in-the-middle approach and break up to ten rounds of the cipher. We also describe heuristic methods we used to find practical SAT-based and differential attacks. Finally, we also present an analysis of the cycle structure of the internal rounds of PRINCE leading both to a low complexity distinguisher for 4-round PRINCE-core and an alternative representation of the cipher valid in particular contexts and which highlights, in these cases, a poor diffusion.


94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
68P25 Data encryption (aspects in computer science)
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory


Full Text: DOI


[1] Biham, E.; Shamir, A., Differential cryptanalysis of DES-like cryptosystems, J. CRYPTOLOGY, 4, 1, 3-72 (1991) · Zbl 0729.68017
[2] M. Matsui, Linear cryptoanalysis method for DES cipher. in Advances in Cryptology—EUROCRYPT 93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, (Proceedings, 1993), pp. 386-397 · Zbl 0951.94519
[3] H. Demirci, A.A. Selçuk, A meet-in-the-middle attack on 8-round AES. in Fast Software Encryption, (Springer, 2008), pp. 116-126 · Zbl 1154.68391
[4] N. Semiconductors, The PRINCE challenge (2014). https://www.emsec.rub.de/research/research_startseite/prince-challenge/
[5] J. Borghoff, A. Canteaut, T. Güneysu, E.B. Kavun, M. Knezevic, L.R. Knudsen, G. Leander, V. Nikov, C. Paar, C. Rechberger, et al, PRINCE—a low-latency block cipher for pervasive computing applications. in Advances in Cryptology-ASIACRYPT 2012. (Springer, 2012), pp. 208-225 · Zbl 1292.94035
[6] A. Biryukov, L. Perrin, State of the art in lightweight cryptography. http://cryptolux.org/index.php/Lightweight_Cryptography
[7] H. Soleimany, C. Blondeau, X. Yu, W. Wu, K. Nyberg, H. Zhang, L. Zhang, Y. Wang, Reflection cryptanalysis of PRINCE-like ciphers. in S. Moriai, ed., Fast Software Encryption - 20th International Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised Selected Papers. Vol. 8424 of Lecture Notes in Computer Science (Springer, 2013), pp. 71-91. 10.1007/978-3-662-43933-3_5 · Zbl 1321.94090
[8] J. Jean, I. Nikolić, T. Peyrin, L. Wang, S. Wu, Security analysis of prince. in Fast Software Encryption: 20th International Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised Selected Papers. Vol. 8424., (Springer, 2014), 92
[9] L. Li, K. Jia, X. Wang, Improved meet-in-the-middle attacks on aes-192 and prince. Cryptology ePrint Archive, Report 2013/573 (2013). http://eprint.iacr.org/
[10] A. Canteaut, T. Fuhr, H. Gilbert, M. Naya-Plasencia, J.R. Reinhard, Multiple differential cryptanalysis of round-reduced PRINCE (full version). Cryptology ePrint Archive, Report 2014/089 (2014). http://eprint.iacr.org/ · Zbl 1382.94079
[11] Morawiecki, P., Practical attacks on the round-reduced PRINCE, IET Inf. Secur., 11, 3, 146-151 (2017)
[12] C. Rechberger, Update on the 10000 euro PRINCE cipher-breaking challenge: Results of round-1 (2014). http://crypto.2014.rump.cr.yp.to/d037206eda8f9278cef1ea26cd62e51f.pdf
[13] O. Dunkelman, N. Keller, A. Shamir, Improved single-key attacks on 8-round AES-192 and AES-256. in Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings. pp. 158-176 (2010) · Zbl 1253.94045
[14] P. Derbez, P. Fouque, Exhausting Demirci-Selçuk meet-in-the-middle attacks against reduced-round AES. in Fast Software Encryption - 20th International Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised Selected Papers. pp. 541-560 (2013) · Zbl 1321.94053
[15] P. Derbez, P.A. Fouque, J. Jean, Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting. in T. Johansson, P.Q. Nguyen, eds., EUROCRYPT. Vol. 7881 of Lecture Notes in Computer Science., (Springer, 2013), pp. 371-387 · Zbl 1306.94044
[16] F. Abed, E. List, S. Lucks, On the security of the core of prince against biclique and differential cryptanalysis. Cryptology ePrint Archive, Report 2012/712 (2012). http://eprint.iacr.org/
[17] A. Biryukov, A. Shamir, Structural cryptanalysis of SASAS, in B. Pfitzmann, ed., Advances in Cryptology—EUROCRYPT 2001. Vol. 2045 of Lecture Notes in Computer Science. (Springer, Berlin, Heidelberg, 2001), pp. 395-405 · Zbl 0981.94015
[18] I. Mironov, L. Zhang, Applications of sat solvers to cryptanalysis of hash functions. In Biere, A., Gomes, C., eds.: Theory and Applications of Satisfiability Testing—SAT 2006. Volume 4121 of Lecture Notes in Computer Science. (Springer, Berlin, Heidelberg, 2006), pp. 102-115 · Zbl 1187.94028
[19] N. Eén, N. Sörensson, An extensible SAT-solver. in Theory and applications of satisfiability testing, (Springer, 2004), pp. 502-518 · Zbl 1204.68191
[20] A. Biryukov, Analysis of involutional ciphers: Khazad and Anubis. in Fast Software Encryption, (Springer, 2003), pp. 45-53 · Zbl 1254.94026
[21] J.H. Moore, G.J. Simmons, Cycle structure of the DES with weak and semi-weak keys. in Advances in Cryptology-CRYPTO’86, (Springer, 1987), pp. 9-32 · Zbl 0634.94013
[22] O. Dunkelman, N. Keller, A. Shamir, Minimalism in cryptography: The Even-Mansour scheme revisited. in Advances in Cryptology—EUROCRYPT 2012. (Springer, 2012), pp. 336-354 · Zbl 1297.94065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.