### Observer Attack on Stream Ciphers

##### 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.

Note: Accepted in the proceedings of 25th International Symposium on Mathematical Theory of Networks and Systems (MTNS 2022)

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Cryptanalysis Stream ciphers Koopman operator Observer theory
Contact author(s)
ramachandran @ ee iitb ac in
vrs @ ee iitb ac in
History
2022-07-19: last of 2 revisions
See all versions
Short URL
https://ia.cr/2021/126

CC BY

BibTeX

@misc{cryptoeprint:2021/126,
author = {Ramachandran Anantharaman and Virendra Sule},
title = {Observer Attack on Stream Ciphers},
howpublished = {Cryptology ePrint Archive, Paper 2021/126},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/126}},
url = {https://eprint.iacr.org/2021/126}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.