Correlation attacks on combination generators. (English) Zbl 1267.68110
Summary: The combination generator is a popular stream cipher construction. It consists of several independent devices working in parallel whose outputs are combined by a Boolean function. The output of this function is the keystream. The security of this generator has been extensively studied in the case where the devices are LFSRs. Some particular cases where the devices are nonlinear have also been studied, most notably the different versions of the eSTREAM proposal named Achterbahn. Several cryptanalysis techniques against these ciphers have been published, extending the classical correlation attack. But each of these attacks has been presented mainly in a very particular scenario. Therefore, this paper aims at generalising these methods to any combination generator in order to be able to compare their respective advantages and to determine the optimal attack for each particular generator. Generic formulas for the data-time-space complexities are then provided, which only depend on the number of devices, their periods and the number of their internal states and of the Boolean combining function. Some of the considered improvements can also be used in a much more general context, which includes linear attacks against some block ciphers.
Software:
eSTREAMReferences:
| [1] | Biryukov, A., De Cannière, C., Quisquater, M.: On multiple linear approximations. In: Advances in Cryptology–CRYPTO 2004. Lecture Notes in Computer Science, vol. 3152, pp. 1–22. Springer, Heidelberg (2004) · Zbl 1104.94018 |
| [2] | Blahut, R.E.: Fast Algorithms for Digital Signal Processing. Addison Wesley (1985) · Zbl 0579.94001 |
| [3] | Canteaut, A., Filiol, E.: Ciphertext only reconstruction of stream ciphers based on combination generators. In: Fast Software Encryption–FSE 2000. Lecture Notes in Computer Science, vol. 1978, pp. 165–180. Springer-Verlag (2001) · Zbl 0999.94543 |
| [4] | Canteaut, A., Naya-Plasencia, M.: Parity-check relations on combination generators. IEEE Trans. Inf. Theory 58(6), 3900–3911 (2012) · Zbl 1267.68110 · doi:10.1109/TIT.2012.2184736 |
| [5] | Canteaut, A., Trabbia, M.: Improved fast correlation attacks using parity-check equations of weight 4 and 5. In: Advances in Cryptology–EUROCRYPT 2000. Lecture Notes in Computer Science, vol. 1807, pp. 573–588. Springer-Verlag (2000) · Zbl 1082.94509 |
| [6] | Chepyshov, V., Johansson, T., Smeets, B.: A simple algorithm for fast correlation attacks on stream ciphers. In: Fast Software Encryption–FSE 2000, Lecture Notes in Computer Science, vol. 1978, pp. 124–135. Springer-Verlag (2000) |
| [7] | Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: an algorithmic point of view. In: Advances in Cryptology–EUROCRYPT 2002. Lecture Notes in Computer Science, vol. 2332, pp. 209–221. Springer-Verlag (2002) · Zbl 1055.94010 |
| [8] | Coppersmith, D., Halevi, S., Jutla, C.: Cryptanalysis of stream ciphers with linear masking. In: Advances in Cryptology–CRYPTO 2002. Lecture Notes in Computer Science, vol. 2442. Springer-Verlag (2002) · Zbl 1026.94525 |
| [9] | Courtois, N.: Fast algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology–CRYPTO 2003. Lecture Notes in Computer Science, vol. 2729, pp. 176–194. Springer-Verlag (2003) · Zbl 1122.94365 |
| [10] | Courtois, N., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology–EUROCRYPT 2003. Lecture Notes in Computer Science, vol. 2656, pp. 345–359. Springer-Verlag (2003) · Zbl 1038.94525 |
| [11] | ECRYPT–European Network of Excellence in Cryptology: The eSTREAM Stream Cipher Project. http://www.ecrypt.eu.org/stream/ (2004) |
| [12] | Ekdahl, P., Johansson, T.: Distinguishing attacks on SOBER-t16 and t32. In: Fast Software Encryption–FSE 2002. LNCS, vol. 2365, pp. 210–224. Springer (2002) · Zbl 1045.94518 |
| [13] | Gammel, B., Göttfert, R., Kniffler, O.: The Achterbahn stream cipher. Submission to eSTREAM. http://www.ecrypt.eu.org/stream/ (2005) |
| [14] | Gammel, B., Göttfert, R., Kniffler, O.: Achterbahn-128/80. Submission to eSTREAM. http://www.ecrypt.eu.org/stream/ (2006) |
| [15] | Gammel, B., Göttfert, R., Kniffler, O.: Status of Achterbahn and Tweaks. In: Proceedings of SASC 2006–Stream Ciphers Revisited. http://www.ecrypt.eu.org/stream/papersdir/2006/027.pdf (2006) |
| [16] | Gammel, B., Göttfert, R., Kniffler, O.: Achterbahn-128/80: design and analysis. In: Proceedings of SASC 2007–Stream Ciphers Revisited. http://www.ecrypt.eu.org/stream/papersdir/2007/020.pdf (2007) |
| [17] | Gérard, B., Tillich, J.P.: On linear cryptanalysis with many linear approximations. In: IMA International Conference, Cryptography and Coding. Lecture Notes in Computer Science, vol. 5921, pp. 112–132. Springer (2009) · Zbl 1234.94041 |
| [18] | Gérard, B., Tillich, J.P.: Advanced Linear Cryptanalysis of Block and Stream Ciphers, vol. 7, chap. Using Tools from Error Correcting Theory in Linear Cryptanalysis, pp. 87–114. IOS Press (2011) · Zbl 1293.94067 |
| [19] | Göttfert, R., Gammel, B.: On the frame length of Achterbahn-128/80. In: Proceedings of the 2007 IEEE Information Theory Workshop on Information Theory for Wireless Networks, pp. 1–5. IEEE (2007) |
| [20] | Hell, M., Johansson, T.: Cryptanalysis of Achterbahn-Version 2. In: Selected Areas in Cryptography–SAC 2006. Lecture Notes in Computer Science, vol. 4356, pp. 45–55. Springer (2006) · Zbl 1161.94405 |
| [21] | Hell, M., Johansson, T.: Cryptanalysis of Achterbahn-128/80. IET Inf. Secur. 1(2), 47–52 (2007) · Zbl 1161.94405 · doi:10.1049/iet-ifs:20060153 |
| [22] | Hell, M., Johansson, T., Brynielsson, L.: An overview of distinguishing attacks on stream ciphers. Cryptogr. Commun. 1(1), 71–94 (2009) · Zbl 1178.94189 · doi:10.1007/s12095-008-0006-7 |
| [23] | Hermelin, M., Cho, J., Nyberg, K.: Multidimensional extension of Matsui’s Algorithm 2. In: Fast Software Encryption–FSE 2009. Lecture Notes in Computer Science, vol. 5665, pp. 209–227. Springer (2009) · Zbl 1248.94068 |
| [24] | Hermelin, M., Nyberg, K.: Advanced Linear Cryptanalysis of Block and Stream Ciphers, vol. 7, chap. Linear Cryptanalysis Using Multiple Linear Approximations, pp. 25–54. IOS Press (2011) |
| [25] | Johansson, T., Jönsson, F.: Fast correlation attacks based on turbo code techniques. In: Advances in Cryptology–CRYPTO’99. Lecture Notes in Computer Science, vol. 1666, pp. 181–197. Springer-Verlag (1999) · Zbl 0954.94008 |
| [26] | Johansson, T., Jönsson, F.: Improved fast correlation attack on stream ciphers via convolutional codes. In: Advances in Cryptology–EUROCRYPT’99. Lecture Notes in Computer Science, vol. 1592, pp. 347–362. Springer-Verlag (1999) · Zbl 0931.94027 |
| [27] | Johansson, T., Jönsson, F.: Fast correlation attacks through reconstruction of linear polynomials. In: Advances in Cryptology–CRYPTO’00. Lecture Notes in Computer Science, vol. 1880, pp. 300–315. Springer-Verlag (2000) · Zbl 0995.94523 |
| [28] | Johansson, T., Meier, W., Muller, F.: Cryptanalysis of Achterbahn. In: Fast Software Encryption–FSE 2006, Lecture Notes in Computer Science, vol. 4047, pp. 1–14. Springer (2006) · Zbl 1234.68091 |
| [29] | Joux, A.: Algorithmic Cryptanalysis. Chapman & Hall/CRC (2009) · Zbl 1172.94008 |
| [30] | Junod, P., Vaudenay, S.: Optimal key ranking procedures in a statistical cryptanalysis. In: Fast Software Encryption–FSE 2003. Lecture Notes in Computer Science, vol. 2887, pp. 235–246. Springer-Verlag (2003) · Zbl 1254.94036 |
| [31] | Lu, Y., Vaudenay, S.: Faster correlation attack on Bluetooth keystream generator E0. In: Advances in Cryptology–CRYPTO 2004. Lecture Notes in Computer Science, vol. 3152, pp. 407–425. Springer-Verlag (2004) · Zbl 1104.94311 |
| [32] | Matsui, M.: The first experimental cryptanalysis of the data encryption standard. In: Advances in Cryptology–CRYPTO’94. Lecture Notes in Computer Science, vol. 839. Springer-Verlag (1995) |
| [33] | Meier, W., Staffelbach, O.: Fast correlation attacks on stream ciphers. In: Advances in Cryptology–EUROCRYPT’88. Lecture Notes in Computer Science, vol. 330, pp. 301–314. Springer-Verlag (1988) |
| [34] | Meier, W., Staffelbach, O.: Fast correlation attack on certain stream ciphers. J. Cryptol. 1(3), 159–176 (1989) · Zbl 0673.94010 · doi:10.1007/BF02252874 |
| [35] | Naya-Plasencia, M.: Cryptanalysis of Achterbahn-128/80. In: Fast Software Encryption–FSE 2007. Lecture Notes in Computer Science, vol. 4593, pp. 73–86. Springer (2007) · Zbl 1186.94462 |
| [36] | Naya-Plasencia, M.: Cryptanalysis of Achterbahn-128/80 with a new keystream limitation. In: WEWoRC 2007–Second Western European Workshop in Research in Cryptology. Lecture Notes in Computer Science, vol. 4945, pp. 142–152. Springer (2008) · Zbl 1166.94321 |
| [37] | Siegenthaler, T.: Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Trans. Inf. Theory 30(5), 776–780 (1984) · Zbl 0554.94010 · doi:10.1109/TIT.1984.1056949 |
| [38] | Siegenthaler, T.: Decrypting a class of stream ciphers using ciphertext only. IEEE Trans. Comput. C-34(1), 81–84 (1985) · doi:10.1109/TC.1985.1676518 |
| [39] | Zhang, M.: Maximum correlation analysis of nonlinear combining functions in stream ciphers. J. Cryptol. 13(3), 301–313 (2000) · Zbl 1015.94007 · doi:10.1007/s001450010007 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
