Iterative optimum symbol-by-symbol decoding and fast correlation attacks

The relation between fast correlation attacks on stream ciphers based on linear feedback shift registers (LFSRs) and the Hartmann-Rudolph (1976) algorithm for optimal symbol-by-symbol decoding of linear block codes is theoretically investigated. By iterating approximate versions of the HR algorithm, novel iterative probabilistic decoding algorithms for fast correlation attacks are developed. In particular, these algorithms can be applied when a large number of nonorthogonal parity checks are used. A number of properties of the proposed iterated versions of the HR algorithm including convergence conditions and critical bit error rates are derived.