Recently, AIDA/cube testers have been revealed to be useful in building distinguishers for several cryptography schemes. χ² tests, on the other hand, are well known and extensively used for distinguishing purposes. In this study, the notion of multi-χ² test and AIDA/cube testers are utilised to introduce the superpoly algebraic normal form monomial test through which the output of reduced round Trivium is distinguished from being random. The test successfully distinguishes the keystream of Trivium with 830 out of 1152 initialisation rounds with a complexity of 2³⁹ operations, which is the most effective distinguisher on reduced Trivium thus far. Applying algebraic IV differential attack (AIDA)/cube testers to a system, one of the main concerns is the appropriate choice of the superpoly variables, in the sense that the complexity of distinguishing the system output becomes near minimal. In an effort to discover appropriate superpoly variables, the authors propose a heuristic method that determines weak combination set of bits. The notion of weak combinations is defined in this study as a property ofthe cube variables whose corresponding superpoly is distinguishable. This heuristic method is performed on reduced round Trivium and its strength on determining appropriate superpoly variables is verified for 730 and 760 rounds Trivium.

References

1. 1)
  - 22. Stankovski, P.: ‘Greedy distinguishers and nonrandomness detectors’, InGong, G., Gupta, K.C. (Eds.), INDOCRYPT. Lecture Notes in Computer Science, (LNCS, 6498), (Springer, 2010), pp. 210–226.
2. 2)
  - 1. Englund, H., Johansson, T., Turan, M.S.: ‘A framework for chosen IV statistical analysis of stream ciphers’. INDOCRYPT,2007, (LNCS4859), pp. 268–281.
3. 3)
  - 15. Vardasbi, A., Salmasizadeh, M., Mohajeri, J.: ‘On the multi-chi-square tests and their data complexity’, ISC Int. J. Inf. Security (ISeCure), 2012, 4, (1), pp. 15–24.
4. 4)
  - 12. Bedi, S.S., Rajesh Pillai, N.: ‘Cube attacks on Trivium’, available at: http://eprint.iacr.org/2009/015.
5. 5)
  - 8. Kaminsky, A.: ‘Cube test analysis of the statistical behavior of CubeHash and Skein’, IACR Cryptology ePrint Archive, 2010. Available at: http://eprint.iacr.org/2010/262.
6. 6)
  - 2. Saarinen, M.J.O.: ‘Chosen-IV statistical attacks on eSTREAM stream ciphers.’ eSTREAM, ECRYPT Stream Cipher Project, Report 2006/013, 2006. Available at: http://www.ecrypt.eu.org/stream.
7. 7)
  - 16. Nakahara, J.Jr., Sekar, G., Santana de Freitas, D., Chiann, C., Hugo de Souza, R., Preneel, B.: ‘A new approach to χ2 cryptanalysis of block ciphers’. Information Security, 12th Int. Conf., ISC 2009,(LNCS5735) (Springer, 2009) pp. 1–16.
8. 8)
  - 18. Pearson, K.: ‘On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling’, Philos. Mag. Series 550, 1900, pp. 157–175 (doi: 10.1080/14786440009463897).
9. 9)
  - 4. Filiol, E.: ‘A new statistical testing for symmetric ciphers and hash functions’. Int. Conf. on Information, Communications and Signal Processing,(LNCS2119), (Springer-Verlag, 2001), pp. 21–35.
10. 10)
  - 23. Knellwolf, S., Meier, W., Naya-Plasencia, M.: ‘Conditional differential cryptanalysis of trivium and KATAN’, in Miri, A., Vaudenay, S., (Eds.): ‘Selected areas in cryptography’ – 18th Int. Workshop, SAC 2011, (LNCS, 7118) (Springer, 2012), pp. 200–212.
11. 11)
  - 5. Knudsen, L.R., Rijmen, V.: ‘Known-key distinguishers for some block ciphers’, in AC07, (LNCS4833/2008), (Springer-Verlag, 2007), pp. 315–324.
12. 12)
  - 7. Aumasson, J.-P., Dinur, I., Meier, W., Shamir, A.: ‘Cube testers and key recovery attacks on reduced-round MD6 and Trivium’, In Dunkelman, O. (Ed.) FSE'09, LNCS 5665(FSE, LNCS) (Springer, 2009).
13. 13)
  - 6. Lai, X.: ‘Higher order derivatives and differential cryptanalysis’, in Blahut, R., (Ed.) ‘Communications and Cryptography’. Kluwer, 1994.
14. 14)
  - 17. Vaudenay, S.: ‘An experiment on DES statistical cryptanalysis’, CCS'96, Proc. Third ACM Conf. on Computer and Communications Security, New Delhi, India, March, 1996.
15. 15)
  - 21. De Canniere, C., Preneel, B.: ‘TRIVIUM - stream cipher construction inspired by block cipher design principles’. eStream: ECRYPTStream Cipher Project, Report 2005/030, 2005, http://www.ecrypteu.org/stream/trivium.html.
16. 16)
  - 20. Fischer, S., Khazaei, S., Meier, W.: ‘Chosen IV statistical analysis for key recovery attacks on stream ciphers’. AFRICACRYPT2008.
17. 17)
  - 13. Dinur, I., Shamir, A.: ‘Cube attacks on tweakable black box polynomials,’ In Joux, A., (Ed.), EUROCRYPT 2009, LNCS, 2009.
18. 18)
  - 9. Vielhaber, M.: ‘Breaking ONE.FIVIUM by AIDA an algebraic IV differential attack,’ in Cryptology ePrint Archive, Report 2007/413.
19. 19)
  - 3. O'Neil, S.: ‘Algebraic structure defectoscopy’. Cryptology ePrintArchive, Report 2007/378, 2007.
20. 20)
  - 19. Dinur, I., Shamir, A.: ‘Breaking grain-128 with dynamic cube attacks’. in Joux, A. (Ed.), Fast Software Encryption-18th International Workshop, FSE 2011, (LNCS6733) (Springer, 2011), pp. 167–187.
21. 21)
  - 11. Vielhaber, M.: ‘Speeding up AIDA, the algebraic IV differential attack, by the fast Reed-Muller transform’, Proc. ISKE Intelligent systems and Knowledge Engineering. Heerlen, Belgium, World Scientific, 2009.
22. 22)
  - 14. Zhu, B., Gong, G., Lai, X., Chen, K.: ‘Another view on cube attack, cube tester, AIDA and higher order differential cryptanalysis’, in: 2012 Technical Reports of the Centre for Applied Cryptographic Research (CACR) at the University of Waterloo, available on: http://cacr.uwaterloo.ca/techreports/2012/cacr2012-01.pdf (accessed: August 2012).
23. 23)
  - 10. Bard, G.V., Courtois, N., Nakahara, J., Sepehrdad, P., Zhang, B.: ‘Algebraic, AIDA/cube, and side channel analysis of KATAN family of blockciphers’, INDOCRYPT 2010, (LNCS6498), Springer, 2012, pp. 176–196.

Superpoly algebraic normal form monomial test on Trivium

References

Related content