UDC 519.7
1 National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine
 alex-dtn@ukr.net
|
2 National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine
3tooth@iszzi.kpi.ua
|
3 National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine
undermyclouds@gmail.com
|
|
A METHOD FOR SECURITY EVALUATION OF SNOW 2.0-LIKE CIPHERS AGAINST
CORRELATION ATTACKS OVER FINITE EXTENSIONS OF THE FIELD OF TWO ELEMENTS
Abstract. A method is proposed for security evaluation of SNOW 2.0-like ciphers against correlation attacks,
which are generated by analogy with well-known attacks against SNOW 2. Unlike the available methods, the proposed
one is oriented to the proof of security and allows us to obtain lower estimates of the efficiency of attacks from the
considered class directly using the stream cipher components in the same way as it is done to prove the security
of block ciphers against linear cryptanalysis. Application of the method to SNOW 2.0 and “Strumok”
ciphers shows that any of the considered correlational attacks against them over the field of order
256 has an average time complexity no less than 2146,20 and 2249,20, respectively, and requires no less than 2142,77 and 2249,38 respectively, keysteam symbols.
Keywords: correlation cryptanalysis, finite-state machine, discrete Fourier transform, proof of security, SNOW 2.0, “Strumok”.
FULL TEXT
REFERENCES
- Ekdahl P., Johansson T. A new version of the stream cipher SNOW. Selected Areas in Cryptography — SAC 2002. LNCS 2295. Springer-Verlag. P. 47–61.
- ISO/IEC 18033-4: 2011(E). Information technology — Security techniques — Encryption algorithm. Part 4: Stream ciphers, 2011. 92 p.
- Watanabe D., Biryukov A., de CanniЩre C. A distinguishing attack of SNOW 2.0 with linear masking method. Selected Arreas in Cryptography — SAC 2003. LNCS 3006. Springer-Verlag. P. 222–233.
- Nyberg K., WallБn J. Improved linear distinguishers for SNOW 2.0. Fast Software Encryption — FSE 2006. LNCS 4047. Springer-Verlag, 2006. P. 144–162.
- Maximov A., Johansson Th. Fast computation for large distribution and its cryptographic application. Advanced in Cryptology — ASIACRYPT 2005. LNCS 3788. Springer-Verlag, 2005. P. 313–332.
- Lee J.-K., Lee D.H., Park S. Cryptanalysis of SOSEMANUC and SNOW 2.0 using linear masks. Advanced in Cryptology — ASIACRYPT 2008. LNCS 5350. Springer-Verlag, 2008. P. 524–538.
- Zhang B., Xu C., Meier W. Fast correlation attacks over extension fields, large-unit linear approximation and cryptanalysis of SNOW 2.0. Cryptology ePrint Archive. Report 2016/311. URL: http://eprint.iacr.org/2016/311.
- Gorbenko I., Kuznetsov A., Gorbenko Yu., Alekseychuk A., Timchenko V. Strumok keystream generator. The 9th IEEE International Conference on Dependable Systems, Services and Technologies, DESSERT’2018, 24–27 May, 2018. Kyiv, Ukraine. P. 292–299.
- Alekseychuk A.N., Konyushok S.N., Poremsky M.V. Upper bounds for the imbalance of discrete functions realized by sequences of finite automata. Kibernetika i sistemnyj analiz. 2019. Vol. 55, N 5. P. 58–66.
- Alekseychuk A.M. A sufficient condition for the stability of SNOW 2.0-like stream ciphers against certain attacks with related keys. Zakhyst informatsiyi. 2016. Vol. 18, N 3. P. 261–268.
- Oliynykov R.V., Gorbenko I.D., Kazymyrov O.V. et. al. A new encryption standard of Ukraine: The Kalyna block cipher. Cryptology ePrint Archive. URL: http://eprint.iacr.org/2015/650.
- Alekseychuk A.N., Kovalchuk L.V., Shevtsov A.S., Yakovlev S.V. About cryptographic properties of the new national encryption standard of Ukraine. Kibernetika i sistemnyj analiz. 2016. Vol. 52, N 3. P. 16–31.
- Lidl R., Niederreiter G. Finite Fields [Russian translation]. Moscow: World, 1988. 818 p.
- Blum A., Kalai A., Wasserman H. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM. 2003. Vol. 50, N 3. P. 506–519.
- Alekseychuk A.M. Sub-exponential algorithms for solving systems of linear Boolean equations with distorted right-hand sides. Prykladnaya radyoélektronyka. 2012. Vol. 11, N 2. P. 3–11.
- Bogos S., TramБr F., Vaudenay S. On solving LPN using BKW and variants. Implementation and analysis. Cryptology ePrint Archive, Report 2015/049. URL: http://eprint.iacr.org/2015/049.
- Alekseychuk A.M., Ignatenko S.M., Poremsky M.V. Systems of linear equations with distorted right-hand sides over finite rings. Matematychne ta kompʺyuterne modelyuvannya. Series: Technical Sciences. 2017. Iss. 15. P. 150–155.
- Wagner D. A generalized birthday problem. Advances in Cryptology — CRYPTO’02, Proceedings. Springer-Verlag, 2002. P. 288–303.
- Alekseychuk A.M., Poremsky M.V. The lower bounds of the information complexity of correlation attacks on stream ciphers above order fields. Zakhyst informatsiyi. 2017. Vol. 19, N 2. P. 119–124.
- Carlet C. Boolean functions for cryptography and error correcting codes. In: Boolean Methods and Models. Cambridge, U.K.: Cambridge Univ. Press, 2006.
- Daemen J. Cipher and hash function design strategies based on linear and differential cryptanalysis. Doctoral Dissertation, 1995.
- Logachev O.A., Salnikov A.A., Yaschenko V.V. Boolean functions in coding theory and cryptology [in Russian]. Moscow: ICNMO, 2004. 470 p.
