×

Full analysis of PRINTcipher with respect to invariant subspace attack: efficient key recovery and countermeasures. (English) Zbl 1308.94062

Summary: In this paper we investigate the invariant property of PRINTcipher initially discovered by G. Leander et al. in their CRYPTO 2011 paper [Lect. Notes Comput. Sci. 6841, 206–221 (2011; Zbl 1287.94080)]. We provide a complete study of the attack and show that there exist 64 families of weak keys for PRINTcipher-48 and as many as 115,669 for PRINTcipher-96. Moreover, we show that searching the weak key space may be substantially sped up by splitting the search process into two consecutive steps. We show that for many classes of weak keys, key recovery can be done with very small time complexity in the chosen/known plaintext scenario. In fact, at least \(2^{45}\) weak keys can be recovered in less than 10 s per key on a single PC. Still, effective countermeasures exist against the attack. On the methodological level, the method of finding all weak key families has value on its own. It is based on mixed integer linear programming and can be adapted to solving other interesting problems on similar ciphers.

MSC:

94A60 Cryptography
90C10 Integer programming

Citations:

Zbl 1287.94080
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdelraheem M.A., Leander G., Zenner E.: Differential cryptanalysis of round-reduced PRINTcipher: Computing roots of permutations. In: Joux A. (ed.) FSE 2011. Lecture Notes in Computer Science, vol. 6733, pp. 1-17. Springer, Berlin (2011). · Zbl 1282.94029
[2] Agren, M., Johansson, T.: Linear cryptanalysis of PRINTcipher—trails and samples everywhere. In: Bernstein D.J., Chatterjee S. (eds.) INDOCRYPT 2011. Lecture Notes in Computer Science, vol. 7107, pp. 114-133. Springer, Berlin (2011). · Zbl 1291.94036
[3] Bard G.V.: Algebraic cryptanalysis, Springer, Dordrecht (2009). · Zbl 1183.94019
[4] Bogdanov A.: On unbalanced Feistel networks with contracting MDS diffusion. Des. Codes Cryptogr. 59(1-3), 35-58 (2011). · Zbl 1213.94085
[5] Bogdanov A., Knudsen L.R., Leander G., Paar C., Poschmann A., Robshaw M.J.B., Seurin Y., Vikkelsoe C.: PRESENT—An ultra-lightweight block cipher. In: Pailier P., Verbauwhede I. (eds.) CHES 2007. Lecture Notes in Computer Science, vol. 4727, pp. 450-466. Springer, Berlin (2007). · Zbl 1142.94334
[6] Borghoff J., Knudsen L.R., Stolpe M.: Bivium as a mixed-integer linear programming problem. In: IMA International Conference on Cryptography and Coding. Lecture Notes in Computer Science, vol. 5921, pp. 133-152. Springer, Berlin (2009). · Zbl 1234.94031
[7] Bogdanov A., Knezević M., Leander G., Toz D., Varici K., Verbauwhede I.: SPONGENT: A lightweight hash function. In: Preneel B., Takagi T. (eds.) CHES 2011. Lecture Notes in Computer Science, vol. 6917, pp. 312-325. Springer, Berlin (2011). · Zbl 1365.94406
[8] Borghoff J., Canteaut A., Gneysu T., Kavun E.B., Knezevic M., Knudsen L.R., Leander G., Nikov V., Paar C., Rechberger C., Rombouts P., Thomsen S.S., Yalcin T.: PRINCE—A low-latency block cipher for pervasive computing applications: Extended Abstract. In: Wang X., Sako K. (eds.) ASIACRYPT 2012. Lecture Notes in Computer Science, vol. 7658, pp. 208-225. Springer, Berlin (2012). · Zbl 1292.94035
[9] Bulygin S., Buchmann J.: Algebraic cryptanalysis of the round-reduced and side channel analysis of the full PRINTcipher-48. In: Lin D., Tsudik G., Wang X. (eds.) CANS 2011. Lecture Notes in Computer Science, vol. 7092, pp. 54-75. Springer, Berlin (2011). · Zbl 1307.94044
[10] Bulygin S., Walter M.: Study of the invariant coset attack on PRINTcipher: More weak keys with practical key recovery. http://eprint.iacr.org/2012/085 (2012). Accessed 15 June 2013.
[11] Bulygin S., Walter M., Buchmann J.: Many weak keys for PRINTcipher: Fast key recovery and countermeasures. In: Dawson E. (ed.) CT-RSA 2013. Lecture Notes in Computer Science, vol. 7779, pp. 189-206. Springer, Berlin (2013). · Zbl 1301.94110
[12] Cid C., Murphy S., Robshaw M.: Algebraic Aspects of the Advanced Encryption Standard. Springer, New York (2006). · Zbl 1130.68047
[13] de Canniére C., Dunkelman O., Knezević M.: KATAN and KTANTAN : A family of small and efficient hardware-oriented block ciphers. In: Clavier C., Gaj K. (eds.) CHES 2009. Lecture Notes in Computer Science, vol. 5747, pp. 272-288. Springer, Berlin (2009). · Zbl 1290.94060
[14] Guo J., Peyrin T., Poschmann A., Robshaw M.: The LED block cipher. In: Preneel B., Takagi T. (eds.) CHES 2011. Lecture Notes in Computer Science, vol. 6917, pp. 326-341. Springer, Berlin (2011). · Zbl 1291.94092
[15] Karakoc F., Demirci H., Harmanci A.E.: Combined differential and linear cryptanalysis of reduced-round PRINTcipher. In: Miri A., Vaudenay S. (eds.) SAC 2011. Lecture Notes in Computer Science, vol. 7118, pp. 169-184. Springer, Berlin (2012). · Zbl 1292.94089
[16] Knudsen L., Leander G., Poschmann A., Robshaw M.J.B.: PRINTcipher: A block cipher for IC-printing. In: Mangard S., Standaert F.-X. (eds.) CHES 2010. Lecture Notes in Computer Science, vol. 6225, pp. 16-32. Springer, Berlin (2010). · Zbl 1297.94080
[17] Leander G., Abdelraheem M.A., AlKhzaimi H., Zenner E.: A cryptanalysis of PRINTcipher: The invariant subspace attack. In: Rogaway P. (ed.) CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841, pp. 206-221. Springer, Berlin (2011). · Zbl 1287.94080
[18] Mouha N., Wang Q., Gu D., Preneel B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Wu C.-K., Yung M., Lin D. (eds.) Inscypt 2011. Lecture Notes in Computer Science, vol. 7537, pp. 57-76. Springer, Berlin (2011). · Zbl 1292.94118
[19] Stein S.W., et al.: SAGE mathematics software. The Sage Development Team. http://www.sagemath.org (2008). Accessed 15 June 2013.
[20] Walter M., Bulygin S., Buchmann J.: Optimizing guessing strategies for algebraic cryptanalysis with applications to EPCBC. In: Kutylowski M.,Yung M. (eds.) Lecture Notes in Computer Science. Springer, Berlin (2012). · Zbl 1311.94100
[21] Wu W., Zhang L.: LBlock: A lightweight block cipher. In: Lopez J., Tsudik G. (eds.) ACNS 2011. Lecture Notes in Computer Science, vol. 6715, pp. 327-344. Springer, Berlin (2011). · Zbl 1250.94047
[22] Yap H., Khoo K., Poschmann A., Henricksen M.: EPCBC—A block cipher suitable for electronic product code encryption. In: Lin D., Tsudik G., Wang X. (eds.) Lecture Notes in Computer Science, vol. 7092, pp. 76-97 Springer, Berlin (2011). · Zbl 1307.94111
[23] Zhao X., Wang T., Guo S.: Fault propagate pattern based DFA on SPN structure block ciphers using bitwise permutation, with application to PRESENT and PRINTcipher. http://eprint.iacr.org/2011/086.pdf (2011). Accessed 15 June 2013.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.