A novel fast correlation attack suitable for simple hardware implementation

Abstract

An algorithm for cryptanalysis of certain keystream generators is proposed. The developed algorithm has the following two advantages over the reported ones: it is more powerful and it can be implemented in a simple hardware suitable for high parallel architectures. The novel algorithm is a method for the fast correlation attack with significantly better performance than the reported methods, assuming a lower complexity and the same inputs. The algorithm is based on error-correction on information bits only (of the corresponding binary block code) with novel method for construction of the parity-checks, and the employed error-correction procedure is an APP based threshold decoding. An experimental analysis of the algorithm performance is presented, and its complexity is pointed out. The novel algorithm is compared with recently proposed improved fast correlation attacks based on the convolutional codes and turbo decoding. The underlying principles, performance and complexity are compared, and the gain obtained with the novel approach is pointed out.