Welcome to the resource topic for 2021/126
Title:
Observer Attack on Stream Ciphers
Authors: Ramachandran Anantharaman and Virendra Sule
Abstract:This paper proposes an internal state recovery attack on special class of stream generators called non-linear combiners and filter generators over finite fields consisting of linear feedback shift registers (LFSRs) and nonlinear functions combining internal states to form output stream. This attack utilizes the concept of an observer, well known in the theory of Linear Dynamical Systems. An observer is a special linear dynamical system which when fed with the output sequence of the stream generator as an input with arbitrary initial state, reconstructs the internal state of the generator in finite time. This attack is termed as observability attack and it is shown that the computations are of complexity O(D^4) in pre-computation and of O(D) for online computation, where D = \sum_{i=0}^{d} {n \choose i} for stream generators with n states and d the degree of the output function, when the stream generator is defined over \mathbb{F}_2. The attack is technically applicable over general finite fields and appropriate bounds on computation are estimated. This attack gives an important estimates of time and memory resources required for cryptanalysis of realistic stream ciphers.
ePrint: https://eprint.iacr.org/2021/126
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .