nach oben

Designs, Codes and Cryptography

Erschienen in:

02.05.2016

Observing biases in the state: case studies with Trivium and Trivia-SC

verfasst von: Santanu Sarkar, Subhamoy Maitra, Anubhab Baksi

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1-2/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity

Nächster Artikel Security proof of the canonical form of self-synchronizing stream ciphers

This assumption is theoretically not true as the state evolves from the previous state and thus they cannot be independent. However, given a standard design, it is expected that after sufficient rounds of iteration, the state bits would not have significant dependence among themselves and thus the assumption works well as a rough estimate which is evident from experimental results that we will discuss in detail in Sect. 2.3 and Remark 3.

As already explained in Sect. 1, it can be assumed for practical purposes as it is expected that after quite a few rounds of initialization, the individual state bits should not have any significant dependence. We explain it with an example in Remark 3.

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).

Baksi A., Maitra S., Sarkar S.: An improved slide attack on trivium. IPSI Transaction on Internet Research (2015).

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.

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).

Biham E., Dunkelman O., Keller N.: Improved slide attacks. In: FSE 2007. LNCS, vol. 4593, pp. 153–166 (2007).

Biryukov A., Wagner D.: Slide attacks. In: FSE 1999. LNCS, vol. 1636, pp. 245–259 (1999)

Biryukov A., Wagner D.: Advanced slide attacks. In: EUROCRYPT 2000. LNCS, vol. 1807, pp. 589–606 (2000).

Blum M., Luby M., Rubinfeld R.: Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47(3), 549–595 (1993).

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).

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).

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).

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.

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).

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).

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).

25.

Knudsen L.R.: Truncated and higher order differentials. In: FSE 1994. LNCS, vol. 1008, pp. 196–211 (1994).

26.

Kukorelly Z.: The piling-up lemma and dependent random variables. In: 7th IMA International Conference. LNCS, vol. 1746, pp. 186–190 (1999).

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).

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).

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).

33.

Priemuth-Schmid D., Biryukov A.: Slid Pairs in Salsa20 and Trivium. In: INDOCRYPT 2008. LNCS, vol. 5365, pp. 1–14 (2008).

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).

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).

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).

Titel: Observing biases in the state: case studies with Trivium and Trivia-SC
verfasst von: Santanu Sarkar
Subhamoy Maitra
Anubhab Baksi
Publikationsdatum: 02.05.2016
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1-2/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-016-0211-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1-2/2017

Improving algebraic attacks on stream ciphers based on linear feedback shift register over

Almost cover-free codes and designs

On some permutation binomials and trinomials over

Optimal software-implemented Itoh–Tsujii inversion for

Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity

Energy bounds for codes and designs in Hamming spaces