Top

Published in:

2020 | OriginalPaper | Chapter

Improved Differential-Linear Attacks with Applications to ARX Ciphers

Authors : Christof Beierle, Gregor Leander, Yosuke Todo

Published in: Advances in Cryptology – CRYPTO 2020

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Out of Oddity – New Cryptanalytic Techniques Against Symmetric Primitives Optimized for Integrity Proof Systems

next chapter 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

Title: Improved Differential-Linear Attacks with Applications to ARX Ciphers
Authors: Christof Beierle
Gregor Leander
Yosuke Todo
Publisher: Springer International Publishing
Book: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56876-4

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

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

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner