Abstract:
Discrete Fourier Transform (DFT) attack is a latest cryptanalytic technique to recover the initial state of a keystream generator by reducing the number of unknowns in the system of linear equations to the minimum, by a corresponding increase in complexity of pre-computation and substitution. The complexity increase is a trade off with reduced unknowns and numbers of the required consecutive bits of the keystream sequence equal to the linear span of the sequence. This attack has been categorized in two versions. One version requires the captured keystream sequence equal to linear span of the cipher for recovering the initial state/key. The second version of this attack reduces the requirement of keystream by lowering the linear span by multiplying the sequence by another sequence having the linear span less than the linear span of the original sequence to recover the key. The DFT attack results in an efficient attack than Fast Algebraic Attack (FAA).
This research explores the possibility of the application of the DFT attack on practical symmetric cipher structure. It includes all versions of DFT attack (Ronjom et al. New Attack, Selective and Fast Selective) and has been tried against different structures including block ciphers, stream ciphers with filtering sequence generators and clock controlled ciphers. The attack has been applied on practical stream cipher Welch Gong (WG)-7. WG-7 is a lightweight, hardware oriented stream cipher that uses a word oriented linear feedback shift register (LFSR) and a nonlinear WG transformation that acts on the LFSR output word. The research aims at faster recovery of keystream than predicted complexity of the DFT attack by the designers.
