Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

A Low-Complexity and High-Performance Algorithm for the Fast Correlation Attack

Miodrag J. MihaljevićContact Information, Marc P. C. FossorierContact Information and Hideki ImaiContact Information

(5)  Mathematical Institute, Serbian Academy of Science and Arts, Kneza Mihaila 35, 11001 Belgrade, Yugoslavia
(6)  Department of Electrical Engineering, University of Hawaii, 2540 Dole St. Holmes Hall 483, 96822 Honolulu, HI, USA
(7)  Institute of Industrial Science, University of Tokyo, 7-22-1, Roppongi, 106-8558 Minato-ku, Tokyo, Japan
Abstract
An algorithm for cryptanalysis of certain keystream generators is proposed. The developed algorithm has the following two advantages over other reported ones: (i) it is more powerful and (ii) it provides a high-speed software implementation, as well as a simple hardware one, suitable for high parallel architectures. The novel algorithm is a method for the fast correlation attack with significantly better performance than other reported methods, assuming a lower complexity and the same inputs. The algorithm is based on decoding procedures of the corresponding binary block code with novel constructions of the paritychecks, and the following two decoding approaches are employed: the a posterior probability based threshold decoding and the belief propagation based bit-flipping iterative decoding. These decoding procedures offer good trade-offs between the required sample length, overall complexity and performance. The novel algorithm is compared with recently proposed improved fast correlation attacks based on convolutional codes and turbo decoding. The underlying principles, performance and complexity are compared, and the gain obtained with the novel approach is pointed out.

Keywords  stream ciphers - keystream generators - linear feedback shift registers - fast correlation attack - decoding

This work was supported by JSPS Grant RFTF 96P00604 and NSF Grant CCR-97- 32959

Contact Information Miodrag J. Mihaljević
Email: miodragm@turing.mi.sanu.ac.yu

Contact Information Marc P. C. Fossorier
Email: marc@spectra.eng.hawaii.edu

Contact Information Hideki Imai
Email: imai@iis.u-tokyo.ac.jp
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Referenced by
3 newer articles

  1. Golić, Jovan DJ. (2005) Vectorial Approach to Fast Correlation Attacks. Designs Codes and Cryptography 35(1)
    [CrossRef]
  2. Lu, Yi (2008) Cryptanalysis of an E0-like Combiner with Memory. Journal of Cryptology 21(3)
    [CrossRef]
  3. Michael, L.B. (2002) A framework for secure download for software-defined radio. IEEE Communications Magazine 40(7)
    [CrossRef]
Remote Address: 38.107.191.105 • Server: mpweb04
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)