Improved guess-and-determine attack on TRIVIUM

Improved guess-and-determine attack on TRIVIUM

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

TRIVIUM is a stream cipher of the finalists by eSTREAM project and has been accepted as ISO standard. Although the design has a simple structure, no attack on its full cipher has been found yet. In this study, based on Maximov and Biryukov's attack, the authors present an improved guess-and-determine attack on TRIVIUM. Analysis details are provided corresponding to TRIVIUM specifications for better comprehension, and errors that may lead to higher attack complexity in the original attack are pointed and corrected. They further bring in some techniques like backward-clock equation collection, quadratic equations, linear transformation to improve the attack. In addition, they integrate with time-memory-data tradeoffs from the framework, based on the analysis of the coefficient matrices form of derived linear equation systems on the internal state. In this way, better use of the imposed quadratic conditions can be made, which leads to reduced attack complexity by filtering out the impossible keystreams before solving the equation systems. Their attack offers more parameter selections, and gives several borderline results compared with the key exhaustive search. The new attack behaves better in the original case. It also verifies the necessity of data requirement imposed on TRIVIUM, which is questioned in TRIVIUM specifications.


    1. 1)
      • 1. De Canniere, C., Preneel, B.: ‘Trivium specifications’. Report 2005/030, eSTREAM. ECRYPT Stream Cipher Project, 2005.
    2. 2)
      • 2. International Organization for Standardization (ISO): ‘ISO/IEC 29192-3:2012, information technology – security techniques – lightweight cryptography – part 3: stream ciphers’, 2012.
    3. 3)
      • 3. Englund, H., Johansson, T., Turan, M.S.: ‘A framework for chosen IV statistical analysis of stream ciphers’. Progress in Cryptology – INDOCRYPT 2007, 8th Int. Conf. on Cryptology in India, Chennai, India, 9–13 December 2007, pp. 268281, Proceedings.
    4. 4)
      • 4. Fischer, S., Khazaei, S., Meier, W.: ‘Chosen IV statistical analysis for key recovery attacks on stream ciphers’. Progress in Cryptology – AFRICACRYPT 2008, Casablanca, Morocco, 2008.
    5. 5)
      • 5. Knellwolf, S., Meier, W., Naya-Plasencia, M.: ‘Conditional differential cryptanalysis of Trivium and KATAN’. Int. Workshop on Selected Areas in Cryptography, Toronto, ON, Canada, 2011, pp. 200212, 236–245.
    6. 6)
      • 6. Dinur, I., Shamir, A.: ‘Cube attacks on tweakable black box polynomials’. Advances in Cryptology-EUROCRYPT2009, Cologne, Germany, 2009 (LNCS, 5479), pp. 278299.
    7. 7)
      • 7. Aumasson, J., Dinur, I., Meier, W., et al: ‘Cube testers and key recovery attacks on reduced-round MD6 and Trivium’. Fast Software Encryption, 16th Int. Workshop, FSE 2009, Leuven, Belgium, 2009, pp. 122.
    8. 8)
      • 8. Fouque, P., Vannet, T.: ‘Improving key recovery to 784 and 799 rounds of Trivium using optimized cube attacks’. Fast Software Encryption-20th Int. Workshop, FSE 2013, Singapore, 11–13 March 2013, pp. 502517. Revised Selected Papers.
    9. 9)
      • 9. Todo, Y., Isobe, T., Hao, Y., et al: ‘Cube attacks on non-blackbox polynomials based on division property’. Advances in Cryptology – CRYPTO 2017, Santa Barbara, CA, USA, 20–24 August 2017, pp. 250279, Proceedings, Part III.
    10. 10)
      • 10. Liu, M., Yang, J., Wang, W., et al: ‘Correlation cube attacks: from weak-key distinguisher to key recovery’. Advances in Cryptology – EUROCRYPT 2018, Tel Aviv, Israel, 29 April – 3 May 2018, pp. 715744. Proceedings, Part II.
    11. 11)
      • 11. Fu, X., Wang, X., Dong, X., et al: ‘A key-recovery attack on 855-round Trivium authors’. Advances in Cryptology – CRYPTO 2018, Santa Barbara, CA, USA, 2018, pp. 160184.
    12. 12)
      • 12. Wang, Q., Hao, Y., Todo, Y., et al: ‘Improved division property based cube attacks exploiting algebraic properties of superpoly’. Advances in Cryptology – CRYPTO 2018, Santa Barbara, CA, USA, 2018, pp. 275305.
    13. 13)
      • 13. eSTREAM Discussion Forum: ‘A reformulation of Trivium created on 02/24/06 12:52PM’, 2005.
    14. 14)
      • 14. Raddum, H.: ‘Cryptanalytic results on Trivium’. Report 2006/039, eSTREAM, ECRYPT Stream Cipher Project, 2006.
    15. 15)
      • 15. Khazaei, S., Hasanzadeh, M.M., Kiaei, M.S.: ‘Linear sequential circuit approximation of grain and Trivium stream ciphers’. Report 2005/063, eSTREAM, ECRYPT Stream Cipher Project, 2005.
    16. 16)
      • 16. Maximov, A., Biryukov, A.: ‘Two trivial attacks on Trivium’. Selected Areas in Cryptography 2007, Ottawa, Canada, 2007, pp. 3655.
    17. 17)
      • 17. Babbage, S., De Canniere, C., Lano, J.: ‘Cryptanalysis of SOBER-t32’. FSE 2003. Heidelberg: Springer-Verlag, Lund, Sweden, 2003 (LNCS, 2887), pp. 111128.
    18. 18)
      • 18. Feng, X.T., Liu, J., Zhou, Z.C., et al: ‘A byte-based guess and determine attack on SOSEMANUK’. ASIACRYPT 2010, Singapore, 2010 (LNCS, 6477), pp. 146157.
    19. 19)
      • 19. Golić, J.: ‘Cryptanalysis of alleged A5 stream cipher’. EUROCRYPT, 1997, Germany, 1997, (LNCS, 1233), pp. 239255.
    20. 20)
      • 20. Hawkes, P., Rose, G.G.: ‘Guess-and-Determine attacks on SNOW’. SAC 2002, Newfoundland, Canada, 2002 (LNCS, 2595), pp. 3746.
    21. 21)
      • 21. Mattsson, J.: ‘A guess-and-determine attack on the stream cipher polar bear’. eSTREAM report 2006/017, 2006, pp. 510.

Related content

This is a required field
Please enter a valid email address