Probabilistic properties of bit-search type encryption algorithms and the backtracking attack

Abstract

Linear Feedback Shift Registers (LFSRs) are the pseudorandom number generatorsthat are used as keystream generators in Stream Ciphers. LFSRs are algebraicallyweak systems that have some vulnerability. To overcome this weakness of LFSRs,lots of nonlinear structures are used. In this thesis, we will deal with the mostcommon technique to use nonlinearity in stream ciphers, which is called thecompression algorithms. We investigate the probabilistic properties of the mostcommon ones of these compression algorithms. They are SSG, BSG, ABSG, MBSGand EBSG. We also proposed a new attack to the EBSG algorithms that is called thebacktracking attack.Keywords: Bit Search Generator, Pseudo-Random Sequence, Backtracking Attack,Compression, Self-Shrinking Generator, ABSG, MBSG, EBSG.