×

Combined differential and linear cryptanalysis of reduced-round PRINTcipher. (English) Zbl 1292.94089

Miri, Ali (ed.) et al., Selected areas in cryptography. 18th international workshop, SAC 2011, Toronto, ON, Canada, August 11–12, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28495-3/pbk). Lecture Notes in Computer Science 7118, 169-184 (2012).
Summary: In this paper we analyze the security of PRINTcipher using a technique that combines differential and linear cryptanalysis. This technique is different from differential-linear cryptanalysis. We use linear approximations to increase the probability of differential characteristics. We show that specific choices of some of the key bits give rise to a certain differential characteristic probability, which is far higher than the best characteristic probability claimed by the designers. We give the underlying mechanism of this probability increase. We have developed attacks on 29 and 31 rounds of PRINTcipher-48 for 4.54% and 0.036% of the keys, respectively. Moreover, we have implemented the proposed attack algorithm on 20 rounds of the cipher.
For the entire collection see [Zbl 1234.94005].

MSC:

94A60 Cryptography
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. LNCS, vol. 6733, pp. 1–17. Springer, Heidelberg (2011) · Zbl 1282.94029 · doi:10.1007/978-3-642-21702-9_1
[2] Aumasson, J.-P., Henzen, L., Meier, W., Naya-Plasencia, M.: QUARK: A lightweight hash. In: Mangard and Standaert [24], pp. 1–15 (2010) · Zbl 1297.94043 · doi:10.1007/978-3-642-15031-9_1
[3] Badel, S., Dagtekin, N., Nakahara, J., Ouafi, K., Reffé, N., Sepehrdad, P., Susil, P., Vaudenay, S.: ARMADILLO: A Multi-Purpose Cryptographic Primitive Dedicated to Hardware. In: Mangard and Standaert [24], pp. 398–412 (2010) · Zbl 1227.94027 · doi:10.1007/978-3-642-15031-9_27
[4] Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of Skipjack Reduced to 31 Rounds using Impossible Differentials. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 12–23. Springer, Heidelberg (1999) · Zbl 0927.94013 · doi:10.1007/3-540-48910-X_2
[5] Biham, E., Dunkelman, O., Keller, N.: Enhancing Differential-Linear Cryptanalysis. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 254–266. Springer, Heidelberg (2002) · Zbl 1065.94538 · doi:10.1007/3-540-36178-2_16
[6] Biham, E., Dunkelman, O., Keller, N.: Differential-Linear Cryptanalysis of Serpent. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 9–21. Springer, Heidelberg (2003) · Zbl 1254.94024 · doi:10.1007/978-3-540-39887-5_2
[7] Biham, E., Shamir, A.: Differential Cryptanalysis of DES-Like Cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991) · Zbl 0787.94014 · doi:10.1007/3-540-38424-3_1
[8] 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: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007) · Zbl 1142.94334 · doi:10.1007/978-3-540-74735-2_31
[9] Bulygin, S.: Algebraic Cryptanalysis of the Round-Reduced and Side Channel Analysis of the Full PRINTcipher-48. Cryptology ePrint Archive, Report 2011/287 (2011), http://eprint.iacr.org/ · Zbl 1307.94044
[10] De Cannière, C.: trivium: A Stream Cipher Construction Inspired by Block Cipher Design Principles. In: Katsikas, S.K., López, J., Backes, M., Gritzalis, S., Preneel, B. (eds.) ISC 2006. LNCS, vol. 4176, pp. 171–186. Springer, Heidelberg (2006) · Zbl 1156.94345 · doi:10.1007/11836810_13
[11] De Cannière, C., Dunkelman, O., Knežević, M.: KATAN and KTANTAN – A Family of Small and Efficient Hardware-Oriented Block Ciphers. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 272–288. Springer, Heidelberg (2009) · Zbl 1290.94060 · doi:10.1007/978-3-642-04138-9_20
[12] Cheng, H., Heys, H.M., Wang, C.: PUFFIN: A Novel Compact Block Cipher Targeted to Embedded Digital Systems. In: Fanucci, L. (ed.) DSD, pp. 383–390. IEEE (2008) · doi:10.1109/DSD.2008.34
[13] Daemen, J., Govaerts, R., Vandewalle, J.: Weak Keys for IDEA. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 224–231. Springer, Heidelberg (1994) · Zbl 0877.94031 · doi:10.1007/3-540-48329-2_20
[14] Dunkelman, O., Indesteege, S., Keller, N.: A Differential-Linear Attack on 12-Round Serpent. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 308–321. Springer, Heidelberg (2008) · Zbl 1203.94097 · doi:10.1007/978-3-540-89754-5_24
[15] Ågren, M., Johansson, T.: Linear Cryptanalysis of PRINTcipher – Trails and Samples Everywhere. Cryptology ePrint Archive, Report 2011/423 (2011), http://eprint.iacr.org/ · Zbl 1291.94036
[16] Hawkes, P.: Differential-Linear Weak Key Classes of IDEA. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 112–126. Springer, Heidelberg (1998) · Zbl 0919.94022 · doi:10.1007/BFb0054121
[17] Hong, D., Sung, J., Hong, S., Lim, J., Lee, S., Koo, B., Lee, C., Chang, D., Lee, J., Jeong, K., Kim, H., Kim, J., Chee, S.: HIGHT: A New Block Cipher Suitable for Low-Resource Device. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 46–59. Springer, Heidelberg (2006) · Zbl 1307.94058 · doi:10.1007/11894063_4
[18] Izadi, M., Sadeghiyan, B., Sadeghian, S.S., Khanooki, H.A.: MIBS: A New Lightweight Block Cipher. In: Garay, J.A., Miyaji, A., Otsuka, A. (eds.) CANS 2009. LNCS, vol. 5888, pp. 334–348. Springer, Heidelberg (2009) · Zbl 05639356 · doi:10.1007/978-3-642-10433-6_22
[19] Knudsen, L.R., Leander, G., Poschmann, A., Robshaw, M.J.B.: PRINTcipher: A Block Cipher for IC-Printing. In: Mangard and Standaert [24], pp. 16–32 · Zbl 1297.94080 · doi:10.1007/978-3-642-15031-9_2
[20] Langford, S.K., Hellman, M.E.: Differential-Linear Cryptanalysis. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 17–25. Springer, Heidelberg (1994) · Zbl 0939.94524 · doi:10.1007/3-540-48658-5_3
[21] Leander, G., Abdelraheem, M.A., AlKhzaimi, H., Zenner, E.: A cryptanalysis of PRINTcipher: The Invariant Subspace Attack. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 206–221. Springer, Heidelberg (2011) · Zbl 1287.94080 · doi:10.1007/978-3-642-22792-9_12
[22] Lim, C.H., Korkishko, T.: mCrypton – A Lightweight Block Cipher for Security of Low-Cost RFID Tags and Sensors. In: Song, J.-S., Kwon, T., Yung, M. (eds.) WISA 2005. LNCS, vol. 3786, pp. 243–258. Springer, Heidelberg (2006) · doi:10.1007/11604938_19
[23] Liu, Z., Gu, D., Zhang, J., Li, W.: Differential-Multiple Linear Cryptanalysis. In: Bao, F., Yung, M., Lin, D., Jing, J. (eds.) Inscrypt 2009. LNCS, vol. 6151, pp. 35–49. Springer, Heidelberg (2010) · Zbl 1281.94039 · doi:10.1007/978-3-642-16342-5_3
[24] Mangard, S., Standaert, F.-X. (eds.): CHES 2010. LNCS, vol. 6225. Springer, Heidelberg (2010) · Zbl 1193.68012
[25] Matsui, M.: Linear Cryptanalysis Method for DES Cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994) · Zbl 0951.94519 · doi:10.1007/3-540-48285-7_33
[26] Ohkuma, K.: Weak Keys of Reduced-Round Present for Linear Cryptanalysis. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 249–265. Springer, Heidelberg (2009) · Zbl 1267.94088 · doi:10.1007/978-3-642-05445-7_16
[27] Ojha, S.K., Kumar, N., Jain, K., Sangeeta, L.: TWIS – A Lightweight Block Cipher. In: Prakash, A., Sen Gupta, I. (eds.) ICISS 2009. LNCS, vol. 5905, pp. 280–291. Springer, Heidelberg (2009) · Zbl 1304.94078 · doi:10.1007/978-3-642-10772-6_21
[28] Standaert, F.-X., Piret, G., Gershenfeld, N., Quisquater, J.-J.: SEA: A Scalable Encryption Algorithm for Small Embedded Applications. In: Domingo-Ferrer, J., Posegga, J., Schreckling, D. (eds.) CARDIS 2006. LNCS, vol. 3928, pp. 222–236. Springer, Heidelberg (2006) · Zbl 1333.94048 · doi:10.1007/11733447_16
[29] Sun, X., Lai, X.: The Key-Dependent Attack on Block Ciphers. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 19–36. Springer, Heidelberg (2009) · Zbl 1267.94098 · doi:10.1007/978-3-642-10366-7_2
[30] Wagner, D.: The Boomerang Attack. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 156–170. Springer, Heidelberg (1999) · Zbl 0942.94022 · doi:10.1007/3-540-48519-8_12
[31] Guo, S.-Z., Zhao, X.-J., Wang, T.: Fault-Propagation Pattern Based Dfa on Spn Structure Block Ciphers using Bitwise Permutation, with Application to Present and PRINTcipher. Cryptology ePrint Archive, Report 2011/086 (2011), http://eprint.iacr.org/
[32] Zhang, W., Zhang, L., Wu, W., Feng, D.: Related-Key Differential-Linear Attacks on Reduced AES-192. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 73–85. Springer, Heidelberg (2007) · Zbl 1153.94444 · doi:10.1007/978-3-540-77026-8_7
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.