Paper 2006/141

Linear Sequential Circuit Approximation of Grain and Trivium Stream Ciphers

Shahram Khazaei, Mahdi M. Hasanzadeh, and Mohammad S. Kiaei

Abstract

Grain and Trivium are two hardware oriented synchronous stream ciphers proposed as the simplest candidates to the ECRYPT Stream Cipher Project, both dealing with 80-bit secret keys. In this paper we apply the linear sequential circuit approximation method to evaluate the strength of these stream ciphers against distinguishing attack. In this approximation method which was initially introduced by Golic in 1994, linear models are effectively determined for autonomous finite-state machines. We derive linear functions of consecutive key-stream bits which are held with correlation coefficient of about 2^-63.7 and 2^-126 for Grain and Trivium ciphers, respectively. Then using the concept of so-called generating function, we turn them into linear functions with correlation coefficient of 2^-29 for Grain and 2^-72 for Trivium. It shows that the Grain output sequence can be distinguished from a purely random sequence, using about 2^58 bits of the output sequence with the same time complexity. However, our attempt fails to find a successful distinguisher for Trivium.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Stream CipherDistinguishing AttackLinear Sequential Circuit ApproximationGrainTriviumECRYPTSecurity Evaluation.
Contact author(s)
shahram khazaei @ gmail com
History
2006-04-11: received
Short URL
https://ia.cr/2006/141
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/141,
      author = {Shahram Khazaei and Mahdi M.  Hasanzadeh and Mohammad S.  Kiaei},
      title = {Linear Sequential Circuit Approximation of Grain and Trivium Stream Ciphers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/141},
      year = {2006},
      url = {https://eprint.iacr.org/2006/141}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.