[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Multivariate correlation attacks and the cryptanalysis of LFSR-based stream ciphers

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

Cryptanalysis of modern symmetric ciphers may be done by using linear equation systems with multiple right hand sides, which describe the encryption process. The tool was introduced by Raddum and Semaev (Des Codes Cryptogr 49(1):147–160, 2008) where several solving methods were developed. In this work, the probabilities are ascribed to the right hand sides and a statistical attack is then applied. The new approach is a multivariate generalisation of the correlation attack by Siegenthaler (IEEE Trans Comput C 49(1):81–85, 1985). A fast version of the attack is provided too. It may be viewed as an extension of the fast correlation attack in Meier and Staffelbach (J Cryptol 1(3):159–176, 1989), based on exploiting so called parity-checks for linear recurrences. Parity-checks are a particular case of the relations that we introduce in the present work. The notion of a relation is irrelevant to linear recurrences. We show how to apply the method to some LFSR-based stream ciphers including those from the Grain family. The new method generally requires a lower number of the keystream bits to recover the initial states than other techniques reported in the literature.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Data availability

The datasets generated during the current study are not publicly available due to their large size, but are available from the corresponding author on reasonable request.

Notes

  1. It is not necessary for the polynomial to be primitive, however, when it is, the LFSR sequence has maximum period \(2^n - 1\) on a non-zero initial state.

References

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

    Article  Google Scholar 

  2. Ågren M., Löndahl C., Hell M., Johansson T.: A survey on fast correlation attacks. Cryptogr. Commun. 4(3), 173–202 (2012).

    Article  MathSciNet  Google Scholar 

  3. Anderson R.: Searching for the optimum correlation attack. In: Preneel B. (ed.) Fast Software Encryption, vol. 1008, pp. 137–143. Lecture Notes in Computer Science. Springer, Berlin (1995).

  4. Billingsley P.: Probability and Measure, 3rd edn. Wiley Series in Probability and Statistics. Wiley, New York (1995).

  5. Biryukov A., Shamir A.: Cryptanalytic time/memory/data tradeoffs for stream ciphers. In: Okamoto T. (ed.) Advances in Cryptology—ASIACRYPT 2000, vol. 1976, pp. 1–13. Lecture Notes in Computer Science. Springer, Berlin (2000).

  6. Canteaut A., Trabbia M.: Improved fast correlation attacks using parity-check equations of weight 4 and 5. In: Preneel B. (ed.) Advances in Cryptology—EUROCRYPT 2000, vol. 1807, pp. 573–588. Lecture Notes in Computer Science. Springer, Berlin (2000).

  7. Carlet C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2021).

    Google Scholar 

  8. Chepyzhov V., Johansson T., Smeets B.: A simple algorithm for fast correlation attacks on stream ciphers. In: Goos G., Hartmanis J., Leeuwen J., Schneier B. (eds.) Fast Software Encryption, vol. 1978, pp. 181–195. Lecture Notes in Computer Science. Springer, Berlin (2001).

  9. Chose P., Joux A., Mitton M.: Fast correlation attacks: an algorithmic point of view. In: Knudsen L. (ed.) Advances in Cryptology—EUROCRYPT 2002, vol. 2332, pp. 209–221. Lecture Notes in Computer Science. Springer, Berlin (2002).

  10. Courtois N., Meier W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham E. (ed.) Advances in Cryptology—EUROCRYPT 2003, vol. 2656, pp. 345–359. Lecture Notes in Computer Science. Springer, Berlin (2003).

  11. Courtois N.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh D. (ed.) Advances in Cryptology—CRYPTO 2003, vol. 2729, pp. 176–194. Lecture Notes in Computer Science. Springer, Berlin (2003).

  12. Didier F.: Attacking the filter generator by finding zero inputs of the filtering function. In: Srinathan K., Pandu Rangan C., Yung M. (eds.) Progress in Cryptology—INDOCRYPT 2007, vol. 4859, pp. 404–413. Lecture Notes in Computer Science. Springer, Berlin (2007).

  13. Ekdahl P., Maximov A., Johansson T., Yang J.: SNOW-Vi: an extreme performance variant of SNOW-V for lower grade CPUs. In: Pöpper C., Vanhoef M., Batina L., Mayrhofer R. (eds.) WiSec ’21, pp. 261–272. Association for Computing Machinery, New York (2021).

  14. Ekdahl P., Johansson T., Maximov A., Yang J.: A new SNOW stream cipher called SNOW-V. IACR Trans. Symm. Cryptol. 2019(3), 1–42 (2019).

    Google Scholar 

  15. Fauskanger S., Semaev I.: Separable statistics and multidimensional linear cryptanalysis. IACR Tran. Symm. Cryptol. 2018(2), 79–110 (2018).

    Article  Google Scholar 

  16. Golić J.D., Morgari G.: Vectorial fast correlation attacks. Cryptology. ePrint Archive, Paper 2004/247 (2004). https://eprint.iacr.org/2004/247.

  17. Golić J.D.: On the security of nonlinear filter generators. In: Gollmann D. (ed.) Fast Software Encryption, vol. 1039, pp. 173–188. Lecture Notes Computer Science. Springer, Berlin (1996).

  18. Golić J.D., Clark A., Dwason E.: Generalized inversion attack on nonlinear filter generators. IEEE Trans. Comput. 49(10), 1100–1109 (2000).

    Article  Google Scholar 

  19. Golić J.D., Hawkes P.: Vectorial approach to fast correlation attacks. Des. Codes Cryptogr. 35(1), 5–19 (2005).

    Article  MathSciNet  Google Scholar 

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

  21. Hell M., Johansson T., Maximov A., Meier W.: In: Robshaw, M., Billet, O. (eds.) The Grain Family of Stream Ciphers. Lecture Notes in Computer Science, vol. 4986, pp. 179–190. Springer, Berlin (2008).

  22. Hell M., Johansson T., Meier W.: Grain: a stream cipher for constrained environments. Int. J. Wirel. Mobile Comput. 2(1), 86–93 (2007).

    Article  Google Scholar 

  23. Johansson T., Jönsson F.: Fast correlation attacks based on turbo code techniques. In: Wiener M. (ed.) Advances in Cryptology—CRYPTO ’99, vol. 1666, pp. 181–197. Lecture Notes in Computer Science. Springer, Berlin (1999).

  24. Johansson T., Jönsson F.: Fast correlation attacks through reconstruction of linear polynomials. In: Bellare M. (ed.) Advances in Cryptology—CRYPTO 2000, vol. 1880, pp. 300–315. Lecture Notes in Computer Science. Springer, Berlin (2000).

  25. Johansson T., Jönsson F.: Improved fast correlation attacks on stream ciphers via convolutional codes. In: Stern J. (ed.) Advances in Cryptology—EUROCRYPT ’99, vol. 1592, pp. 347–362. Lecture Notes in Computer Science. Springer, Berlin (1999).

  26. Lenstra A., Lenstra H., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982).

    Article  MathSciNet  Google Scholar 

  27. Leveiller S., Boutros J., Guillot P., Zémor G.: Cryptanalysis of nonlinear filter generators with \(\{0, 1\}\)-metric Viterbi decoding. In: Honary B. (ed.) Cryptography and Coding, vol. 2260, pp. 402–414. Lecture Notes in Computer Science. Springer, Berlin (2001).

  28. Leveiller S., Zémor G., Guillot P., Boutros J.: A new cryptanalytic attack for PN-generators filtered by a Boolean function. In: Nyberg K., Heys H. (eds.) Selected Areas in Cryptography, vol. 2595, pp. 232–249. Lecture Notes in Computer Science. Springer, Berlin (2003).

  29. Meier W., Staffelbach O.: Nonlinearity criteria for cryptographic functions. In: Quisquater J.-J., Vandewalle J. (eds.) Advances in Cryptology—EUROCRYPT ’89, vol. 434, pp. 549–562. Lecture Notes in Computer Science. Springer, Berlin (1990).

  30. Meier W.: Fast correlation attacks: methods and countermeasures. In: Joux, A. (ed.) Fast Software Encryption, vol. 6733, pp. 55–67. Lecture Notes in Computer Science. Springer, Berlin (2011).

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

    Article  MathSciNet  Google Scholar 

  32. Mihaljević M., Fossorier M., Imai H.: Fast correlation attack algorithm with list decoding and an application. In: Matsui M. (ed.) Fast Software Encryption, vol. 2355, pp. 196–210. Lecture Notes in Computer Science. Springer, Berlin (2002).

  33. Molland H., Mathiassen J.E., Helleseth T.: Improved fast correlation attack using low rate codes. In: Paterson K. (ed.) Cryptography and Coding, vol. 2898, pp. 67–81. Lecture Notes in Computer Science. Springer, Berlin (2003).

  34. R Core Team: R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna (2021). https://www.R-project.org.

  35. Raddum H., Semaev I.: Solving multiple right hand sides linear equations. Des. Codes Cryptogr. 49(1), 147–160 (2008).

    Article  MathSciNet  Google Scholar 

  36. Shi Z., Jin C., Zhang J., Cui T., Ding L., Jin Y.: A correlation attack on full SNOW-V and SNOW-Vi. In: Dunkelman O., Dziembowski S. (eds.) Advances in Cryptology—EUROCRYPT 2022, vol. 13277, pp. 34–56. Lecture Notes in Computer Science. Springer, Berlin (2022).

  37. Siegenthaler T.: Decrypting a class of stream ciphers using ciphertext only. IEEE Trans. Comput. C 49(1), 81–85 (1985).

    Article  Google Scholar 

  38. Todo Y., Isobe T., Meier W., Aoki K., Zhang B.: Fast correlation attack revisited. In: Shacham H., Boldyreva A. (eds.) Advances in Cryptology—CRYPTO 2018, vol. 10992, pp. 129–159. Lecture Notes in Computer Science. Springer, Berlin (2018).

  39. Zhou Z., Feng D., Zhang B.: Vectorial decoding algorithm for fast correlation attack and its applications to stream cipher Grain-128a. IACR Trans. Symm. Cryptol. 2022(2), 322–350 (2022).

    Article  Google Scholar 

Download references

Acknowledgements

Some computations for the various experiments were performed on resources provided by UNINETT Sigma2 - the National Infrastructure for High Performance Computing and Data Storage in Norway.

Author information

Authors and Affiliations

  1. Cryptography Research Centre, Technology Innovation Institute, Abu Dhabi, United Arab Emirates

    Isaac A. Canales-Martínez

  2. Department of Informatics, University of Bergen, Bergen, Norway

    Igor Semaev

Authors
  1. Isaac A. Canales-Martínez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Igor Semaev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Isaac A. Canales-Martínez or Igor Semaev.

Ethics declarations

Competing interests

The authors have no competing interests to declare that are relevant to the content of this article.

Additional information

Communicated by C. Mitchell.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A: Toy example

Appendix A: Toy example

1.1 A.1  Application of the new method

Here we illustrate the idea of the new method by applying it to a small device. Let the keystream \(z_1,\dots ,z_{11} = 1,0,1,0,0,0,0,0,0,1,0\) be produced by a filter generator where \(g(x) = x^7 + x^5 + x^2 + x + 1\), \(f(x_1, x_2, x_3) = x_1 + x_1x_2 + x_2x_3\) and \((k_1, k_2, k_3) = (0, 2, 5)\). We will find its initial state X. We have

$$\begin{aligned} M = \begin{pmatrix} 0 &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 \\ 1 &{} 1 &{} 1 &{} 0 &{} 0 &{} 1 &{} 0 \end{pmatrix} \qquad \text {and} \qquad \Lambda = \begin{pmatrix} 1 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 0 \end{pmatrix}. \end{aligned}$$

Then the matrices \(A_i = \Lambda M^{i-1}\), \(i = 1, \dots , 11\) are

$$\begin{aligned} A_1 = \begin{pmatrix} 1 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 0 \end{pmatrix},{} & {} A_2 = \begin{pmatrix} 0 &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 \end{pmatrix},{} & {} A_3 = \begin{pmatrix} 0 &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 0 &{} 0 \\ 1 &{} 1 &{} 1 &{} 0 &{} 0 &{} 1 &{} 0 \end{pmatrix}, \\ A_4 = \begin{pmatrix} 0 &{} 0 &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 1 &{} 1 &{} 1 &{} 0 &{} 0 &{} 1 \end{pmatrix},{} & {} A_5 = \begin{pmatrix} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 \\ 1 &{} 1 &{} 0 &{} 1 &{} 1 &{} 1 &{} 0 \end{pmatrix},{} & {} A_6 = \begin{pmatrix} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 0 \\ 1 &{} 1 &{} 1 &{} 0 &{} 0 &{} 1 &{} 0 \\ 0 &{} 1 &{} 1 &{} 0 &{} 1 &{} 1 &{} 1 \end{pmatrix}, \\ A_7 = \begin{pmatrix} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 \\ 0 &{} 1 &{} 1 &{} 1 &{} 0 &{} 0 &{} 1 \\ 1 &{} 1 &{} 0 &{} 1 &{} 0 &{} 0 &{} 1 \end{pmatrix},{} & {} A_8 = \begin{pmatrix} 1 &{} 1 &{} 1 &{} 0 &{} 0 &{} 1 &{} 0 \\ 1 &{} 1 &{} 0 &{} 1 &{} 1 &{} 1 &{} 0 \\ 1 &{} 0 &{} 0 &{} 0 &{} 1 &{} 1 &{} 0 \end{pmatrix},{} & {} A_9 = \begin{pmatrix} 0 &{} 1 &{} 1 &{} 1 &{} 0 &{} 0 &{} 1 \\ 0 &{} 1 &{} 1 &{} 0 &{} 1 &{} 1 &{} 1 \\ 0 &{} 1 &{} 0 &{} 0 &{} 0 &{} 1 &{} 1 \end{pmatrix}, \\ A_{10} = \begin{pmatrix} 1 &{} 1 &{} 0 &{} 1 &{} 1 &{} 1 &{} 0 \\ 1 &{} 1 &{} 0 &{} 1 &{} 0 &{} 0 &{} 1 \\ 1 &{} 1 &{} 0 &{} 0 &{} 0 &{} 1 &{} 1 \end{pmatrix},{} & {} A_{11} = \begin{pmatrix} 0 &{} 1 &{} 1 &{} 0 &{} 1 &{} 1 &{} 1 \\ 1 &{} 0 &{} 0 &{} 0 &{} 1 &{} 1 &{} 0 \\ 1 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 1 \end{pmatrix}. \end{aligned}$$

The truth table of f is in Table 9. The distributions \(P_{(0)} = (1/4,1/4,1/4,0,0,0,1/4,0)\) and \(P_{(1)} = (0,0,0,1/4,1/4,1/4,0,1/4)\) correspond to \(f(a) = 0\) and \(f(a) = 1\), respectively. Hence, the distributions of the random variables \(X_i\) are \(P_i = P_{(0)}\), for \(i=2,4,5,6,7,8,9,11\), and \(P_i = P_{(1)}\), for \(i=1,3,10\). That defines the system (4).

Table 9 Truth table of \(f(x_1, x_2, x_3) = x_1 + x_1x_2 + x_2x_3\)
Full size table

Let the matrices \(B_r,\) \(r=1,\dots ,7\), be obtained by taking the first r rows of

$$\begin{aligned} B = \begin{pmatrix} 0&{}0&{}0&{}0&{}1&{}0&{}1 \\ 1&{}0&{}1&{}0&{}0&{}0&{}0 \\ 0&{}1&{}0&{}1&{}0&{}0&{}0 \\ 1&{}1&{}1&{}0&{}0&{}0&{}0 \\ 1&{}1&{}1&{}0&{}0&{}0&{}1 \\ 0&{}0&{}0&{}0&{}1&{}1&{}1 \\ 0&{}0&{}1&{}0&{}1&{}0&{}0 \end{pmatrix}. \end{aligned}$$

We will use short relations of weight \(d = 2\). To show the idea of relations, let us consider \(B_3\) and \(I = \{1,2\}\): we have that \(\langle A_1,A_2 \rangle \cap \langle B_3 \rangle =\langle T_{3\,I}B_3 \rangle \), where \(T_{3\,I}=\begin{pmatrix} 0 &{} 1 &{} 0 \\ 0 &{} 0 &{} 1 \end{pmatrix}\) and therefore \(t_{3\,I}=2\). We define the sets

$$\begin{aligned} {\mathcal {I}}_1&= \left\{ \{5,7\}, \{1,5\} \right\} , \\ {\mathcal {I}}_2&= \left\{ \{1,6\}, \{1,7\}, \{2,5\} \right\} , \\ {\mathcal {I}}_3&= \left\{ \{8,10\}, \{2,11\}, \{3,7\}, \{4,8\} \right\} , \\ {\mathcal {I}}_4&= \left\{ \{2,4\}, \{4,6\}, \{2,6\}, \{2,7\}, \{2,10\} \right\} , \\ {\mathcal {I}}_5&= \left\{ \{5,11\}, \{1,2\}, \{2,9\}, \{7,11\}, \{6,7\}, \{1,11\}, \{4,5\}, \{10,11\}, \{1,8\}, \{5,8\} \right\} , \\ {\mathcal {I}}_6&= \left\{ \{1,10\}, \{3,4\}, \{5,9\}, \{8,11\}, \{4,10\}, \{3,6\}, \{3,9\} \right\} , \\ {\mathcal {I}}_7&= \left\{ \{8,9\} \right\} , \end{aligned}$$

and compute the probability distribution of those relations. We set the success probability \(\beta =0.9\) and get the thresholds

$$\begin{aligned} (c_1, \dots , c_7) = (-2.8344, -8.8069, -15.4057, -17.0976, -39.5219, -28.2609, -4.0000). \end{aligned}$$

The applcation of the tree search yielded a unique candidate solution \(b = (0,0,1,0,0,1,1)^T\); the tree traversal is depicted in Figure 7. Solving the linear system \(B_7X = b\) yields \(X = (1,0,1,1,0,1,0)^T\), which is the correct initial state.

Fig. 7
figure 7

Tree traversal for the toy example. Filled nodes represent the survivor nodes. Non-filled nodes represent rejected nodes whose branch is not traversed

Full size image

We also applied the hybrid approach with \(r_0 = 3\). Since this is a small example, we used all the available relations modulo \(B_3\) for the given keystream to compute the statistic at that level:

$$\begin{aligned} {\mathcal {I}} = \left\{ \begin{array}{l} \{1,2\}, \{1,3\}, \{1,5\}, \{1,6\}, \{1,7\}, \{1,8\}, \{1,9\}, \{1,10\}, \{1,11\}, \\ \{2,3\}, \{2,4\}, \{2,5\}, \{2,6\}, \{2,7\}, \{2,9\}, \{2,10\}, \{2,11\}, \{3,4\}, \\ \{3,6\}, \{3,7\}, \{3,9\}, \{3,10\}, \{3,11\}, \{4,5\}, \{4,6\}, \{4,8\}, \{4,10\}, \\ \{4,11\}, \{5,6\}, \{5,7\}, \{5,8\}, \{5,9\}, \{5,11\}, \{6,7\}, \{6,10\}, \{7,8\}, \\ \{7,9\}, \{7,10\}, \{7,11\}, \{8,9\}, \{8,10\}, \{8,11\}, \{9,10\}, \{9,11\}, \{10,11\} \end{array}\right\} . \end{aligned}$$

After applying the FFT at level 3, the candidates were sorted as follows according to the value of the statistic:

$$\begin{aligned} (0,1,0), \quad (1,1,0), \quad (1,1,1), \quad (0,1,1), \quad (0,0,1), \quad (1,0,0), \quad (0,0,0), \quad (1,0,1). \end{aligned}$$

Neither of the first four candidates survived at level 4. The fifth candidate is the one corresponding to the correct initial state, which was recovered, and the tree search stopped at this point. The complexity of the hybrid method is defined by the FFT. Due to the size of this example, the hybrid approach is the worst. For bigger instances, however, the hybrid approach yields the best results (e.g., the results in Sect. 8.2).

1.2 A.2  Constructing \(B_r\) and relations

We now illustrate the principles in Sect. 8.1 (i.e., how to obtain the matrices \(B_r\) and the sets \({\mathcal {I}}_r\)) for the toy example.

  • The matrix \(B = B_7\) is constructed by randomly taking vectors from \((1,1,0)A_i\), where \(x_1+x_2\) is a good linear approximation to f.

  • The 45 weight-2 relations modulo \(B_3\) in the set \({\mathcal {I}}\) were found using the method in Sect. 4.1. As explained at the beginning of Sect. 6, they can be seen as relations modulo \(B_r\) for \(r = 1,\dots ,7\). Some \(I,J \in {\mathcal {I}}\) taken modulo \(B_r\) may be equivalent for some values of r and not equivalent for others. For example, \(I=\{1, 2\}\) and \(J=\{1, 8\}\). When \(r=1\) we have

    $$\begin{aligned}\begin{pmatrix} 0 \end{pmatrix} B_1 = \begin{pmatrix} 0&0&0 \end{pmatrix} A_1 + \begin{pmatrix} 0&0&0 \end{pmatrix} A_2, \quad \begin{pmatrix} 0 \end{pmatrix} B_1 = \begin{pmatrix} 0&0&0 \end{pmatrix} A_1 + \begin{pmatrix} 0&0&0 \end{pmatrix} A_8.\end{aligned}$$

    When \(r=2\) we have

    $$\begin{aligned}\begin{pmatrix} 0&1 \end{pmatrix} B_2 = \begin{pmatrix} 1&1&0 \end{pmatrix} A_1 + \begin{pmatrix} 0&0&0 \end{pmatrix} A_2, \quad \begin{pmatrix} 0&1 \end{pmatrix} B_2 = \begin{pmatrix} 1&1&0 \end{pmatrix} A_1 + \begin{pmatrix} 0&0&0 \end{pmatrix} A_8.\end{aligned}$$

    Finally, when \(r=3\) we get

    $$\begin{aligned} \begin{pmatrix} 0&{}1&{}0 \\ 0&{}0&{}1 \end{pmatrix} B_3 = \begin{pmatrix} 1&{}1&{}0 \\ 0&{}0&{}0 \end{pmatrix} A_1 + \begin{pmatrix} 0&{}0&{}0 \\ 1&{}1&{}0 \end{pmatrix} A_2, \quad \begin{pmatrix} 0&{}1&{}0 \\ 0&{}0&{}1 \end{pmatrix} B_3 = \begin{pmatrix} 1&{}1&{}0 \\ 0&{}0&{}0 \end{pmatrix} A_1 + \begin{pmatrix} 0&{}0&{}0 \\ 0&{}1&{}1 \end{pmatrix} A_8. \end{aligned}$$

    No indices in I or J are relevant modulo \(B_1\) and the only relevant index of I and J at level 2 is 1, so they are equivalent modulo \(B_1\) and \(B_2\). They are no longer equivalent modulo \(B_r\), \(r\ge 3\), since their set of relevant indices are distinct.

  • The sets \({\mathcal {I}}_r\), \(r=1,\dots ,7\), are disjoint, though not all relations within one set \({\mathcal {I}}_r\) are pairwise disjoint.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Canales-Martínez, I.A., Semaev, I. Multivariate correlation attacks and the cryptanalysis of LFSR-based stream ciphers. Des. Codes Cryptogr. 92, 3391–3427 (2024). https://doi.org/10.1007/s10623-024-01444-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-024-01444-4

Keywords

Mathematics Subject Classification

Search

Navigation