Bias in the nonlinear filter generator output sequence

Sui-Guan Teo; Leonie Simpson; Ed Dawson

Paper 2010/105

Bias in the nonlinear filter generator output sequence

Sui-Guan Teo, Leonie Simpson, and Ed Dawson

Abstract

Nonlinear filter generators are common components used in the keystream generators for stream ciphers and more recently for authentication mechanisms. They consist of a Linear Feedback Shift Register (LFSR) and a nonlinear Boolean function to mask the linearity of the LFSR output. Properties of the output of a nonlinear filter are not well studied. Anderson noted that the $m$-tuple output of a nonlinear filter with consecutive taps to the filter function is unevenly distributed. Current designs use taps which are not consecutive. We examine $m$-tuple outputs from nonlinear filter generators constructed using various LFSRs and Boolean functions for both consecutive and uneven (full positive difference sets where possible) tap positions. The investigation reveals that in both cases, the $m$-tuple output is not uniform. However, consecutive tap positions result in a more biased distribution than uneven tap positions, with some m-tuples not occurring at all. These biased distributions indicate a potential flaw that could be exploited for cryptanalysis.

Note: Corrected a few typographical errors in the paper.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Accepted at the International Cryptology Conference 2010. This is the full version of the paper.
Keywords: Nonlinear filter generator Stream Cipher Output Sequences
Contact author(s): sg teo @ qut edu au
History: 2010-07-05: last of 2 revisions; 2010-03-01: received; See all versions
Short URL: https://ia.cr/2010/105
License: CC BY

BibTeX

@misc{cryptoeprint:2010/105,
      author = {Sui-Guan Teo and Leonie Simpson and Ed Dawson},
      title = {Bias in the nonlinear filter generator output sequence},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/105},
      year = {2010},
      url = {https://eprint.iacr.org/2010/105}
}