nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Improved Differential-Linear Attacks with Applications to ARX Ciphers

verfasst von : Christof Beierle, Gregor Leander, Yosuke Todo

Erschienen in: Advances in Cryptology – CRYPTO 2020

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We present several improvements to the framework of differential-linear attacks with a special focus on ARX ciphers. As a demonstration of their impact, we apply them to Chaskey and ChaCha and we are able to significantly improve upon the best attacks published so far.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Out of Oddity – New Cryptanalytic Techniques Against Symmetric Primitives Optimized for Integrity Proof Systems

Nächstes Kapitel Cryptanalysis Results on Spook

After the submission of this paper, the authors of [13] independently found the same distinguisher without applying the technique for improving over the differential part, and the presented attack complexities are very close to ours.

Under the assumption that the sets \(\{\langle \varGamma _{\mathrm{out}}, E(x) \rangle \oplus \langle \varGamma _{\mathrm{out}}, E(x \oplus \varDelta _{\mathrm{in}}) \rangle \mid x \in \mathcal {X}\}\) and \(\{\langle \varGamma _{\mathrm{out}}, E(x) \rangle \oplus \langle \varGamma _{\mathrm{out}}, E(x \oplus \varDelta _{\mathrm{in}}) \rangle \mid x \in \mathcal {S}\}\) are indistinguishable, where \(\mathcal {S}\) denotes a set of uniformly chosen samples of the same size as \(\mathcal {X}\).

Or at least with a cost much lower than \(p^{-1}\), see Sect. 3.2.

Of course, the discarded data has to be considered in the data complexity of the attack.

If \(|q_{i,j}|\) is not too small and if the number s of approximations is not too huge, we can empirically compute \(q_{i,j}\) for all i, j. In other cases, we estimate \(q_{i,j} = \mathbf {Cor}_{x \in \mathcal {X} }\left[ \langle \varGamma _{\mathrm{out}}^{(p_i)},z \rangle \oplus \langle \varGamma _{\mathrm{out}}^{(p_j)},\tilde{z} \rangle \right] \) by assuming indistinguishability of the sets \(\{\langle \varGamma _{\mathrm{out}}^{(p_i)},z \rangle \oplus \langle \varGamma _{\mathrm{out}}^{(p_j)},\tilde{z} \rangle \mid x \in \mathcal {X} \text { s.t. } (y,\tilde{y}) \in \mathcal {T}_{p_i} \times \mathcal {T}_{p_j}\}\) and \(\{\langle \varGamma _{\mathrm{out}}^{(p_i)},z \rangle \oplus \langle \varGamma _{\mathrm{out}}^{(p_j)},\tilde{z} \rangle \mid x \in \mathcal {S}\}\), where \(\mathcal {S}\) is a set of uniformly random samples of \(\mathcal {X}\) of suitable size.

Note that we might choose different \((\varGamma _{\mathrm{out}}^{(b_0b_1)},\gamma ^{(b_0b_1)})\) for \(\mathcal {T}_{b_0b_1}\). For example, for

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-56877-1_12/503460_1_En_12_IEq319_HTML.gif

, we might alternatively choose which is obtained from Lemma 2. To verify, note that \(\mathcal {S}_4 \subseteq \mathcal {S}_1\).

Note that \(\mathcal {P}\) is not necessarily a direct sum of \(\mathcal {P}_1\), \(\mathcal {P}_2\), and \(\mathcal {P}_3\). In other words, the dimension of \(\mathcal {P}\) might be smaller than 6, for instance if \(i=j\), i.e., \(\zeta _1 = \zeta _2\).

The first case is the exactly same as the one shown in [20], but its correlation was reported as \(2^{-6.1}\). We are not sure the reason of this gap, but we think that \(2^{-6.1}\) refers to the bias instead of the correlation.

It means that the success probability is \(0.489 \times 2 = 0.978\) under the condition that the right pair is successfully obtained during \(2^{17.206}\) iterations.

Note that it means that the success probability is \(0.499 \times 2 = 0.999\) under the condition that the right pair is successfully obtained during \(2^{7}\) iterations.

Aumasson, J.-P., Fischer, S., Khazaei, S., Meier, W., Rechberger, C.: New features of latin dances: analysis of Salsa, ChaCha, and Rumba. In: Nyberg, K. (ed.) FSE 2008, Revised Selected Papers. LNCS, vol. 5086, pp. 470–488. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-71039-4_30CrossRef

Aumasson, J.P., Henzen, L., Meier, W., Phan, R.C.W.: SHA-3 proposal Blake. In: Submission to NIST (2008)

Aumasson, J.-P., Neves, S., Wilcox-O’Hearn, Z., Winnerlein, C.: BLAKE2: simpler, smaller, fast as MD5. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 119–135. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38980-1_8CrossRef

Bar-On, A., Dunkelman, O., Keller, N., Weizman, A.: DLCT: a new tool for differential-linear cryptanalysis. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part I. LNCS, vol. 11476, pp. 313–342. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_11CrossRef

Beierle, C., et al.: Lightweight AEAD and Hashing using the sparkle permutation family. IACR Trans. Symm. Cryptol. 2020(S1), 208–261 (2020)

Bernstein, D.J.: ChaCha, a variant of Salsa20 (2008). http://cr.yp.to/chacha.html

Bernstein, D.J.: The Salsa20 family of stream ciphers. In: Robshaw, M., Billet, O. (eds.) New Stream Cipher Designs. LNCS, vol. 4986, pp. 84–97. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68351-3_8CrossRef

Biham, E., Carmeli, Y.: An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X. In: Joux, A., Youssef, A. (eds.) SAC 2014, Revised Selected Papers. LNCS, vol. 8781, pp. 59–76. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13051-4_4CrossRef

Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_1CrossRef

10.

Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P. (eds.) Boolean Methods and Models. Cambridge University Press (2007)

11.

Choudhuri, A.R., Maitra, S.: Significantly improved multi-bit differentials for reduced round Salsa and ChaCha. IACR Trans. Symm. Cryptol. 2016(2), 261–287 (2016)

12.

Collard, B., Standaert, F.-X., Quisquater, J.-J.: Improving the time complexity of Matsui’s linear cryptanalysis. In: Nam, K.-H., Rhee, G. (eds.) ICISC 2007. LNCS, vol. 4817, pp. 77–88. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-76788-6_7CrossRef

13.

Coutinho, M., Neto, T.C.S.: New multi-bit differentials to improve attacks against ChaCha. IACR Cryptology ePrint Archive 2020/350 (2020). https://eprint.iacr.org/2020/350

14.

Dey, S., Sarkar, S.: Improved analysis for reduced round Salsa and ChaCha. Discrete Appl. Math. 227, 58–69 (2017)MathSciNetCrossRef

15.

Dinu, D., Perrin, L., Udovenko, A., Velichkov, V., Großschädl, J., Biryukov, A.: Design strategies for ARX with provable bounds: Sparx and LAX. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 484–513. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_18CrossRef

16.

Hermelin, M., Cho, J.Y., Nyberg, K.: Multidimensional linear cryptanalysis. J. Cryptol. 32(1), 1–34 (2019)MathSciNetCrossRef

17.

Khovratovich, D., Nikolić, I.: Rotational cryptanalysis of ARX. In: Hong, S., Iwata, T. (eds.) FSE 2010, Revised Selected Papers. LNCS, vol. 6147, pp. 333–346. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13858-4_19CrossRef

18.

Knudsen, L., Wagner, D.: Integral cryptanalysis. In: Daemen, J., Rijmen, V. (eds.) FSE 2002, Revised Papers. LNCS, vol. 2365, pp. 112–127. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45661-9_9CrossRef

19.

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). https://doi.org/10.1007/3-540-48658-5_3CrossRef

20.

Leurent, G.: Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 344–371. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_14CrossRef

21.

Lipmaa, H., Moriai, S.: Efficient algorithms for computing differential properties of addition. In: Matsui, M. (ed.) FSE 2001, Revised Papers. LNCS, vol. 2355, pp. 336–350. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45473-X_28CrossRef

22.

Maitra, S.: Chosen IV cryptanalysis on reduced round ChaCha and Salsa. Discrete Appl. Math. 208, 88–97 (2016)MathSciNetCrossRef

23.

Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48285-7_33CrossRef

24.

Mouha, N., Mennink, B., Van Herrewege, A., Watanabe, D., Preneel, B., Verbauwhede, I.: Chaskey: an efficient MAC algorithm for 32-bit microcontrollers. In: Joux, A., Youssef, A. (eds.) SAC 2014, Revised Selected Papers. LNCS, vol. 8781, pp. 306–323. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13051-4_19CrossRef

25.

Nyberg, K., Wallén, J.: Improved linear distinguishers for SNOW 2.0. In: Robshaw, M. (ed.) FSE 2006, Revised Selected Papers. LNCS, vol. 4047, pp. 144–162. Springer, Heidelberg (2006). https://doi.org/10.1007/11799313_10CrossRef

26.

Shi, Z., Zhang, B., Feng, D., Wu, W.: Improved key recovery attacks on reduced-round Salsa20 and ChaCha. In: Kwon, T., Lee, M.-K., Kwon, D. (eds.) ICISC 2012, Revised Selected Papers. LNCS, vol. 7839, pp. 337–351. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37682-5_24CrossRef

27.

Shimizu, A., Miyaguchi, S.: Fast data encipherment algorithm FEAL. In: Chaum, D., Price, W.L. (eds.) EUROCRYPT 1987. LNCS, vol. 304, pp. 267–278. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-39118-5_24CrossRef

28.

Todo, Y., Leander, G., Sasaki, Yu.: Nonlinear invariant attack. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 3–33. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_1CrossRef

29.

Wallén, J.: Linear approximations of addition modulo 2\(^{ {n}}\). In: Johansson, T. (ed.) FSE 2003, Revised Papers. LNCS, vol. 2887, pp. 261–273. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39887-5_20

Titel: Improved Differential-Linear Attacks with Applications to ARX Ciphers
verfasst von: Christof Beierle
Gregor Leander
Yosuke Todo
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56876-4

Electronic ISBN: 978-3-030-56877-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-56877-1_12

Springer Professional

Abstract

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

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner