×

State cycles, initialization and the Trivium stream cipher. (English) Zbl 1285.94097

Summary: Trivium is a keystream generator for a binary additive synchronous stream cipher. It was selected in the final portfolio for the Profile 2 category of the eSTREAM project. The keystream generator is constructed using bit-based shift registers. In this paper we present an alternate representation of Trivium using word-based shift registers, with a word size of three bits. This representation is useful for determining cycles of internal state values. Under this representation it is clear that the state space can be partitioned into subspaces and that over some of these subspaces the state update function is effectively linear. The role of the initialization process is critical in ensuring the states used for generating keystream are updated nonlinearly at some point, as the state update function alone does not provide this.

MSC:

94A60 Cryptography
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory

Software:

eSTREAM; Trivium
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bernstein, D.: A reformulation of TRIVIUM. Submission to Phorum: ECRYPT forum, 20 February 2006. Available at http://www.ecrypt.eu.org/stream/phorum/read.php?1,448
[2] Courtois, N.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (eds.) Advances in Cryptology–CRYPTO’03. Lecture Notes in Computer Science, vol. 2729, pp. 177–194. Springer, Berlin (2003) · Zbl 1122.94365
[3] de Canniere, C., Preneel, B.: Trivium specification. Submission to eSTREAM, ECRYPT Stream Cipher Project. Report 2005/030 (2005). Available at http://www.ecrypt.eu.org/stream/ciphers/trivium/trivium.pdf
[4] Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. In: Joux, A. (ed.) Advances in Cryptology–EUROCRYPT 2009. Lecture Notes in Computer Science, vol. 5479, pp. 278–299. Springer, Berlin (2009) · Zbl 1239.94045
[5] Englund, H., Johansson, T., Turan, M.: A framework for chosen IV statistical analysis of stream ciphers. In: Srinathan, K., Pandu Rangan, C., Yung, M. (eds.) Progress in Cryptology–INDOCRYPT 2007. Lecture Notes in Computer Science, vol. 4859, pp. 268–281. Springer, Berlin (2007) · Zbl 1153.94373
[6] eSTREAM: The ECRYPT Stream Cipher Project. Available at http://www.ecrypt.eu.org/stream/
[7] Hong, J.: Some trivial states of Trivium. Posted to eSTREAM Phorum, 7 September 2005
[8] Hong, J.: Certain pairs of key–IV pairs for Trivium. Posted to eSTREAM Phorum, 13 September 2005
[9] Hu, H., Gong, G.: Periods on two kinds of nonlinear feedback shift registers with time varying feedback functions. Int. J. Found. Comput. Sci. 22(6), 1317–1329 (2011) · Zbl 1236.94046 · doi:10.1142/S0129054111008738
[10] Khazaei, S.: Re: A reformulation of TRIVIUM. Submission to Phorum: ECRYPT forum, 21 February 2006. Available at http://www.ecrypt.eu.org/stream/phorum/read.php?1,448
[11] Khazaei, S., Hasanzadeh, M.: Linear sequential circuit approximation of the trivium stream cipher. eSTREAM, ECRYPT Stream Cipher Project, Report 2005/063 (2005). Available at http://www.ecrypt.eu.org/stream/papersdir/2005/063.pdf
[12] Maximov, A., Biryukov, A.: Two trivial attacks on trivium. eSTREAM, ECRYPT Stream Cipher Project, Report 2007/003 (2007). Available at http://www.ecrypt.eu.org/stream/papersdir/2007/003.pdf · Zbl 1154.94418
[13] Raddum, H.: Cryptanalytic results on trivium. eSTREAM, ECRYPT Stream Cipher Project, Report 2006/039 (2006). Available at http://www.ecrypt.eu.org/stream/papersdir/2006/039.pdf
[14] Turan, M., Kara, O.: Linear approximations for 2-round trivium. eSTREAM, ECRYPT Stream Cipher Project, Report 2007/008 (2007). Available at http://www.ecrypt.eu.org/stream/papersdir/2007/008.pdf
[15] Vielhaber, M.: Breaking ONE.FIVIUM by AIDA an algebraic IV differential attack. IACR Cryptology eprint Archive, Report 2007/413 (2007). Available at http://eprint.iacr.org/2007/413.pdf
[16] Vielhaber, M.: AIDA breaks BIVIUM (A & B) in 1 minute dual core CPU time. IACR Cryptology eprint Archive, Report 2009/402 (2009). Available at http://eprint.iacr.org/2009/402.pdf
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.