A survey on fast correlation attacks

详细信息    查看全文

• 作者：Martin 脜gren (1)
  Carl L枚ndahl (1)
  Martin Hell (1)
  Thomas Johansson (1) thomas@eit.lth.se
• 关键词：Fast correlation attacks &#8211 ; Stream ciphers &#8211 ; Cryptanalysis
• 刊名：Cryptography and Communications
• 出版年：2012
• 出版时间：December 2012
• 年：2012
• 卷：4
• 期：3-4
• 页码：173-202
• 全文大小：574.9 KB
• 参考文献：1. Bahl, L., Cocke, J., Jelinek, F., Raviv, J.: Optimal decoding of linear codes for minimizing symbol error rate. IEEE Trans. Inf. Theory 20(2), 284–287 (1974)
  2. Berrou, C., Glavieux, A.: Near optimum error correcting and decoding: turbo-codes. IEEE Trans. Commun. 4(10), 1261–1271 (1996)
  3. Berrou, C., Glavieux, A., Thitimajshima, P.: Near Shannon limit error-correcting coding and decoding. In: Proc., IEEE Int. Conf. on Communications, ICC’93, pp. 1064–1070 (1993)
  4. Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: Yao, F.F., Luks, E.M. (eds.) STOC, pp. 435–440. ACM (2000)
  5. Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4), 506–519 (2003)
  6. Canteaut, A., Filiol, E. (2002) On the influence of the filtering function on the performance of fast correlation attacks on filter generators. In: Symposium on Information Theory, pp. 299–306
  7. 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. Lecture Notes in Computer Science, vol. 1807, pp. 573–588. Springer-Verlag (2000)
  8. Chepyzhov, V., Johansson, T., Smeets, B.: A simple algorithm for fast correlation attacks on stream ciphers. In: Schneier, B. (ed.) Fast Software Encryption 2000. Lecture Notes in Computer Science, vol. 1978, pp. 181–195. Springer-Verlag (2000)
  9. Chepyzhov, V., Smeets, B.: On a fast correlation attack on certain stream ciphers. In: Davies, D.W. (ed.) Advances in Cryptology—EUROCRYPT’91. Lecture Notes in Computer Science, vol. 547, pp. 176–185. Springer-Verlag (1991)
  10. Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: An algorithmic point of view. Lect. Notes Comput. Sci. 2332, 209–221 (2002)
  11. Coppersmith, D.: Fast evaluation of logarithms in fields of characteristic two. IEEE Trans. Inf. Theory 30(4), 587–594 (1984)
  12. Fossorier, M.P.C., Mihaljevic, M.J., Imai, H.: Reduced complexity iterative decoding of low-density parity check codes based on belief propagation. IEEE Trans. Commun. 47, 673–680 (1999)
  13. Fossorier, M.P.C., Mihaljević, M.J., Imai, H.: Modeling block decoding approaches for the fast correlation attack. IEEE Trans. Inf. Theory 53(12), 4728–4737 (2007)
  14. Fossorier, M.P.C., Mihaljević, M.J. Imai, H., Cui, Y., Matsuura, K.: An algorithm for solving the LPN problem and its application to security evaluation of the HB protocols for RFID authentication. In: Barua, R., Lange, T. (eds.) Progress in Cryptology—INDOCRYPT 2005. Lecture Notes in Computer Science, vol. 4329, pp. 48–62. Springer-Verlag (2006)
  15. Gallager, R.G.: Low-density parity-check codes. IEEE Trans. Inf. Theory 8(1), 21–28 (1962)
  16. Gallager, R.G.: Low-Density Parity-Check Codes. PhD thesis, MIT Press, Cambridge (1963)
  17. Gilbert, E.N., MacWilliams, F.J., Sloane, N.J.A.: Codes which detect deception. Bell Syst. Tech. J. 53(3), 405–424 (1974)
  18. Goldreich, O., Rubinfeld, R., Sudan, M.: Learning polynomials with queries: the highly noisy case. In: 36th Annual Symposium on Foundation of Computer Science, pp. 294–303 (1995)
  19. Golić, J.Dj.: Computation of low-weight parity-check polynomials. Electron. Lett. 32(21), 1981–1982 (1996)
  20. Golić, J.Dj.: Iterative optimum symbol-by-symbol decoding and fast correlation attacks. IEEE Trans. Inf. Theory 47(7), 3040–3049 (2001)
  21. Hartmann, C.R.P., Rudolph, L.D.: An optimum symbol-by-symbol decoding rule for linear codes. IEEE Trans. Inf. Theory 22(5):514–517 (1976)
  22. Johansson, T., J枚nsson, F.: Fast correlation attacks based on turbo code techniques. In: Wiener, M.J. (ed.) Advances in Cryptology—CRYPTO’99. Lecture Notes in Computer Science, vol. 1666, pp. 181–197. Springer-Verlag (1999)
  23. Johansson, T., J枚nsson, F.: Improved fast correlation attacks on stream ciphers via convolutional codes. In: Stern, J. (ed.) Advances in Cryptology—EUROCRYPT’99. Lecture Notes in Computer Science, vol. 1592, pp. 347–362. Springer-Verlag (1999)
  24. Johansson, T., J枚nsson, F.: Fast correlation attacks through reconstruction of linear polynomials. In: Bellare, M. (ed.) Advances in Cryptology—CRYPTO 2000. Lecture Notes in Computer Science, vol. 1880, pp. 300–315. Springer-Verlag (2000)
  25. J枚nsson, F.: Some results on fast correlation attacks. PhD thesis, Lund University, Department of Information Technology, P.O. Box 118, SE–221 00, Lund, Sweden (2002)
  26. Levieil, 脡., Fouque, P.-A.: An improved LPN algorithm. In: De Prisco, R., Yung, M. (eds.) SCN. Lecture Notes in Computer Science, vol. 4116, pp. 348–359. Springer-Verlag (2006)
  27. Meier, W.: Fast correlation attacks: methods and countermeasures. In: Joux, A. (eds.) Fast Software Encryption 2011. Lecture Notes in Computer Science, pp. 55–67. Springer-Verlag (2011)
  28. Meier, W., Staffelbach, O.: Fast correlation attacks on certain stream ciphers. J. Cryptol. 1(3), 159–176 (1989)
  29. Mihaljević, M.J., Fossorier, M., Imai, H.: A low-complexity and high-performance algorithm for the fast correlation attack. In: Schneier, B. (ed.) Fast Software Encryption 2000. Lecture Notes in Computer Science, vol. 1978, pp. 196–212. Springer-Verlag (2000)
  30. Mihaljević, M.J., Fossorier, M., Imai, H.: On decoding techniques for cryptanalysis of certain encryption algorithms. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E84-A, 919–930 (2001)
  31. Mihaljević, M.J., Fossorier, M., Imai, H.: Fast correlation attack algorithm with list decoding and an application. In: Fast Software Encryption 2001. Lecture Notes in Computer Science, vol. 2355, pp. 196–210. Springer-Verlag (2002)
  32. Mihaljević, M.J., Golić, J.D.: A fast iterative algorithm for a shift register initial state reconstruction given the noisy output sequence. In: Seberry, J., Pieprzyk, J. (eds.) Advances in Cryptology—AUSCRYPT’90. Lecture Notes in Computer Science, vol. 453, pp. 165–175. Springer-Verlag (1990)
  33. Molland, H., Mathiassen, J., Helleseth, T.: Improved fast correlation attack using low rate codes. In: Paterson, K. (ed.) Cryptography and Coding—9th IMA Conference. Lecture Notes in Computer Science, vol. 2898, pp. 67–81. Springer Berlin/Heidelberg (2003)
  34. Noorkami, M., Fekri, F.: A fast correlation attack via unequal error correcting ldpc codes. In: Okamoto, T. (ed.) Topics in Cryptology—CT-RSA 2004. Lecture Notes in Computer Science, vol. 2964, pp. 54–66 (2004)
  35. Penzhorn, W.T.: Correlation attacks on stream ciphers: computing low weight parity checks based on error correction codes. In: Gollman, D. (ed.) Fast Software Encryption’96. Lecture Notes in Computer Science, vol. 1039, pp. 159–172. Springer-Verlag (1996)
  36. Penzhorn, W.T., K眉hn, G.J.: Computation of low-weight parity checks for correlation attacks on stream ciphers. In: Boyd, C. (ed.) Cryptography and Coding—5th IMA Conference. Lecture Notes in Computer Science, vol. 1025, pp. 74–83. Springer-Verlag (1995)
  37. Siegenthaler, T.: Correlation Attacks on Certain Stream Ciphers with Nonlinear Generators. Presented at IEEE Int. Symp. Inform. Theory, Saint Jovite, Canada, 26–29 Sept. (1983)
  38. Siegenthaler, T.: Decrypting a class of stream ciphers using ciphertext only. IEEE Trans. Comput. 34, 81–85 (1985)
  39. Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) Advances in Cryptology—CRYPTO 2002. Lecture Notes in Computer Science, vol. 2442, pp. 288–303. Springer-Verlag (2002)
  40. Zhang, B., Feng, D.: Multi-pass fast correlation attack on stream ciphers. In: Biham, E., Youssef, A.M. (eds.) Selected Areas in Cryptography—SAC 2006. Lecture Notes in Computer Science, vol. 4356, pp. 234–248. Springer-Verlag (2007)
• 作者单位：1. Department of Electrical and Information Technology, Lund University, P.O. Box 118, 221 00 Lund, Sweden
• ISSN：1936-2455

文摘

Fast correlation attacks, pioneered by Meier and Staffelbach in 1988, constitute an important class of attacks on stream ciphers. They exploit a correlation between the keystream and the output of a linear feedback shift register (LFSR) within the cipher. Several factors affect the feasibility of such an attack, e.g., the amount of available keystream and the number of taps in the LFSR. Notably, for a fixed number of taps, the length of the LFSR does not affect the complexity of the attack. When the register does not have a sufficiently small number of taps, however, the attacker will try to find parity check equations of low weight, at which point the length of the register does matter. In this paper, we go through the significant contributions to this field of cryptanalysis, reiterating the various algorithms that have been developed for finding parity check equations and performing the online stage on received keystream. We also suggest some new generalizations of Meier-Staffelbach’s original formulations.