Cryptology ePrint Archive: Report 2013/240

Algebraic analysis of Trivium-like ciphers

Sui-Guan Teo and Kenneth Koon-Ho Wong and Harry Bartlett and Leonie Simpson and Ed Dawson

Abstract: Trivium is a bit-based stream cipher in the final portfolio of the eSTREAM project. In this paper, we apply the approach of Berbain et al. to Trivium-like ciphers and perform new algebraic analyses on them, namely Trivium and its reduced versions: Trivium-N, Bivium-A and Bivium-B. In doing so, we answer an open question in the literature. We demonstrate a new algebraic attack on Bivium-A. This attack requires less time and memory than previous techniques which use the F4 algorithm to recover Bivium-A's initial state. Though our attacks on Bivium-B, Trivium and Trivium-N are worse than exhaustive keysearch, the systems of equations which are constructed are smaller and less complex compared to previous algebraic analysis. Factors which can affect the complexity of our attack on Trivium-like ciphers are discussed in detail.

Category / Keywords: secret-key cryptography / Stream ciphers, Trivium, Trivium-N, Bivium-A, Bivium-B, algebraic attacks

Date: received 28 Apr 2013, last revised 28 Apr 2013

Contact author: teosuiguan at gmail com

Available formats: PDF | BibTeX Citation

Version: 20130429:113712 (All versions of this report)

Discussion forum: Show discussion | Start new discussion