Top

Published in:

2018 | OriginalPaper | Chapter

Fast Correlation Attack Revisited

Cryptanalysis on Full Grain-128a, Grain-128, and Grain-v1

Authors : Yosuke Todo, Takanori Isobe, Willi Meier, Kazumaro Aoki, Bin Zhang

Published in: Advances in Cryptology – CRYPTO 2018

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

A fast correlation attack (FCA) is a well-known cryptanalysis technique for LFSR-based stream ciphers. The correlation between the initial state of an LFSR and corresponding key stream is exploited, and the goal is to recover the initial state of the LFSR. In this paper, we revisit the FCA from a new point of view based on a finite field, and it brings a new property for the FCA when there are multiple linear approximations. Moreover, we propose a novel algorithm based on the new property, which enables us to reduce both time and data complexities. We finally apply this technique to the Grain family, which is a well-analyzed class of stream ciphers. There are three stream ciphers, Grain-128a, Grain-128, and Grain-v1 in the Grain family, and Grain-v1 is in the eSTREAM portfolio and Grain-128a is standardized by ISO/IEC. As a result, we break them all, and especially for Grain-128a, the cryptanalysis on its full version is reported for the first time.

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 Practical and Tightly-Secure Digital Signatures and Authenticated Key Exchange

next chapter A Key-Recovery Attack on 855-round Trivium

Grain-128a has two modes of operation: stream cipher mode and authenticated encryption mode. We can break the stream cipher mode under the known-plaintext setting. However we cannot attack the authenticated encryption mode under the reasonable assumption.

Accurately, when the correct initial state is guessed, it follows \(\mathcal{N}(Nc, N+Nc^2)\). However, since N is huge and \(N c^2\) is small, the normal distribution \(\mathcal{N}(Nc, N)\) is enough to approximate the distribution.

The correlation c is the lower bound for all \(\gamma _i\). Therefore, while the empirical correlation may not follow \(\mathcal{N}(Nc,N)\), it does not affect the attack feasibility because it is far from \(\mathcal{N}(0,N)\).

Since we only use \(N<2^n\) parity-check equations, it is enough to use additions or subtraction on n-bit registers.

Siegenthaler, T.: Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Trans. Inf. Theory 30(5), 776–780 (1984)MathSciNetCrossRef

Meier, W., Staffelbach, O.: Fast correlation attacks on certain stream ciphers. J. Cryptol. 1(3), 159–176 (1989)MathSciNetCrossRef

Zeng, K., Yang, C.H., Rao, T.R.N.: An improved linear syndrome algorithm in cryptanalysis with applications. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 34–47. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_3CrossRef

Mihaljevic, M.J., Golic, J.D.: A fast iterative algorithm for a shift register initial state reconstruction given the noisy output sequence. In: Seberry, J., Pieprzyk, J. (eds.) AUSCRYPT 1990. LNCS, vol. 453, pp. 165–175. Springer, Heidelberg (1990). https://doi.org/10.1007/BFb0030359CrossRef

Chepyzhov, V., Smeets, B.J.M.: On a fast correlation attack on certain stream ciphers. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 176–185. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_16CrossRef

Johansson, T., Jönsson, F.: Improved fast correlation attacks on stream ciphers via convolutional codes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 347–362. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_24CrossRef

Johansson, T., Jönsson, F.: Fast correlation attacks based on turbo code techniques. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 181–197. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_12CrossRef

Canteaut, A., Trabbia, M.: Improved fast correlation attacks using parity-check equations of weight 4 and 5. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 573–588. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_40CrossRef

Chepyzhov, V.V., Johansson, T., Smeets, B.J.M.: A simple algorithm for fast correlation attacks on stream ciphers. In: Goos, G., Hartmanis, J., van Leeuwen, J., Schneier, B. (eds.) FSE 2000. LNCS, vol. 1978, pp. 181–195. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44706-7_13CrossRefMATH

10.

Mihaljevi, M.J., Fossorier, M.P.C., Imai, H.: Fast correlation attack algorithm with list decoding and an application. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 196–210. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45473-X_17CrossRef

11.

Berbain, C., Gilbert, H., Maximov, A.: Cryptanalysis of Grain. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 15–29. Springer, Heidelberg (2006). https://doi.org/10.1007/11799313_2CrossRef

12.

Lee, J., Lee, D.H., Park, S.: Cryptanalysis of sosemanuk and SNOW 2.0 using linear masks. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 524–538. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89255-7_32CrossRef

13.

Zhang, B., Xu, C., Meier, W.: Fast correlation attacks over extension fields, large-unit linear approximation and cryptanalysis of SNOW 2.0. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 643–662. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_31CrossRef

14.

Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: an algorithmic point of view. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 209–221. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_14CrossRef

15.

Zhang, B., Feng, D.: Multi-pass fast correlation attack on stream ciphers. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 234–248. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74462-7_17CrossRef

16.

Wagner, D.A.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–304. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_19CrossRef

17.

Dinur, I., Güneysu, T., Paar, C., Shamir, A., Zimmermann, R.: An experimentally verified attack on full grain-128 using dedicated reconfigurable hardware. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 327–343. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_18CrossRef

18.

Fu, X., Wang, X., Chen, J.: Determining the nonexistent terms of non-linear multivariate polynomials: How to break Grain-128 more efficiently. IACR Cryptol. ePrint Archive 2017, 412 (2017)

19.

Zhang, B., Xu, C., Meier, W.: Fast near collision attack on the Grain v1 stream cipher. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part II. LNCS, vol. 10821, pp. 771–802. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_25CrossRef

20.

Ågren, M., Hell, M., Johansson, T., Meier, W.: Grain-128a: a new version of Grain-128 with optional authentication. IJWMC 5(1), 48–59 (2011)CrossRef

21.

Hell, M., Johansson, T., Maximov, A., Meier, W.: A stream cipher proposal: Grain-128. In: IEEE International Symposium on Information Theory (ISIT 2006). IEEE, pp. 1614–1618 (2006)

22.

Hell, M., Johansson, T., Meier, W.: Grain: a stream cipher for constrained environments. IJWMC 2(1), 86–93 (2007)CrossRef

23.

ISO/IEC: JTC1: ISO/IEC 29167–13: Information technology - automatic identification and data capture techniques - part 13: Crypto suite Grain-128A security services for air interface communications (2015)

24.

Aumasson, J., Henzen, L., Meier, W., Naya-Plasencia, M.: Quark: a lightweight hash. J. Cryptol. 26(2), 313–339 (2013)MathSciNetCrossRef

25.

Armknecht, F., Mikhalev, V.: On lightweight stream ciphers with shorter internal states. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 451–470. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48116-5_22CrossRef

26.

Mikhalev, V., Armknecht, F., Müller, C.: On ciphers that continuously access the non-volatile key. IACR Trans. Symmetric Cryptol. 2016(2), 52–79 (2016)

27.

Hell, M., Johansson, T., Meier, W.: Grain - a stream cipher for constrained environments (2005). http://www.ecrypt.eu.org/stream

28.

Zhang, B., Li, Z., Feng, D., Lin, D.: Near collision attack on the Grain v1 stream cipher. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 518–538. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43933-3_27CrossRef

29.

Dinur, I., Shamir, A.: Breaking Grain-128 with dynamic cube attacks. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 167–187. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21702-9_10CrossRef

30.

Lehmann, M., Meier, W.: Conditional differential cryptanalysis of Grain-128a. In: Pieprzyk, J., Sadeghi, A.-R., Manulis, M. (eds.) CANS 2012. LNCS, vol. 7712, pp. 1–11. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35404-5_1CrossRef

31.

Todo, Y., Isobe, T., Hao, Y., Meier, W.: Cube attacks on non-blackbox polynomials based on division property. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 250–279. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_9CrossRef

32.

Wang, Q., Hao, Y., Todo, Y., Li, C., Isobe, T., Meier, W.: Improved division property based cube attacks exploiting algebraic properties of superpoly. CRYPTO 2018, Accepted at CRYPTO 2018 (2018). http://eprint.iacr.org/2017/1063

33.

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

34.

Mouha, N., Wang, Q., Gu, D., Preneel, B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Wu, C.-K., Yung, M., Lin, D. (eds.) Inscrypt 2011. LNCS, vol. 7537, pp. 57–76. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34704-7_5CrossRefMATH

35.

Sun, S., Hu, L., Wang, P., Qiao, K., Ma, X., Song, L.: Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part I. LNCS, vol. 8873, pp. 158–178. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_9CrossRef

Title: Fast Correlation Attack Revisited
Authors: Yosuke Todo
Takanori Isobe
Willi Meier
Kazumaro Aoki
Bin Zhang
Publisher: Springer International Publishing
Book: Advances in Cryptology – CRYPTO 2018
Print ISBN: 978-3-319-96880-3

Electronic ISBN: 978-3-319-96881-0

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-96881-0_5

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