Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptology
Published in: Journal of Cryptology 4/2022

01-10-2022 | Research Article

Improved Differential-Linear Attacks with Applications to ARX Ciphers

Authors: Christof Beierle, Marek Broll, Federico Canale, Nicolas David, Antonio Flórez-Gutiérrez, Gregor Leander, María Naya-Plasencia, Yosuke Todo

Published in: Journal of Cryptology | Issue 4/2022

Log in

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

search-config
loading …

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.
previous article The Inverse of and Its Applications to Rasta-Like Ciphers

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
Appendix
Available only for authorised users
Footnotes
1
After presenting those results at CRYPTO 2020 [1], improved attacks on ChaCha have been proposed [26]. Later, [27] pointed out mistakes in some parts of [26], leading to an updated version that has been published on the Cryptology ePrint Archive [28]. Very recently, another improved differential-linear attack has been presented [25].
 
2
Under the assumption that the sets \(\{\langle \Gamma _{\mathrm {out}}, E(x) \rangle \oplus \langle \Gamma _{\mathrm {out}}, E(x \oplus \Delta _{\mathrm {in}}) \rangle \mid x \in {\mathcal {X}}\}\) and \(\{\langle \Gamma _{\mathrm {out}}, E(x) \rangle \oplus \langle \Gamma _{\mathrm {out}}, E(x \oplus \Delta _{\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}}\).
 
3
Or at least with a cost much lower than \(p^{-1}\), see Sect. 5.2.
 
4
The first case is exactly the one shown in [19], but its correlation was reported as \(2^{-6.1}\). We are not sure about the reason for this gap, but we think that \(2^{-6.1}\) refers to the bias instead of the correlation.
 
5
The theoretical justification is discussed in [27] after the proposal of our original paper [1].
 
6
This correlation is estimated originally when the key \(k_7\) changes randomly, but \(k_7\) is a fixed constant. These correlations are much higher or lower according to the fixed key, but on key average, which is the natural attack assumption for symmetric-key ciphers, the average correlation is \(-2^{-1}\).
 
7
Note that it means that the success probability is \(0.491 \times 2 = 0.982\) under the condition that the right pair is successfully obtained during \(2^{5}\) iterations.
 
8
This is the same attack proposed in our original paper [1].
 
9
Note that it means that the success probability is almost 1 under the condition that the right pair is successfully obtained during \(2^{5}\) iterations.
 
10
When we estimate \(\epsilon _a\), we used the average correlation. When we used the median instead of the average, \(\epsilon _a = 2^{-11.1687}\). Then, the data and time complexities are \(2^{49.7856}\) and \(2^{231.823}\), respectively.
 
11
Some follow-up works [25‐27, 41] have been proposed after our original proposal [1]. Our attack is still the best for 6-round attack in the context of key recovery. Even for 7 rounds, there have not been follow-up works that essentially improve the complexity yet. On the other hand, Coutinho and Neto presented more efficient distinguishing attacks in [41], and Miyashita, Ito, and Miyaji showed the key-recovery attack on 7.25 rounds in [25].
 
12
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\).
 
Literature
1.
C. Beierle, G. Leander, Y. Todo, Improved differential-linear attacks with applications to ARX ciphers, in Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Proceedings, Part III. LNCS, vol. 12172 (Springer, Cham, 2020), pp. 329–358
2.
M. Broll, F. Canale, N. David, A. Flórez-Gutiérrez, G. Leander, M. Naya-Plasencia, Y. Todo, Further improving differential-linear attacks: Applications to Chaskey and Serpent. IACR Cryptol. ePrint Arch. 2021, 820 (2021). https://​eprint.​iacr.​org/​2021/​820
3.
A. Shimizu, S. Miyaguchi, Fast data encipherment algorithm FEAL, in Chaum, D., Price, W.L. (eds.) EUROCRYPT ’87, Proceedings. LNCS, vol. 304 (Springer, Berlin, Heidelberg, 1987), pp. 267–278
4.
D.J. Bernstein, The Salsa20 family of stream ciphers, in Robshaw, M.J.B., Billet, O. (eds.) New Stream Cipher Designs - The eSTREAM Finalists. LNCS, vol. 4986 (Springer, Berlin, Heidelberg, 2008), pp. 84–97
5.
6.
J.-P. Aumasson, L. Henzen, W. Meier, R.C.-W. Phan, SHA-3 proposal Blake. Submission to NIST (2008)
7.
J. Aumasson, S. Neves, Z. Wilcox-O’Hearn, C. Winnerlein, BLAKE2: simpler, smaller, fast as MD5, in Jr., M.J.J., Locasto, M.E., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013, Proceedings. LNCS, vol. 7954 (Springer, Berlin, Heidelberg, 2013), pp. 119–135
8.
D. Dinu, L. Perrin, A. Udovenko, V. Velichkov, J. Großschädl, A. Biryukov, Design strategies for ARX with provable bounds: Sparx and LAX, in Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Proceedings, Part I. LNCS, vol. 10031 (Springer, Berlin, Heidelberg, 2016), pp. 484–513
9.
C. Beierle, A. Biryukov, L.C. dos Santos, J. Großschädl, L. Perrin, A. Udovenko, V. Velichkov, Q. Wang, Lightweight AEAD and hashing using the Sparkle permutation family. IACR Trans. Symmetric Cryptol. 2020(S1), 208–261 (2020)CrossRef
10.
N. Mouha, B. Mennink, A.V. Herrewege, D. Watanabe, B. Preneel, I. Verbauwhede, Chaskey: An efficient MAC algorithm for 32-bit microcontrollers, in Joux, A., Youssef, A.M. (eds.) SAC 2014, Revised Selected Papers. LNCS, vol. 8781 (Springer, Cham, 2014), pp. 306–323
11.
L.R. Knudsen, D.A. Wagner, Integral cryptanalysis, in Daemen, J., Rijmen, V. (eds.) FSE 2002, Revised Papers. LNCS, vol. 2365 (Springer, Berlin, Heidelberg, 2002), pp. 112–127
12.
Y. Todo, G. Leander, Y. Sasaki, Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64. J. Cryptol. 32(4), 1383–1422 (2019)MathSciNetCrossRef
13.
D. Khovratovich, I. Nikolic, Rotational cryptanalysis of ARX, in Hong, S., Iwata, T. (eds.) FSE 2010, Revised Selected Papers. LNCS, vol. 6147 (Springer, Berlin, Heidelberg, 2010), pp. 333–346
14.
15.
M. Matsui, Linear cryptanalysis method for DES cipher, in Helleseth, T. (ed.) EUROCRYPT ’93, Proceedings. LNCS, vol. 765 (Springer, Berlin, Heidelberg, 1993), pp. 386–397
16.
H. Lipmaa, S. Moriai, Efficient algorithms for computing differential properties of addition, in Matsui, M. (ed.) FSE 2001, Revised Papers. LNCS, vol. 2355 (Springer, Berlin, Heidelberg, 2001), pp. 336–350
17.
J. Wallén, Linear approximations of addition modulo 2\({}^{\text{n}}\), in Johansson, T. (ed.) FSE 2003, Revised Papers. LNCS, vol. 2887 (Springer, Berlin, Heidelberg, 2003), pp. 261–273
18.
S.K. Langford, M.E. Hellman, Differential-linear cryptanalysis, in Desmedt, Y. (ed.) CRYPTO ’94, Proceedings. LNCS, vol. 839 (Springer, Berlin, Heidelberg, 1994), pp. 17–25
19.
G. Leurent, Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning, in Fischlin, M., Coron, J. (eds.) EUROCRYPT 2016, Proceedings, Part I. LNCS, vol. 9665 (Springer, Berlin, Heidelberg, 2016), pp. 344–371
20.
A.R. Choudhuri, S. Maitra, Significantly improved multi-bit differentials for reduced round Salsa and ChaCha. IACR Trans. Symmetric Cryptol. 2016(2), 261–287 (2016)
21.
22.
J. Aumasson, S. Fischer, S. Khazaei, W. Meier, ,C. Rechberger, New features of Latin dances: Analysis of Salsa, ChaCha, and Rumba, in Nyberg, K. (ed.) FSE 2008, Revised Selected Papers. LNCS, vol. 5086 (Springer, Berlin, Heidelberg, 2008), pp. 470–488
23.
Z. Shi, B. Zhang, D. Feng, W. Wu, Improved key recovery attacks on reduced-round Salsa20 and ChaCha, in Kwon, T., Lee, M., Kwon, D. (eds.) ICISC 2012, Revised Selected Papers. LNCS, vol. 7839 (Springer, Berlin, Heidelberg, 2012), pp. 337–351
24.
25.
26.
M. Coutinho, T.C.S. Neto, Improved linear approximations to ARX ciphers and attacks against ChaCha, in Canteaut, A., Standaert, F. (eds.) EUROCRYPT 2021, Proceedings, Part I. LNCS, vol. 12696 (Springer, Cham, 2021), pp. 711–740
27.
28.
29.
E. Biham, Y. Carmeli, An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X, in Joux, A., Youssef, A.M. (eds.) SAC 2014, Revised Selected Papers. LNCS, vol. 8781 (Springer, Cham, 2014), pp. 59–76
30.
J. Neyman, E.S. Pearson, On the problem of the most efficient tests of statistical hypotheses. Philos. Trans. R. Soc. Lond. Ser. A Containing Papers of a Mathematical or Physical Character 231, 289–337 (1933)
31.
T. Baignères, P. Junod, S. Vaudenay, How far can we go beyond linear cryptanalysis? in Lee, P.J. (ed.) ASIACRYPT 2004, Proceedings. LNCS, vol. 3329 (Springer, Berlin, Heidelberg, 2004), pp. 432–450
32.
C. Blondeau, B. Gérard, K. Nyberg, Multiple differential cryptanalysis using LLR and \(\chi \) 2 statistics, in Visconti, I., Prisco, R.D. (eds.) SCN 2012, Proceedings. LNCS, vol. 7485 (Springer, Berlin, Heidelberg, 2012), pp. 343–360
33.
B. Collard, F. Standaert, J. Quisquater, Improving the time complexity of Matsui’s linear cryptanalysis, in Nam, K., Rhee, G. (eds.) ICISC 2007, Proceedings. LNCS, vol. 4817 (Springer, Berlin, Heidelberg, 2007), pp. 77–88
34.
E. Biham, O. Dunkelman, N. Keller, Enhancing differential-linear cryptanalysis, in Zheng, Y. (ed.) ASIACRYPT 2002, Proceedings. LNCS, vol. 2501 (Springer, Berlin, Heidelberg, 2002), pp. 254–266
35.
A. Bar-On, O. Dunkelman, N. Keller, A. Weizman, DLCT: A new tool for differential-linear cryptanalysis, in Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Proceedings, Part I. LNCS, vol. 11476 (Springer, Cham, 2019), pp. 313–342
36.
S. Knellwolf, W. Meier, M. Naya-Plasencia, Conditional differential cryptanalysis of NLFSR-based cryptosystems, in Abe, M. (ed.) ASIACRYPT 2010, Proceedings. LNCS, vol. 6477 (Springer, Berlin, Heidelberg, 2010), pp. 130–145
37.
C. Blondeau, G. Leander, K. Nyberg, Differential-linear cryptanalysis revisited. J. Cryptol. 30(3), 859–888 (2017)MathSciNetCrossRef
38.
C. Carlet, Boolean Functions for Cryptography and Coding Theory (Cambridge University Press, Cambridge, 2021)MATH
39.
K. Nyberg, Linear approximation of block ciphers, in Santis, A.D. (ed.) EUROCRYPT 1994. LNCS, vol. 950 (Springer, Berlin, Heidelberg, 1994), pp. 439–444
40.
41.
Metadata
Title
Improved Differential-Linear Attacks with Applications to ARX Ciphers
Authors
Christof Beierle
Marek Broll
Federico Canale
Nicolas David
Antonio Flórez-Gutiérrez
Gregor Leander
María Naya-Plasencia
Yosuke Todo
Publication date
01-10-2022
Publisher
Springer US
Published in
Journal of Cryptology / Issue 4/2022
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-022-09437-z

Other articles of this Issue 4/2022

Journal of Cryptology 4/2022 Go to the issue

Research Article

ZK-PCPs from Leakage-Resilient Secret Sharing

Research Article

Breaking the Decisional Diffie–Hellman Problem for Class Group Actions Using Genus Theory: Extended Version

Research Article

On the (in)Security of ROS

Research Article

Efficient Perfectly Secure Computation with Optimal Resilience

Research Article

Signed (Group) Diffie–Hellman Key Exchange with Tight Security

Research Article

The Inverse of and Its Applications to Rasta-Like Ciphers

Premium Partner

    Image Credits