Paper 2005/126

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

Shahram Khazaei, Mahmood Salmasizadeh, and Javad Mohajeri

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
stream ciphersclock-controlled generatorsshrinking generatordivide and conquer attackoptimal correlation attacksdeletion channeljoint probability.
Contact author(s)
shahram khazaei @ gmail com
History
2012-05-19: revised
2005-04-29: received
See all versions
Short URL
https://ia.cr/2005/126
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/126,
      author = {Shahram Khazaei and Mahmood Salmasizadeh and Javad Mohajeri},
      title = {On the Statistically Optimal Divide and Conquer Correlation Attack on the Shrinking Generator},
      howpublished = {Cryptology {ePrint} Archive, Paper 2005/126},
      year = {2005},
      url = {https://eprint.iacr.org/2005/126}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.