Cryptology ePrint Archive: Report 2007/129
An Algebraic Analysis of Trivium Ciphers based on the Boolean Satisfiability Problem
Cameron McDonald, Chris Charnes, Josef Pieprzyk
Abstract: Trivium is a stream cipher candidate of the eStream project.
It has successfully moved into phase three of the selection process under
the hardware category. No attacks faster than the exhaustive search have
so far been reported on Trivium.
Bivium-A and Bivium-B are simplified versions of Trivium
that are built on the same design principles but with two registers.
The simplified design is useful in investigating Trivium type ciphers
with a reduced complexity and provides insight into effective
attacks which could be extended to Trivium.
This paper focuses on an algebraic analysis which
uses the boolean satisfiability problem in propositional logic.
For reduced variants of the cipher,
this analysis recovers the internal state with
a minimal amount of keystream observations.
Category / Keywords: Algebraic Analysis, Boolean Satisfiability, Trivium, eStream
Date: received 4 Apr 2007, last revised 17 Dec 2007
Contact author: cmcdonal at ics mq edu au
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Note: Revision of results.
Version: 20071218:054516 (All versions of this report)
Short URL: ia.cr/2007/129
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]