Two alerts for design of certain stream ciphers: Trapped LFSR and weak resilient function over GF(q)

Abstract

This paper points out: (i) a possibility for malicious selection of the LFSRs feedback polynomials in order to install a trap-door for the cryptanalysis; and (ii) a weakness of the construction of the resilient functions over GF(q) proposed at CRYPTO'96. Two corresponding methods for cryptanalysis are proposed. It is shown that although certain keystream generators over GF(q) are resistant against correlation and linear complexity based attacks, they are vulnerable by some novel attacks. The efficiency of these attacks depends on characteristics of the employed LFSRs and resilient functions. The developed attacks imply that LFSRs with certain characteristic polynomials and certain resilient functions are inappropriate as the building components for nonlinear combination generators and related schemes. They imply certain design criteria for employment of LFSRs and resilient functions over GF(q) in the nonlinear combination keystream generators and related schemes.