Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Cryptography and Communications
Erschienen in: Cryptography and Communications 3-4/2012

01.12.2012

A survey on fast correlation attacks

verfasst von: Martin Ågren, Carl Löndahl, Martin Hell, Thomas Johansson

Erschienen in: Cryptography and Communications | Ausgabe 3-4/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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.
Vorheriger Artikel Correlation attacks on combination generators
Nächster Artikel High order differential attacks on stream ciphers

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
Anhänge
Nur mit Berechtigung zugänglich
Literatur
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)MathSciNetMATHCrossRef
2.
Berrou, C., Glavieux, A.: Near optimum error correcting and decoding: turbo-codes. IEEE Trans. Commun. 4(10), 1261–1271 (1996)CrossRef
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)MathSciNetCrossRef
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)MathSciNetCrossRef
11.
Coppersmith, D.: Fast evaluation of logarithms in fields of characteristic two. IEEE Trans. Inf. Theory 30(4), 587–594 (1984)MathSciNetMATHCrossRef
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)CrossRef
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)CrossRef
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.
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)MathSciNetMATH
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)CrossRef
20.
Golić, J.Dj.: Iterative optimum symbol-by-symbol decoding and fast correlation attacks. IEEE Trans. Inf. Theory 47(7), 3040–3049 (2001)MATHCrossRef
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)MathSciNetMATHCrossRef
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.
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)CrossRef
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)
Metadaten
Titel
A survey on fast correlation attacks
verfasst von
Martin Ågren
Carl Löndahl
Martin Hell
Thomas Johansson
Publikationsdatum
01.12.2012
Verlag
Springer US
Erschienen in
Cryptography and Communications / Ausgabe 3-4/2012
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI
https://doi.org/10.1007/s12095-012-0062-x

Weitere Artikel der Ausgabe 3-4/2012

Cryptography and Communications 3-4/2012 Zur Ausgabe

EditorialNotes

Guest editorial

OriginalPaper

Correlation attacks on combination generators

OriginalPaper

High order differential attacks on stream ciphers

OriginalPaper

Cryptanalysis of WG-7: a lightweight stream cipher

OriginalPaper

Synthetic linear analysis with applications to CubeHash and Rabbit

OriginalPaper

State cycles, initialization and the Trivium stream cipher

Premium Partner

    Bildnachweise