International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the Statistically Optimal Divide and Conquer Correlation Attack on the Shrinking Generator

Authors:
Shahram Khazaei
Mahmood Salmasizadeh
Javad Mohajeri
Download:
URL: http://eprint.iacr.org/2005/126
Search ePrint
Search Google
Abstract: The shrinking generator is a well-known key stream generator composed of two LFSR?s, LFSRx and LFSRc, where LFSRx is clock-controlled according to the regularly clocked LFSRc. In this paper we investigate the minimum required length of the output sequence for successful reconstruction of the LFSRx initial state in an optimal probabilistic divide and conquer correlation attack. We extract an exact expression for the joint probability of the prefix of length m of the output sequence of LFSRx and prefix of length n of the output sequence of the generator. Then we use computer simulation to compare our probability measure and two other probability measures, previousely proposed in [5] and [3], in the sense of minimum required output length. Our simulation results show that our measure reduces the required output length.
BibTeX
@misc{eprint-2005-12462,
  title={On the Statistically Optimal Divide and Conquer Correlation Attack on the Shrinking Generator},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / stream ciphers, clock-controlled generators, shrinking generator, divide and conquer attack, optimal correlation attacks, deletion channel, joint probability.},
  url={http://eprint.iacr.org/2005/126},
  note={ shrm59@yahoo.com 12900 received 26 Apr 2005},
  author={Shahram Khazaei and Mahmood Salmasizadeh and Javad Mohajeri},
  year=2005
}