Title: Algebraic analysis of Trivium and Trivium/128

Authors: Mehreen Afzal, Ashraf Masood

Addresses: College of Signals, National University of Science and Technology, Rawalpindi 46000, Pakistan. ' College of Signals, National University of Science and Technology, Rawalpindi 46000, Pakistan

Abstract: Trivium an eSTREAM candidate has an internal state of 288 bits, and it has been designed to provide a security level of 80 bits. Recently, its tweaked structure Trivium/128 with three added gates is also proposed which is meant to provide the security level of 128 bits without any increase in the internal state bits. This article presents an algebraic analysis of the key generating structure of both versions. Our experiments target to recover the internal state bits by solving practically the varying degree equations of Trivium, with some guessed bits using Groebner basis algorithm. Our analysis shows that although tweaked structure offer more complex equations, still it is unsuitable to provide a security level of 128 bits. We also propose a modified version of the Trivium. The algebraic relations of internal states with output bits formed using our proposed modified version are higher in degrees in comparison with both previous versions. Thus, our proposed version offers increased difficulty of recovering internal state bits by solving algebraic equations and this proves it to be more suitable to provide 128-bit security level.

Keywords: algebraic equations; cryptanalysis; Groebner basis; stream ciphers; Trivium; electronic security; key generation.

DOI: 10.1504/IJESDF.2008.021452

International Journal of Electronic Security and Digital Forensics, 2008 Vol.1 No.4, pp.344 - 352

Published online: 27 Nov 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article