Paper 2021/928

Necessary and Sufficient Conditions for Galois NFSRs Equivalent to Fibonacci Ones and Their Application to the Stream Cipher Trivium

Jianghua Zhong, Yingyin Pan, Wenhui Kong, and Dongdai Lin

Abstract

Many recent stream ciphers use Galois NFSRs as their main building blocks, such as the hardware-oriented finalists Grain and Trivium in the eSTREAM project. Previous work has found some types of Galois NFSRs equivalent to Fibonacci ones, including that used in Grain. Based on the observability of an NFSR on [0,N-1], which means any two initial states of an NFSR are distinguishable from their corresponding output sequences of length N, the paper first presents two easily verifiable necessary and sufficient conditions for Galois NFSRs equivalent to Fibonacci ones. It then validates both conditions by the Galois NFSRs previously found (not) equivalent to Fibonacci ones. As an application, the paper finally reveals that the 288-stage Galois NFSR used in Trivium is neither equivalent to a 288-stage Fibonacci NFSR, nor observable on [0,287], theoretically verifying Trivium's good design criteria of confusion and diffusion.

Note: Several grammatical errors and typos were corrected. A theorem (i.e., Theorem 4.12') and its short proof were added to Page 17.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Shift registerBoolean functionstream cipherTriviumequivalenceobservabilityBoolean network
Contact author(s)
zhongjianghua @ iie ac cn
History
2021-08-20: revised
2021-07-09: received
See all versions
Short URL
https://ia.cr/2021/928
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/928,
      author = {Jianghua Zhong and Yingyin Pan and Wenhui Kong and Dongdai Lin},
      title = {Necessary and Sufficient Conditions for Galois NFSRs Equivalent to Fibonacci Ones and Their Application to the Stream Cipher Trivium},
      howpublished = {Cryptology ePrint Archive, Paper 2021/928},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/928}},
      url = {https://eprint.iacr.org/2021/928}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.