Skip to main content
Top
Published in: Designs, Codes and Cryptography 11/2020

24-07-2020

The phantom of differential characteristics

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

Published in: Designs, Codes and Cryptography | Issue 11/2020

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
Footnotes
1
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.
 
2
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.
 
Literature
1.
go back to reference 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). 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).
2.
go back to reference 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 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).
3.
go back to reference 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., 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).
4.
go back to reference 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., 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).
5.
go back to reference 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). 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).
6.
go back to reference 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). 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).
7.
go back to reference 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). 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).
8.
go back to reference 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). 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).
9.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference Daemen J., Rijmen V.: AES and the wide trail design strategy. In: EUROCRYPT 2002, pp. 108–109 (2002). Daemen J., Rijmen V.: AES and the wide trail design strategy. In: EUROCRYPT 2002, pp. 108–109 (2002).
12.
go back to reference Daemen J., Rijmen V.: The Design of Rijndael: AES-The Advanced Encryption Standard. Information Security and CryptographySpringer, Berlin (2002).CrossRef Daemen J., Rijmen V.: The Design of Rijndael: AES-The Advanced Encryption Standard. Information Security and CryptographySpringer, Berlin (2002).CrossRef
13.
go back to reference Daemen J., Rijmen V.: Plateau characteristics. IET Inf. Secur. 1(1), 11–17 (2007).CrossRef Daemen J., Rijmen V.: Plateau characteristics. IET Inf. Secur. 1(1), 11–17 (2007).CrossRef
14.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference Lai X.: Higher order derivatives and differential cryptanalysis. Commun. Cryptogr. 276, 227–233 (1994).CrossRef Lai X.: Higher order derivatives and differential cryptanalysis. Commun. Cryptogr. 276, 227–233 (1994).CrossRef
23.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference National Bureau of Standards: Data Encryption Standard. US Department of Commerce, FIPS Publication 46 (1977). National Bureau of Standards: Data Encryption Standard. US Department of Commerce, FIPS Publication 46 (1977).
29.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference Sun L., Wang W., Wang M.: More accurate differential properties of LED64 and Midori64. IACR Trans. Symmetric Cryptol. 2018(3), 93–123 (2018). Sun L., Wang W., Wang M.: More accurate differential properties of LED64 and Midori64. IACR Trans. Symmetric Cryptol. 2018(3), 93–123 (2018).
34.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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).
Metadata
Title
The phantom of differential characteristics
Authors
Yunwen Liu
Wenying Zhang
Bing Sun
Vincent Rijmen
Guoqiang Liu
Chao Li
Shaojing Fu
Meichun Cao
Publication date
24-07-2020
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 11/2020
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-020-00782-3

Other articles of this Issue 11/2020

Designs, Codes and Cryptography 11/2020 Go to the issue

Premium Partner