Observer Attack on Stream Ciphers

Ramachandran Anantharaman; Virendra Sule

Paper 2021/126

Observer Attack on Stream Ciphers

Ramachandran Anantharaman

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 in pre-computation and of for online computation, where for stream generators with states and the degree of the output function, when the stream generator is defined over . 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)

Metadata

Available format(s): PDF
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; 2021-02-05: received; See all versions
Short URL: https://ia.cr/2021/126
License: 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},
      url = {https://eprint.iacr.org/2021/126}
}