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.
|
 |
A Low-Complexity and High-Performance Algorithm for the Fast Correlation Attack
| |
|
A Low-Complexity and High-Performance Algorithm for the Fast Correlation Attack
Miodrag J. Mihaljević5 , Marc P. C. Fossorier6 and Hideki Imai7 
| (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
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|