Truncated differential based known-key attacks on round-reduced SIMON. (English) Zbl 1398.94121
Summary: At Crypto 2015, C. Blondeau et al. [Lect. Notes Comput. Sci. 9215, 455–474 (2015; Zbl 1375.94104)] proposed a truncated-differential-based known-key attack on full PRESENT, a nibble oriented lightweight block cipher with an SPN structure. The truncated difference they used is derived from the existing multidimensional linear characteristics. An innovative technique of their work is the design of a MITM layer added before the characteristic that covers extra rounds with a complexity lower than that of a generic construction. We notice that there are good linear hulls for bit-oriented block cipher SIMON corresponding to highly qualified truncated differential characteristics. Based on these characteristics, we propose known-key distinguishers on round-reduced SIMON block cipher family, which is bit oriented and has a Feistel structure. Similar to the MITM layer, we design a specific start-from-the-middle method for pre-adding extra rounds with complexities lower than generic bounds. With these techniques, we launch basic known-key attacks on round-reduced SIMON. We also involve some key guessing technique and further extend the basic attacks to more rounds. Our known-key attacks can reach as many as 29/32/38/48/63-rounds of SIMON32/48/64/96/128, which comes quite close to the full number of rounds. To the best of our knowledge, these are the first known-key results on the block cipher SIMON.
MSC:
| 94A60 | Cryptography |
Citations:
Zbl 1375.94104Software:
PRESENT; mCrypton; KLEIN; TWINE; HIGHT; KATAN; SIMON; KTANTAN; LED; PRINCE; Piccolo; SIMECKReferences:
| [1] | Abdelraheem M.A., Alizadeh J., Alkhzaimi H.A., Aref M.R., Bagheri N., Gauravaram P., Lauridsen M.M.: Improved linear cryptanalysis of reduced-round SIMON. IACR Cryptology ePrint Archive 2014, 681 (2014). · Zbl 1377.94024 |
| [2] | Abdelraheem M.A., Alizadeh J., AlKhzaimi H.A., Aref M.R., Bagheri N., Gauravaram P.: Improved linear cryptanalysis of reduced-round SIMON-32 and SIMON-48. In: Biryukov, A., Goyal, V. (eds.) Progress in Cryptology—INDOCRYPT 2015. Proceedings of the 16th International Conference on Cryptology in India, Bangalore, India, 6-9 Dec 2015. Lecture Notes in Computer Science, vol. 9462, pp. 153-179. Springer, Berlin (2015). · Zbl 1377.94024 |
| [3] | Abed F., List E., Lucks S., Wenzel J.: Differential cryptanalysis of round-reduced Simon and Speck. In: Cid, C., Rechberger, C., (eds.) Fast Software Encryption—21st International Workshop, FSE 2014, London, UK, 3-5 Mar 2014. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8540, pp. 525-545. Springer, Berlin (2015). · Zbl 1382.94037 |
| [4] | Ashur T.: Improved linear trails for the block cipher Simon. IACR Cryptology ePrint Archive 2015, 285 (2015). |
| [5] | Beaulieu R., Shors D., Smith J., Treatman-Clark S., Weeks B., Wingers L.: The SIMON and SPECK families of lightweight block ciphers. IACR Cryptology ePrint Archive 2013, 404 (2013). · Zbl 1382.94059 |
| [6] | Beaulieu R., Shors D., Smith J., Treatman-Clark S., Weeks B., Wingers L.: The SIMON and SPECK lightweight block ciphers. In: Proceedings of the 52nd Annual Design Automation Conference, San Francisco, CA, USA, 7-11 June 2015, pp. 175:1-175:6. ACM, New York (2015). · Zbl 1382.94059 |
| [7] | Biryukov A., Roy A., Velichkov V.: Differential analysis of block ciphers SIMON and SPECK. In: Cid, C., Rechberger, C., (eds.) Fast Software Encryption. 21st International Workshop, FSE 2014, London, UK, 3-5 Mar 2014. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8540, pp. 546-570. Springer, Berlin (2015). · Zbl 1382.94067 |
| [8] | Black J., Rogaway P., Shrimpton T.: Black-box analysis of the block-cipher-based hash-function constructions from PGV. In: Yung, M. (ed.) Advances in Cryptology—CRYPTO 2002. Proceedings of 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, 18-22 Aug 2002. Lecture Notes in Computer Science, vol. 2442, pp. 320-335. Springer, Berlin (2002). · Zbl 1026.94522 |
| [9] | Blondeau C., Nyberg K.: Links between truncated differential and multidimensional linear properties of block ciphers and underlying attack complexities. In: Nguyen, P.Q., Oswald, E., (eds.) Advances in Cryptology—EUROCRYPT 2014. Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, 11-15 May 2014. Lecture Notes in Computer Science, vol. 8441, pp. 165-182. Springer, Berlin (2014). · Zbl 1332.94060 |
| [10] | Blondeau C., Peyrin T., Wang L.: Known-key distinguisher on full PRESENT. In: Gennaro, R., Robshaw, M. (eds.) Proceedings of the 35th Annual Cryptology Conference on Advances in Cryptology—CRYPTO 2015, Santa Barbara, CA, USA, 16-20 Aug 2015. Part I. Lecture Notes in Computer Science, vol. 9215, pp. 455-474. Springer, Berlin (2015). · Zbl 1375.94104 |
| [11] | 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.) Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems—CHES 2007, Vienna, Austria, 10-13 Sept 2007. Lecture Notes in Computer Science, vol. 4727, pp. 450-466. Springer, Berlin (2007). · Zbl 1142.94334 |
| [12] | Borghoff J., Canteaut A., Güneysu T., Kavun E.B., Knezevic M., Knudsen L.R., Leander G., Nikov V., Paar C., Rechberger C., Rombouts P., Thomsen S.S., Yalçin T.: PRINCE—a low-latency block cipher for pervasive computing applications—extended abstract. In: Wang, X., Sako, K. (eds.) Advances in Cryptology—ASIACRYPT 2012. Proceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, 2-6 Dec 2012. Lecture Notes in Computer Science, vol. 7658, pp. 208-225. Springer, Berlin (2012). · Zbl 1292.94035 |
| [13] | Cannière C.D., Dunkelman O., Knezevic M.: KATAN and KTANTAN—a family of small and efficient hardware-oriented block ciphers. In: Clavier, C., Gaj, K. (eds.) Proceedings of the 11th International Workshop on Cryptographic Hardware and Embedded Systems—CHES 2009, Lausanne, Switzerland, 6-9 Sept 2009. Lecture Notes in Computer Science, vol. 5747, pp. 272-288. Springer, Berlin (2009). · Zbl 1290.94060 |
| [14] | Chen H., Wang X.: Improved linear hull attack on round-reduced Simon with dynamic key-guessing techniques. IACR Cryptology ePrint Archive 2015, 666 (2015). |
| [15] | Dinur I., Güneysu T., Paar C., Shamir A., Zimmermann R.: An experimentally verified attack on full Grain-128 using dedicated reconfigurable hardware. In: Lee, D.H., Wang, X., (eds.) Advances in Cryptology—ASIACRYPT 2011. Proceedings of the 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, 4-8 Dec 2011. Lecture Notes in Computer Science, vol. 7073, pp. 327-343. Springer, Berlin (2011). · Zbl 1227.94042 |
| [16] | Dinur I., Liu Y., Meier W., Wang Q.: Optimized interpolation attacks on LowMC. In: Iwata, T., Cheon, J.H., (eds.) Advances in Cryptology—ASIACRYPT 2015. Proceedings of the 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, 29 November-3 December 2015. Part II. Lecture Notes in Computer Science, vol. 9453, pp. 535-560. Springer, Berlin (2015). · Zbl 1382.94092 |
| [17] | Dinur I., Shamir A.: Breaking Grain-128 with dynamic cube attacks. In: Joux, A. (ed.) 18th International Workshopon ast Software Encryption, FSE 2011, Lyngby, Denmark, 13-16 Feb 2011, Revised Selected Papers. Lecture Notes in Computer Science, vol. 6733, pp. 167-187. Springer, Berlin (2011). · Zbl 1282.94042 |
| [18] | Dong L., Wang Y., Wu W., Zou J.: Known-key distinguishers on 15-round 4-branch type-2 generalised Feistel networks with single substitution-permutation functions and near-collision attacks on its hashing modes. IET Inf. Secur. 9(5), 277-283 (2015). |
| [19] | Dong L., Wu W., Wu S., Zou J.: Known-key distinguishers on type-1 Feistel scheme and near-collision attacks on its hashing modes. Front. Comput. Sci. 8(3), 513-525 (2014). · Zbl 1368.94095 |
| [20] | Fouque P., Jean J., Peyrin T.: Structural evaluation of AES and chosen-key distinguisher of 9-round AES-128. In: Canetti, R., Garay, J.A. (eds.) Proceedings of the 33rd Annual Cryptology Conference on Advances in Cryptology—CRYPTO 2013, Santa Barbara, CA, USA, 18-22 Aug 2013. Part I. Lecture Notes in Computer Science vol. 8042, pp. 183-203. Springer, Berlin (2013). · Zbl 1310.94144 |
| [21] | Gilbert H.: A simplified representation of AES. In: Sarkar, P., Iwata, T., (eds.): Advances in Cryptology—ASIACRYPT 2014. Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., 7-11 Dec 2014. Part I. Lecture Notes in Computer Science, vol. 8873, pp. 200-222. Springer, Berlin (2014). · Zbl 1301.94003 |
| [22] | Gong Z., Nikova S., Law Y.W.: KLEIN: a new family of lightweight block ciphers. In: Juels, A., Paar, C., (eds.) RFID. Security and Privacy—7th International Workshop, RFIDSec 2011, Amherst, USA, 26-28 June 2011, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7055, pp. 1-18. Springer, Berlin (2011). · Zbl 1436.94068 |
| [23] | Guo J., Peyrin T., Poschmann A., Robshaw M.J.B.: The LED block cipher. In: Preneel, B., Takagi, T., (eds.) Proceedings of the 13th International Workshop on Cryptographic Hardware and Embedded Systems—CHES 2011, Nara, Japan, 28 Sept-1 Oct 2011. Lecture Notes in Computer Science, vol. 6917, pp. 326-341. Springer, Berlin (2011). · Zbl 1291.94092 |
| [24] | 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.) Proceedings of the 8th International Workshop on Cryptographic Hardware and Embedded Systems—CHES 2006, Yokohama, Japan, 10-13 Oct 2006. Lecture Notes in Computer Science, vol. 4249, pp. 46-59. Springer, Berlin (2006). · Zbl 1307.94058 |
| [25] | Knudsen L.R., Rijmen V.: Known-key distinguishers for some block ciphers. In: Kurosawa, K. (ed.) Advances in Cryptology—ASIACRYPT 2007. Proceedings of the 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, 2-6 Dec 2007. Lecture Notes in Computer Science, vol. 4833, pp. 315-324. Springer, Berlin (2007). · Zbl 1153.94403 |
| [26] | Kölbl S., Leander G., Tiessen T.: Observations on the SIMON block cipher family. In: Gennaro, R., Robshaw, M., (eds.) Proceedings of the 35th Annual Cryptology Conference on Advances in Cryptology—CRYPTO 2015, Santa Barbara, CA, USA, 16-20 Aug 2015. Part I. Lecture Notes in Computer Science, vol. 9215, pp. 161-185. Springer, Berlin (2015). · Zbl 1369.94546 |
| [27] | Koyama T., Sasaki Y., Kunihiro N.: Multi-differential cryptanalysis on reduced DM-PRESENT-80: collisions and other differential properties. In: Kwon, T., Lee, M., Kwon, D. (eds.) 15th International Conference on Information Security and Cryptology—ICISC 2012, Seoul, Korea, 28-30 Nov 2012, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7839, pp. 352-367. Springer, Berlin (2012). · Zbl 1342.94078 |
| [28] | Lauridsen M.M., Rechberger C.: Linear distinguishers in the key-less setting: Application to PRESENT. In: Leander, G. (ed.) Fast Software Encryption—22nd International Workshop, FSE 2015, Istanbul, Turkey, 8-11 Mar 2015, Revised Selected Papers. Lecture Notes in Computer Science, vol. 9054, pp. 217-240. Springer, Berlin (2015). · Zbl 1367.94323 |
| [29] | Lim C.H., Korkishko T.: mCrypton—a lightweight block cipher for security of low-cost RFID tags and sensors. In: Song, J., Kwon, T., Yung, M. (eds.) Information Security Applications: 6th International Workshop, WISA 2005, Jeju Island, Korea, 22-24 Aug 2005, Revised Selected Papers. Lecture Notes in Computer Science, vol. 3786, pp. 243-258. Springer, Berlin (2005). |
| [30] | Mennink B., Preneel B.: On the impact of known-key attacks on hash functions. In: Iwata, T., Cheon, J.H., (eds.): Advances in Cryptology—ASIACRYPT 2015. Proceedings of the 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29-December 3 2015. Part II. Lecture Notes in Computer Science, vol. 9453, pp. 59-84. Springer, Berlin (2015). · Zbl 1375.94149 |
| [31] | Minier M., Phan R.C., Pousse B.: Distinguishers for ciphers and known key attack against Rijndael with large blocks. In: Preneel, B. (ed.) Progress in Cryptology—AFRICACRYPT 2009, Proceedings of the Second International Conference on Cryptology in Africa, Gammarth, Tunisia, 21-25 June 2009. Lecture Notes in Computer Science, vol. 5580, pp. 60-76. Springer, Berlin (2009). · Zbl 1246.94035 |
| [32] | Nikolic I., Pieprzyk J., Sokolowski P., Steinfeld R.: Known and chosen key differential distinguishers for block ciphers. In: Rhee, K.H., Nyang, D., (eds.) 13th International Conference on Information Security and Cryptology—ICISC 2010, Seoul, Korea, 1-3 Dec 2010, Revised Selected Papers. Lecture Notes in Computer Science vol. 6829, pp. 29-48. Springer, Berlin (2010). · Zbl 1297.94094 |
| [33] | Preneel B., Govaerts R., Vandewalle J.: Hash functions based on block ciphers: a synthetic approach. In: Stinson, D.R. (ed.) Advances in Cryptology—CRYPTO ’93. Proceedings of the 13th Annual International Cryptology Conference, Santa Barbara, California, USA, 22-26 Aug 1993. Lecture Notes in Computer Science, vol. 773, pp. 368-378. Springer, Berlin (1993). · Zbl 0877.94039 |
| [34] | Raddum H.: Algebraic analysis of the Simon block cipher family. In: Lauter, K.E., Rodríguez-Henríquez, F. (eds.) Progress in Cryptology—LATINCRYPT 2015. Proceedings of the 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, 23-26 Aug 2015. Lecture Notes in Computer Science, vol. 9230, pp. 157-169. Springer, Berlin (2015). · Zbl 1370.94540 |
| [35] | Sasaki Y., Yasuda K.: Known-key distinguishers on 11-round Feistel and collision attacks on its hashing modes. In: Joux, A. (ed.) Fast Software Encryption—18th International Workshop, FSE 2011, Lyngby, Denmark, 13-16 Feb 2011, Revised Selected Papers. Lecture Notes in Computer Science, vol. 6733, pp. 397-415. Springer, Berlin (2011). · Zbl 1307.94095 |
| [36] | Sasaki Y.: Known-key attacks on Rijndael with large blocks and strengthening ShiftRow parameter. In: Echizen, I., Kunihiro, N., Sasaki, R. (eds.) Advances in Information and Computer Security. Proceedings of the 5th International Workshop on Security, IWSEC 2010, Kobe, Japan, 22-24 Nov 2010. Lecture Notes in Computer Science vol. 6434, pp. 301-315. Springer, Berlin (2010). |
| [37] | Shanmugam D., Selvam R., Annadurai S.: Differential power analysis attack on SIMON and LED block ciphers. In: Chakraborty, R.S., Matyas, V., Schaumont, P. (eds.) Proceedings of the 4th International Conference on Security, Privacy, and Applied Cryptography Engineering, SPACE 2014, Pune, India, 18-22 Oct 2014. Lecture Notes in Computer Science, vol. 8804, pp. 110-125. Springer, Berlin (2014). |
| [38] | Shi D., Hu L., Sun S., Song L., Qiao K., Ma X.: Improved linear (hull) cryptanalysis of round-reduced versions of SIMON. IACR Cryptology ePrint Archive 2014, 973 (2014). |
| [39] | Shibutani K., Isobe T., Hiwatari H., Mitsuda A., Akishita T., Shirai T.: Piccolo: an ultra-lightweight blockcipher. In: Preneel, B., Takagi, T., (eds.) Proceedings of the 13th International Workshop on Cryptographic Hardware and Embedded Systems—CHES 2011, Nara, Japan, 28 Sept-1 Oct 2011. Lecture Notes in Computer Science, vol. 6917, pp. 342-357. Springer, Berlin (2011). · Zbl 1291.94154 |
| [40] | Song L., Hu L., Ma B., Shi D.: Match box meet-in-the-middle attacks on the SIMON family of block ciphers. In: Eisenbarth, T., Öztürk, E. (eds.) Lightweight Cryptography for Security and Privacy-Third International Workshop, LightSec 2014, Istanbul, Turkey, 1-2 Sept, 2014, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8898, pp. 140-151. Springer, Berlin (2014). · Zbl 1382.94162 |
| [41] | Sun S., Hu L., Wang P., Qiao K., Ma X., Song L.: Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: Sarkar, P., Iwata, T., (eds.) Advances in Cryptology—ASIACRYPT 2014, Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., 7-11 Dec 2014. Part I. Lecture Notes in Computer Science, vol. 8873, pp. 158-178. Springer, Berlin (2014). · Zbl 1306.94093 |
| [42] | Suzaki T., Minematsu K., Morioka S., Kobayashi E.: TWINE: a lightweight block cipher for multiple platforms. In: Knudsen, L.R., Wu, H. (eds.) Selected Areas in Cryptography: 19th International Conference, SAC 2012, Windsor, ON, Canada, 15-16 Aug 2012, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7707, pp. 339-354. Springer, Berlin (2012). · Zbl 1327.94075 |
| [43] | Takahashi J., Fukunaga T.: Fault analysis on SIMON family of lightweight block ciphers. In: Lee, J., Kim, J. (eds.) 17th International Conference on Information Security and Cryptology—ICISC 2014, Seoul, Korea, 3-5 Dec 2014, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8949, pp. 175-189. Springer, Berlin (2014). · Zbl 1356.94084 |
| [44] | Wang N., Wang X., Jia K., Zhao J.: Improved differential attacks on reduced SIMON versions. IACR Cryptology ePrint Archive 2014, 448 (2014). |
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.
