Out of non-linearity: search impossible differentials by the bitwise characteristic matrix. (English) Zbl 1504.94194
Deng, Robert (ed.) et al., Information security practice and experience. 16th international conference, ISPEC 2021, Nanjing, China, December 17–19, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13107, 69-89 (2021).
Summary: In this paper, we propose the \(\mathcal{M} \)-method which uses the bitwise characteristic matrix to search impossible differentials. \( \mathcal{M} \)-method exploits not only the linear components but also partial information of non-linear components. According to the principle of miss-in-the-middle, we construct two different types of contradiction to search the impossible differentials with limited time and memory complexity by calculating \(\mathcal{M}_{en}^{r_1}\) and \(\mathcal{M}_{de}^{r_2}\) which represent \(r_1\) rounds encryption and \(r_2\) rounds decryption, respectively. Compared with the previous methods, our technique is comprehensible and fast especially for large block size.
As a result, we find the 7-round impossible differentials of GIFT-128, the 5-round impossible differentials of PRIDE, and the 4-round impossible differentials of Pyjamask-96. For GIFT-64, PRESENT, RECTANGLE which are well-analyzed by MILP-method or SAT-method, we construct new impossible differentials. Moreover, the efficiency of our method will not be influenced by the block size, which makes us find the new 5-round impossible differentials of the 320-bit permutation of ASCON.
For the entire collection see [Zbl 1492.68016].
As a result, we find the 7-round impossible differentials of GIFT-128, the 5-round impossible differentials of PRIDE, and the 4-round impossible differentials of Pyjamask-96. For GIFT-64, PRESENT, RECTANGLE which are well-analyzed by MILP-method or SAT-method, we construct new impossible differentials. Moreover, the efficiency of our method will not be influenced by the block size, which makes us find the new 5-round impossible differentials of the 320-bit permutation of ASCON.
For the entire collection see [Zbl 1492.68016].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Albrecht, M.R., Driessen, B., Kavun, E.B., Leander, G., Paar, C., Yalçın, T.: Block ciphers – focus on the linear layer (feat. PRIDE). In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 57-76. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_4 · Zbl 1317.94079 · doi:10.1007/978-3-662-44371-2_4 |
| [2] | Banik, S., Pandey, S.K., Peyrin, T., Sasaki, Y., Sim, S.M., Todo, Y.: Gift: a small present. In: Fischer, W., Homma, N. (eds.) Cryptographic Hardware and Embedded Systems - CHES 2017, pp. 321-345. Springer Cham (2017) · Zbl 1450.94026 |
| [3] | 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). https://doi.org/10.1007/3-540-48910-X_2 · Zbl 0927.94013 · doi:10.1007/3-540-48910-X_2 |
| [4] | Bogdanov, A., et al.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450-466. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74735-2_31 · Zbl 1142.94334 · doi:10.1007/978-3-540-74735-2_31 |
| [5] | Cui, T., Jia, K., Fu, K., Chen, S., Wang, M.: New automatic search tool for impossible differentials and zero-correlation linear approximations. IACR Cryptol. ePrint Arch. p. 689 (2016). http://eprint.iacr.org/2016/689 |
| [6] | Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 278-299. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_16 · Zbl 1239.94045 · doi:10.1007/978-3-642-01001-9_16 |
| [7] | Dobraunig, C., Eichlseder, M., Mendel, F., Schlffer, M.: Ascon - submission to the CASEAR competition (2016) |
| [8] | Dolmatov, V.: GOST R 34.12-2015: Block cipher “kuznyechik”. In: RFC, pp. 1-14 (2016) |
| [9] | Guo, J., Peyrin, T., Poschmann, A.: The PHOTON family of lightweight hash functions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 222-239. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_13 · Zbl 1287.94069 · doi:10.1007/978-3-642-22792-9_13 |
| [10] | Hu, X., Li, Y., Jiao, L., Tian, S., Wang, M.: Mind the propagation of states. In: Moriai, S., Wang, H. (eds.) Advances in Cryptology - ASIACRYPT 2020, pp. 415-445. Springer, Cham (2020) · Zbl 1511.94113 |
| [11] | Kim, J., Hong, S., Sung, J., Lee, S., Lim, J., Sung, S.: Impossible differential cryptanalysis for block cipher structures. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 82-96. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24582-7_6 · Zbl 1123.94352 · doi:10.1007/978-3-540-24582-7_6 |
| [12] | Knudsen, L.: Deal - a 128-bit block cipher. In: NIST AES Proposal (1998) |
| [13] | Liu, Y., Weiming T., Shen, Z.: H.L.L.W.: Impossible differential cryptanalysis of lightweight block cipher pyjamask. Appl. Res. Comput. (2021). https://doi.org/10.19734/j.issn.1001-3695.2021.03.0063 |
| [14] | Luo, Y., Wu, Z., Lai, X., Gong, G.: A unified method for finding impossible differentials of block cipher structures. IACR Cryptol. ePrint Arch. p. 627 (2009). http://eprint.iacr.org/2009/627 |
| [15] | Sasaki, Yu., Todo, Y.: New impossible differential search tool from design and cryptanalysis aspects. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 185-215. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_7 · Zbl 1394.94941 · doi:10.1007/978-3-319-56617-7_7 |
| [16] | Shen, X., Li, R., Sun, B., Cheng, L., Li, C., Liao, M.: Dual relationship between impossible differentials and zero correlation linear hulls of simon-like ciphers. In: Liu, J.K., Samarati, P. (eds.) Information Security Practice and Experience, pp. 237-255. Springer International Publishing, Cham (2017) · Zbl 1506.94064 · doi:10.1007/978-3-319-72359-4_14 |
| [17] | Shen, X., Liu, G., Sun, B., Li, C.: Impossible differentials of SPN ciphers. In: Chen, K., Lin, D., Yung, M. (eds.) Information Security and Cryptology, pp. 47-63. Springer, Cham (2017) · Zbl 1372.94440 · doi:10.1007/978-3-319-54705-3_4 |
| [18] | Sun, B., Liu, M., Guo, J., Rijmen, V., Li, R.: Provable security evaluation of structures against impossible differential and zero correlation linear cryptanalysis. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 196-213. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_8 · Zbl 1347.94058 · doi:10.1007/978-3-662-49890-3_8 |
| [19] | Sun, B., et al.: Links among impossible differential, integral and zero correlation linear cryptanalysis. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 95-115. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_5 · Zbl 1347.94059 · doi:10.1007/978-3-662-47989-6_5 |
| [20] | Tezcan, C.: Improbable differential attacks on PRESENT using undisturbed bits. J. Comput. Appl. Math. 259, 503-511 (2014) · Zbl 1354.94048 |
| [21] | Wu, S., Wang, M.: Automatic search of truncated impossible differentials for word-oriented block ciphers. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 283-302. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34931-7_17 · Zbl 1295.94157 · doi:10.1007/978-3-642-34931-7_17 |
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.
