nach oben

Erschienen in:

2014 | OriginalPaper | Buchkapitel

Improved Differential Cryptanalysis of Round-Reduced Speck

verfasst von : Itai Dinur

Erschienen in: Selected Areas in Cryptography -- SAC 2014

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

Simon and Speck are families of lightweight block ciphers designed by the U.S. National Security Agency and published in 2013. Each of the families contains 10 variants, supporting a wide range of block and key sizes. Since the publication of Simon and Speck, several research papers analyzed their security using various cryptanalytic techniques. The best previously published attacks on all the 20 round-reduced ciphers are differential attacks, and are described in two papers (presented at FSE 2014) by Abed et al. and Biryukov et al.

In this paper, we focus on the software-optimized block cipher family Speck, and describe significantly improved attacks on all of its 10 variants. In particular, we increase the number of rounds which can be attacked by 1, 2, or 3, for 9 out of 10 round-reduced members of the family, while significantly improving the complexity of the previous best attack on the remaining round-reduced member. Our attacks use an untraditional key recovery technique for differential attacks, whose main ideas were published by Albrecht and Cid at FSE 2009 in the cryptanalysis of the block cipher PRESENT.

Despite our improved attacks, they do not seem to threaten the security of any member of Speck.

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 Security Amplification for the Composition of Block Ciphers: Simpler Proofs and New Results

Nächstes Kapitel Differential Cryptanalysis of SipHash

Nur mit Berechtigung zugänglich

Simon is a Feistel structure, while Speck can be represented as a composition of two Feistel maps [7].

Examples of sub-cipher attacks include the meet-in-the-middle and guess-and-determine attacks on round-reduced GOST, described in [12, 13].

We note that analysis of dependent round-keys can sometimes be performed efficiently using algebraic tools, as claimed in [2].

Recall that we have essentially no (linear) filtering conditions, and thus we must execute the sub-cipher attack for each encrypted input pair. Consequently, we are interested in the average time complexity of the algorithm.

Note that information theoretically, without considering the internal transitions of the differential characteristic, \(p \cdot 2^{2n-1}\) is the best improvement factor that one can hope for, given \(2\cdot p^{-1}\) data.

This step can be slightly optimized to replace many of the full trial encryptions by lighter Speck round evaluations, if we consider the internal transitions of the differential characteristic: while iteratively calculating \(k_{r-1},\ldots ,k_0\), we partially decrypt \(C\) and \(C'\), and verify that they satisfy the differential characteristic for each round. If the verification fails for some round, we discard the key and continue.

For example, assume that we want to solve the standard DEA over 16-bit words (given in hexadecimal) \((x \oplus 0000) \boxplus (y \oplus 0000) = (x \boxplus y) \oplus 8000\). If we solve the system from the LSB to the MSB, then we consider all \(2^{30}\) partial solutions to the 15 LSBs of \(x\) and \(y\), and then discard all of them at the MSB.

We note that after applying the filters, one can try to apply standard counting techniques to recover some key bits in few first rounds of Speck. However, as we can solve the full equation system and test each suggested key efficiently, the counting techniques are not likely to significantly improve the complexity of the attacks.

Abed, F., List, E., Wenzel, J., Lucks, S.: Differential Cryptanalysis of round-reduced Simon and Speck. Presented at FSE 2014. To Appear in Lecture Notes in Computer Science (2014)

Albrecht, M., Cid, C.: Algebraic techniques in differential cryptanalysis. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 193–208. Springer, Heidelberg (2009)CrossRef

Albrecht, M., Cid, C., Dullien, T., Faugère, J.-C., Perret, L.: Algebraic precomputations in differential and integral cryptanalysis. In: Lai, X., Yung, M., Lin, D. (eds.) Inscrypt 2010. LNCS, vol. 6584, pp. 387–403. Springer, Heidelberg (2011)CrossRef

Alizadeh, J., Bagheri, N., Gauravaram, P., Kumar, A., Sanadhya, S.K.: Linear cryptanalysis of round reduced SIMON. Cryptology ePrint Archive, Report 2013/663 (2013). http://eprint.iacr.org/

Alkhzaimi, H.A., Lauridsen, M.M.: Cryptanalysis of the SIMON family of block ciphers. Cryptology ePrint Archive, Report 2013/543 (2013). http://eprint.iacr.org/

Bar-On, A., Dinur, I., Dunkelman, O., Lallemand, V., Tsaban, B.: Improved analysis of Zorro-like ciphers. IACR Cryptology ePrint Archive (2014)

Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK families of lightweight block ciphers. Cryptology ePrint Archive, Report 2013/404 (2013). http://eprint.iacr.org/

Biham, E., Shamir, A.: Differential cryptanalysis of des-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991)MathSciNetCrossRefMATH

Biryukov, A., Roy, A., Velichkov, V.: Differential analysis of block ciphers SIMON and SPECK. Presented at FSE 2014. To Appear in Lecture Notes in Computer Science (2014)

10.

De Cannière, C., Rechberger, C.: Finding SHA-1 characteristics: general results and applications. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 1–20. Springer, Heidelberg (2006)CrossRef

11.

Dinur, I.: Improved differential cryptanalysis of round-reduced Speck. IACR Cryptology ePrint Archive (2014)

12.

Dinur, I., Dunkelman, O., Shamir, A.: Improved attacks on full GOST. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 9–28. Springer, Heidelberg (2012)CrossRef

13.

Isobe, T.: A single-key attack on the full GOST block cipher. J. Cryptol. 26(1), 172–189 (2013)MathSciNetCrossRefMATH

14.

Kara, O.: Reflection cryptanalysis of some ciphers. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 294–307. Springer, Heidelberg (2008)CrossRef

15.

Leurent, G.: Analysis of differential attacks in ARX constructions. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 226–243. Springer, Heidelberg (2012)CrossRef

16.

Leurent, G.: Construction of differential characteristics in ARX designs application to skein. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 241–258. Springer, Heidelberg (2013)CrossRef

17.

Lipmaa, H., Moriai, S.: Efficient algorithms for computing differential properties of addition. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 336–350. Springer, Heidelberg (2002)CrossRef

18.

Mendel, F., Nad, T., Schläffer, M.: Finding SHA-2 characteristics: searching through a minefield of contradictions. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 288–307. Springer, Heidelberg (2011)CrossRef

19.

Paul, S., Preneel, B.: Solving systems of differential equations of addition. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 75–88. Springer, Heidelberg (2005)CrossRef

20.

Stein, W.A., et al.: Sage Mathematics Software. The Sage Development Team. http://www.sagemath.org

21.

Tupsamudre, H., Bisht, S., Mukhopadhyay, D.: Differential fault analysis on the families of SIMON and SPECK ciphers. Cryptology ePrint Archive, Report 2014/267 (2014). http://eprint.iacr.org/

22.

Wang, M., Sun, Y., Mouha, N., Preneel, B.: Algebraic techniques in differential cryptanalysis revisited. In: Parampalli, U., Hawkes, P. (eds.) ACISP 2011. LNCS, vol. 6812, pp. 120–141. Springer, Heidelberg (2011)CrossRef

23.

Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005)CrossRef

Titel: Improved Differential Cryptanalysis of Round-Reduced Speck
verfasst von: Itai Dinur
Verlag: Springer International Publishing
Buch: Selected Areas in Cryptography -- SAC 2014
Print ISBN: 978-3-319-13050-7

Electronic ISBN: 978-3-319-13051-4

Copyright-Jahr: 2014
DOI: https://doi.org/10.1007/978-3-319-13051-4_9

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"