nach oben

Designs, Codes and Cryptography

Erschienen in:

24.07.2020

The phantom of differential characteristics

verfasst von: Yunwen Liu, Wenying Zhang, Bing Sun, Vincent Rijmen, Guoqiang Liu, Chao Li, Shaojing Fu, Meichun Cao

Erschienen in: Designs, Codes and Cryptography | Ausgabe 11/2020

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

For differential cryptanalysis under the single-key model, the key schedules hardly need to be exploited in constructing the characteristics, which is based on the hypothesis of stochastic equivalence. In this paper, we study a profound effect of the key schedules on the validity of the differential characteristics. Noticing the sensitivity in the probability of the characteristics to specific keys, we label the keys where a characteristic has nonzero probability by effective keys. We propose the concept of singular characteristics which are characteristics with no effective keys, and exploit an algorithm to sieve them out by studying the key schedule. We show by a differential characteristic of PRINCE whose expected differential probability is much larger than that of a random permutation, i.e., \(2^{-35}\) vs. \(2^{-64}\). Yet, it is indeed singular which could be mis-used to mount a differential attack. Singular characteristics are found for 3-round AES and 3-round Midori-128 as well. Furthermore, taking the possible mismatches of the effective keys in a number of differential characteristics into consideration, we present singular clusters which indicates an empty intersection of the corresponding effective keys, and this is evidenced by showing two differential characteristics of the 2-round AES. We also show that characteristics are tightly linked to the key schedule, as shown in the paper, a valid characteristic in the AES-128 can be singular for the AES-192. Our results indicate a gap over the perspectives of the designers and the attackers, which warns the latter to validate the theoretically-built distinguishers. Therefore, a closer look into the characteristics is inevitable before any attack is claimed.

Vorheriger Artikel LCD codes and self-orthogonal codes in generalized dihedral group algebras

Nächster Artikel On post-processing in the quantum algorithm for computing short discrete logarithms

Although characteristics with fewer active S-boxes are often preferred by attackers, it is difficult to confirm that such characteristics are not singular. So we construct the example in such a way that the characteristic is guaranteed to possess at least two right inputs. Here, we conjecture that in general a valid characteristic would probably turn into a singular one when the key schedule is modified.

Some experiments show that the estimation under the hypothesis is rather close to reality, see for instance, [21]. It is noteworthy that the irregularity is what the attackers have to pay extra attention to, which is supported by a number of studies such as those we have previously referred to in this paper.

Banik S., Bogdanov A., Isobe T., Shibutani K., Hiwatari H., Akishita T., Regazzoni F.: Midori: a block cipher for low energy. In: Advances in Cryptology—ASIACRYPT 2015, pp. 411–436. Springer (2015).

Biham E., Shamir A.: Differential cryptanalysis of DES-like cryptosystems. In: Advances in Cryptology—CRYPTO ’90, 10th Annual International Cryptology Conference, Santa Barbara, California, USA, 11–15 August 1990. Proceedings, pp. 2–21 (1990).

Biham E., Shamir A.: Differential cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer. In: Advances in Cryptology—CRYPTO ’91, 11th Annual International Cryptology Conference, Santa Barbara, California, USA, 11–15 August 1991. Proceedings, pp. 156–171 (1991).

Biham E., Biryukov A., Shamir A.: Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials. In: Advances in Cryptology—EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, 2–6 May 1999. Proceeding, pp. 12–23 (1999).

Biham E., Dunkelman O., Keller N.: New results on boomerang and rectangle attacks. In: Fast Software Encryption, 9th International Workshop, FSE 2002, Leuven, Belgium, 4–6 February 2002. Revised Papers, pp. 1–16 (2002).

Biryukov A., Khovratovich D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: Advances in Cryptology—ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, 6–10 December 2009. Proceedings, pp. 1–18 (2009).

Blondeau C., Gérard B.: Multiple differential cryptanalysis: theory and practice. In: Fast Software Encryption—18th International Workshop, FSE 2011, Lyngby, Denmark, 13–16 February 2011. Revised Selected Papers, pp. 35–54 (2011).

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: Advances in Cryptology—ASIACRYPT 2012—18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, 2–6 December 2012. Proceedings, pp. 208–225 (2012).

Canteaut A., Fuhr T., Gilbert H., Naya-Plasencia M., Reinhard J.: Multiple differential cryptanalysis of round-reduced PRINCE. In: Fast Software Encryption—21st International Workshop, FSE 2014, London, UK, 3–5 March 2014. Revised Selected Papers, pp. 591–610 (2014).

10.

Canteaut A., Lambooij E., Neves S., Rasoolzadeh S., Sasaki Y., Stevens M.: Refined probability of differential characteristics including dependency between multiple rounds. IACR Trans. Symmetric Cryptol. 2017(2), 203–227 (2017).

11.

Daemen J., Rijmen V.: AES and the wide trail design strategy. In: EUROCRYPT 2002, pp. 108–109 (2002).

12.

Daemen J., Rijmen V.: The Design of Rijndael: AES-The Advanced Encryption Standard. Information Security and CryptographySpringer, Berlin (2002).CrossRef

13.

Daemen J., Rijmen V.: Plateau characteristics. IET Inf. Secur. 1(1), 11–17 (2007).CrossRef

14.

Derbez P., Fouque P., Jean J.: Improved key recovery attacks on reduced-round AES in the single-key setting. In: Advances in Cryptology—EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, 26–30 May 2013. Proceedings, pp. 371–387 (2013).

15.

Gauravaram P., Knudsen L.R., Matusiewicz K., Mendel F., Rechberger C., Schläffer M., Thomsen S.S.: Grøstl-a SHA-3 candidate. In: Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2009).

16.

Hall C., Kelsey J., Rijmen V., Schneier B., Wagner D.: Cryptanalysis of SPEED. In: Selected Areas in Cryptography ’98, SAC’98, Kingston, Ontario, Canada, 17–18 August 1998. Proceedings, pp. 319–338 (1998).

17.

Karpman P., Peyrin T., Stevens M.: Practical free-start collision attacks on 76-step SHA-1. In: Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, USA, 16–20 August 2015. Proceedings, Part I, pp. 623–642 (2015).

18.

Khovratovich D., Nikolic I., Pieprzyk J., Sokolowski P., Steinfeld R.: Rotational cryptanalysis of ARX revisited. In: Fast Software Encryption—22nd International Workshop, FSE 2015, Istanbul, Turkey, 8–11 March 2015. Revised Selected Papers, pp. 519–536 (2015).

19.

Knudsen L.R.: Iterative characteristics of DES and s\({^2}\)-DES. In: Advances in Cryptology—CRYPTO ’92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, 16–20 August 1992. Proceedings, pp. 497–511 (1992).

20.

Knudsen L.R.: Truncated and higher order differentials. In: Fast Software Encryption: Second International Workshop, Leuven, Belgium, 14–16 December 1994. Proceedings, pp. 196–211 (1994).

21.

Kölbl S., Leander G., Tiessen T.: Observations on the SIMON block cipher family. In: Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, USA, 16–20 August 2015. Proceedings, Part I, pp. 161–185. Springer (2015).

22.

Lai X.: Higher order derivatives and differential cryptanalysis. Commun. Cryptogr. 276, 227–233 (1994).CrossRef

23.

Lai X., Massey J.L., Murphy S.: Markov ciphers and differential cryptanalysis. In: Advances in Cryptology—EUROCRYPT ’91, Workshop on the Theory and Application of Cryptographic Techniques, Brighton, UK, 8–11 April 1991, Proceedings, pp. 17–38 (1991).

24.

Lallemand V., Naya-Plasencia M.: Cryptanalysis of KLEIN. In: Fast Software Encryption—21st International Workshop, FSE 2014, London, UK, 3–5 March 2014. Revised Selected Papers, pp. 451–470 (2014).

25.

Leander G., Abdelraheem M., AlKhzaimi H., Zenner E.: A cryptanalysis of PRINTcipher: the invariant subspace attack. In: Advances in Cryptology—CRYPTO 2011—31st Annual Cryptology Conference, Santa Barbara, CA, USA, 14–18 August 2011. Proceedings, pp. 206–221. Springer (2011).

26.

Leurent G.: Analysis of differential attacks in ARX constructions. In: Advances in Cryptology—ASIACRYPT 2012—18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, 2–6 December 2012. Proceedings, pp. 226–243 (2012).

27.

Mendel F., Rechberger C., Schläffer M., Thomsen S.S.: The rebound attack: cryptanalysis of reduced whirlpool and Grøstl. In: Fast Software Encryption, 16th International Workshop, FSE 2009, Leuven, Belgium, 22–25 February 2009. Revised Selected Papers, pp. 260–276 (2009).

28.

National Bureau of Standards: Data Encryption Standard. US Department of Commerce, FIPS Publication 46 (1977).

29.

Stevens M., Bursztein E., Karpman P., Albertini A., Markov Y.: The first collision for full SHA-1. In: Advances in Cryptology—CRYPTO 2017—37th Annual International Cryptology Conference, Santa Barbara, CA, USA, 20–24 August 2017. Proceedings, Part I, pp. 570–596 (2017).

30.

Sun B., Liu Z., Rijmen V., Li R., Cheng L., Wang Q., AlKhzaimi H., Li C.: Links among impossible differential, integral and zero correlation linear cryptanalysis. In: Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, USA, 16–20 August 2015. Proceedings, Part I, pp. 95–115 (2015).

31.

Sun B., Liu M., Guo J., Rijmen V., Li R.: Provable security evaluation of structures against impossible differential and zero correlation linear cryptanalysis. In: Advances in Cryptology—EUROCRYPT 2016—35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, 8–12 May 2016. Proceedings, Part I, pp. 196–213 (2016).

32.

Sun S., Gerault D., Lafourcade P., Yang Q., Todo Y., Qiao K., Hu L.: Analysis of AES, skinny, and others with constraint programming. IACR Trans. Symmetric Cryptol. 2017(1), 281–306 (2017).

33.

Sun L., Wang W., Wang M.: More accurate differential properties of LED64 and Midori64. IACR Trans. Symmetric Cryptol. 2018(3), 93–123 (2018).

34.

Tolba M., Abdelkhalek A., Youssef A.M.: Truncated and multiple differential cryptanalysis of reduced round Midori128. In: Information Security—19th International Conference, ISC 2016, Honolulu, HI, USA, 3–6 September 2016. Proceedings, pp. 3–17 (2016).

35.

Wagner D.: The boomerang attack. In: Fast Software Encryption, 6th International Workshop, FSE ’99, Rome, Italy, 24–26 March 1999. Proceedings, pp. 156–170 (1999).

36.

Wang X., Yu H.: How to break MD5 and other hash functions. In: Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 22–26 May 2005. Proceedings, pp. 19–35 (2005).

37.

Wang X., Yin Y.L., Yu H.: Finding collisions in the full SHA-1. In: Advances in Cryptology—CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, 14–18 August 2005. Proceedings, pp. 17–36 (2005).

38.

Wang G., Keller N., Dunkelman O.: The delicate issues of addition with respect to XOR differences. In: Selected Areas in Cryptography, 14th International Workshop, SAC 2007, Ottawa, Canada, 16–17 August 2007. Revised Selected Papers, pp. 212–231 (2007).

39.

Wang M., Sun Y., Tischhauser E., Preneel B.: A model for structure attacks, with applications to PRESENT and Serpent. In: Fast Software Encryption—19th International Workshop, FSE 2012, Washington, DC, USA, 19–21 March 2012. Revised Selected Papers, pp. 49–68 (2012).

Titel: The phantom of differential characteristics
verfasst von: Yunwen Liu
Wenying Zhang
Bing Sun
Vincent Rijmen
Guoqiang Liu
Chao Li
Shaojing Fu
Meichun Cao
Publikationsdatum: 24.07.2020
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 11/2020
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-020-00782-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 11/2020

On post-processing in the quantum algorithm for computing short discrete logarithms

Fast computation of linear approximation over certain composition functions and applications to SNOW 2.0 and SNOW 3G

Access balancing in storage systems by labeling partial Steiner systems

Linear complementary pair of group codes over finite chain rings

Doubly resolvable Steiner quadruple systems of orders

Tightly CCA-secure encryption scheme in a multi-user setting with corruptions