×

Observing biases in the state: case studies with Trivium and Trivia-SC. (English) Zbl 1402.94068

Summary: One generic model of stream cipher considers updating the states and then combining the state bits to produce the key-stream. In case there are biases in the state bits, that may be reflected on the key-stream bits resulting certain weaknesses (distinguisher and/or key recovery) of the cipher. In this context, we study the state biases as well as key-stream biases with great details. We first experiment with cube testers and heuristically obtain several distinguishers for Trivium running more than 800 rounds (maximum 829) with cube sizes not exceeding 27. Further, we apply our techniques to analyze Trivia-SC (the stream cipher used in TriviA-ck AEAD scheme, selected in second round of CAESAR competition) and obtain distinguishers till 950 rounds with a cube size of 25 only. On Trivia-SC, our results refute certain claims made by the designers against both cube and slide attacks. Our detailed empirical analysis provides new results in reduced-round cryptanalysis of Trivium and Trivia-SC.

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aumasson J.P., Dinur I., Meier W., Shamir A.: Cube testers and key recovery attacks on reduced-round MD6 and trivium. In: FSE 2009. LNCS, vol. 5665, pp. 1-22 (2009). · Zbl 1291.94051
[2] Baksi A., Maitra S., Sarkar S.: An improved slide attack on trivium. IPSI Transaction on Internet Research (2015).
[3] Baksi A., Maitra S., Sarkar S.: Distinguishers, new, for reduced round trivium and trivia-SC using cube testers. In: WCC, the Ninth International Workshop on Coding and Cryptography. France, Paris, April 13-17, 2015.
[4] Banik S., Maitra S., Sarkar S., Turan M.S.: A chosen IV related key attack on Grain-128a. In: ACISP 2013. LNCS, vol. 7959, pp. 13-26 (2008). · Zbl 1285.94042
[5] Biham E., Dunkelman O., Keller N.: Improved slide attacks. In: FSE 2007. LNCS, vol. 4593, pp. 153-166 (2007). · Zbl 1186.94425
[6] Biryukov A., Wagner D.: Slide attacks. In: FSE 1999. LNCS, vol. 1636, pp. 245-259 (1999) · Zbl 0942.94020
[7] Biryukov A., Wagner D.: Advanced slide attacks. In: EUROCRYPT 2000. LNCS, vol. 1807, pp. 589-606 (2000). · Zbl 1082.94506
[8] Blum M., Luby M., Rubinfeld R.: Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47(3), 549-595 (1993). · Zbl 0795.68131
[9] CAESAR: Competition for authenticated encryption: security, applicability, and robustness. Available at http://competitions.cr.yp.to/caesar.html.
[10] Courtois N., Bard G.V., Wagner D.: Algebraic and slide attacks on KeeLoq. In: FSE 2008. LNCS, vol. 5086, pp. 97-115 (2008). · Zbl 1154.68388
[11] Chakraborti A., Nandi M.: TriviA-ck-v1. March 15, 2014. Available at http://competitions.cr.yp.to/round1/triviackv1.
[12] Chakraborti A., Nandi M.: TriviA-ck-v2. August 28, 2015. Available at http://competitions.cr.yp.to/round2/triviackv2.
[13] Chakraborti A., Nandi M.: Important features and flexibilities of TriviA. Presentation at DIAC (2014). Available at http://2014.diac.cr.yp.to/slides/nandi-trivia.
[14] Chakraborti A., Chattopadhyay A., Hassan M., Nandi M.: TriviA: a fast and secure authenticated encryption scheme. In: CHES 2015. LNCS, vol. 9293, pp. 330-353 (2015). · Zbl 1380.94077
[15] De Cannière C., Preneel B.: Trivium. Available at http://www.ecrypt.eu.org/stream/p3ciphers/trivium/trivium_p3.
[16] De Cannière C., Küçük O., Preneel B.: Analysis of Grain’s initialization algorithm. In: AFRICACRYPT 2008. LNCS, vol. 5023, pp. 276-289 (2008). · Zbl 1142.94340
[17] Dinur I., Shamir A.: Cube attacks on tweakable black box polynomials. In: Eurocrypt 2009. LNCS, vol. 5479, pp. 278-299 (2009). See also: Cube Attacks on Tweakable Black Box Polynomials. Available at http://eprint.iacr.org/2008/385. · Zbl 1239.94045
[18] Englund H., Johansson T., Turan M.S.: A framework for chosen IV statistical analysis of stream ciphers. In: INDOCRYPT 2007. LNCS, vol. 4859, pp. 268-281 (2007). · Zbl 1153.94373
[19] eSTREAM: the ECRYPT Stream Cipher Project. Available at http://www.ecrypt.eu.org/stream/.
[20] Fouque P.A., Vannet T.: Improving key recovery to 784 and 799 rounds of trivium using optimized cube attacks. In: FSE 2013. LNCS, vol. 8424, pp. 502-517 (2013). · Zbl 1321.94058
[21] GCC, the GNU Compiler Collection. Available at https://gcc.gnu.org/.
[22] ISO/IEC 29192-2:2012. Available at http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=56552.
[23] Josh R.J., Sarkar S.: Some observations on ACORN v1 and Trivia-SC. In: Lightweight Cryptography Workshop, NIST, USA, 20-21 July 2015.
[24] Knellwolf S., Meier W., Naya-Plasencia M.: Conditional differential cryptanalysis of trivium and KATAN. In: SAC 2011. LNCS, vol. 7118, pp. 200-212 (2011). · Zbl 1292.94095
[25] Knudsen L.R.: Truncated and higher order differentials. In: FSE 1994. LNCS, vol. 1008, pp. 196-211 (1994). · Zbl 0939.94556
[26] Kukorelly Z.: The piling-up lemma and dependent random variables. In: 7th IMA International Conference. LNCS, vol. 1746, pp. 186-190 (1999). · Zbl 0981.94029
[27] Lee Y., Jeong K., Sung J., Hong S.: Related-key chosen IV attacks on Grain-v1 and Grain-128. In: ACISP 2008. LNCS, vol. 5107, pp. 321-335 (2008). · Zbl 1285.94076
[28] Liu M., Lin D., Wang W.: Searching cubes for testing Boolean functions and its application to trivium. In: ISIT 2015, International Symposium on Information Theory, pp. 496-500. Hong Kong, China, 14-19 June 2015.
[29] Massacci F.: Using Walk-SAT and Rel-Sat for cryptographic key search. In: IJCAI 1999, International Joint Conference on Artificial Intelligence, pp. 290-295. Stockholm, Sweden, 31 July-6 August 1999.
[30] Maximov A., Biryukov A.: Two trivial attacks on trivium. In: SAC 2007. LNCS, vol. 4876, pp. 36-55 (2007). · Zbl 1154.94418
[31] Meier W.: Cube testers and key recovery in symmetric cryptography. Presentation at INDOCRYPT (2009). Available at http://indocrypt09.inria.fr/slides_cube_ind09.
[32] Paterson K.G., Poettering B., Schuldt J.C.N.: Big bias hunting in Amazonia: large-scale Computation and exploitation of RC4 biases. In: ASIACRYPT 2014. LNCS, Part 1, vol. 8873, pp. 398-419 (2014). · Zbl 1306.94082
[33] Priemuth-Schmid D., Biryukov A.: Slid Pairs in Salsa20 and Trivium. In: INDOCRYPT 2008. LNCS, vol. 5365, pp. 1-14 (2008). · Zbl 1203.94119
[34] Sage: Open Source Mathematics Software. Available at http://www.sagemath.org/.
[35] Soos M.: CryptoMiniSat-2.9.5. http://www.msoos.org/cryptominisat2/.
[36] Stankovski P.: Greedy distinguishers and nonrandomness detectors. In: INDOCRYPT 2010. LNCS, vol. 6498, pp. 210-226 (2010). · Zbl 1294.94078
[37] Stankovski P: PhD thesis, Lund University, Sweden (2013). Available at http://lup.lub.lu.se/luur/download?func=downloadFile&recordOId=3799743&fileOId=3799763.
[38] Stinson D.R.: Cryptography Theory and Practice, 3rd edn. Chapman & Hall/CRC, Boca Raton (2006). · Zbl 1085.94001
[39] Turan M.S.: Related Key/IV Pairs for Trivia-SC. Discussion at Google Group, 27 August 2014. Available at https://groups.google.com/forum/#searchin/crypto-competitions/trivia/crypto-competitions/Uzgt-2t3knM/kjv5kWKJ3nAJ.
[40] Vardasbi A., Salmasizadeh M., Mohajeri J.: Superpoly algebraic normal form monomial test on Trivium. IET Inf. Secur. 7(3), 230-238 (2013). doi:10.1049/iet-ifs.2012.0175.
[41] Xu C., Zhang B., Feng D.: Linear cryptanalysis of FASER128/256 and TriviA-ck. In: INDOCRYPT 2014. LNCS, vol. 8885, pp. 237-254 (2014). · Zbl 1337.94081
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.