UDC 519.7
1 National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine
 alex-dtn@ukr.net
|
2 Institute of Special Communication and Information Security of the 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
|
|
UPPER BOUNDS FOR IMBALANCE OF DISCRETE FUNCTIONS REALIZED BY SEQUENCES
OF FINITE-STATE MACHINES
Abstract. A matrix representation and upper bounds of the imbalance of an arbitrary discrete function realized by a sequence of finite-state machines are obtained. The obtained results generalize a number of previously known assertions about matrix (linear) representations of the imbalance of the special form functions and can be used to solve the problems of security proofs of stream or block ciphers against a number of statistical attacks.
Keywords: correlation cryptanalysis, imbalance of discrete function, finite-state machine, addition modulo 2n operation, SNOW 2.0, «Strumok».
FULL TEXT
REFERENCES
- Staffelbach O., Meier W. Cryptographic significance of the carry for ciphers based on integer addition. In: Advances in Cryptology-CRYPTO’90. LNCS. 1991. Vol. 537. P. 601–615.
- Sherstnev V.I. The joint distribution of hyphenation when adding integers. Probability Theory and Its Applications. 1996. Vol. 91(2). P. 467–473.
- Walln J. Linear approximation of addition modulo . In: Fast Software Encryption. FSE 2003. LNCS. 2003. Vol. 2887. P. 261–273.
- Lipmaa H., Moriai S. Efficient algorithms for computing differential properties of addition. In: Fast Software Encryption. FSE 2001. LNCS. 2002. Vol. 2355. P. 336–350.
- Lipmaa H., WallБn J., Dumas P. On the additive differential probability of exlusive-or. In: Fast Software Encryption. FSE 2004. LNCS. 2004. Vol. 3017. P. 317–331.
- Lipmaa H. On differential properties of pseudo-hadamard transform and related mappings. In: Progress in Cryptology-INDOCRYPT 2002. LNCS. 2002. Vol. 2551. P. 48–61.
- Kovalchuk L.V., Sirenko O.A. Analysis of the mixing properties of modular and bitwise operations defined on the same media. Kibernetika i sistemnyj analiz. 2011. Vol. 47, N 5. P. 83–97.
- Alekseychuk A.N., Kovalchuk L.V. Upper bounds of maximum values of average differential and linear characteristic probabilities of Feistel cipher with adder modulo . Theory of Stochastic Processes. 2006. Vol. 12(28), N 1–2. P. 20–32.
- 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.
- Alekseychuk A.N., Kovalchuk L.V. Towards a theory of security evaluation for GOST-like ciphers against differential and linear cryptanalysis. Cryptology ePrint Archive, Report 2011/489. URL: http://eprint.iacr.org/2011/489.
- Kovalchuk L.V., Bezdetny V.T. Upper bounds for the average probabilities of difference characteristics of block ciphers with alternating Markov and generalized Markov transformations. Kibernetika i sistemnyj analiz. 2014. Vol. 50, N 3. P. 71–78.
- Watanabe D., Biryukov A., de Cannire C. A distinguishing attack of SNOW 2.0 with linear masking method. In: Selected Arreas in Cryptography. SAC 2003. LNCS. 2003. Vol. 3006. P. 222–233.
- Nyberg K., Walln J. Improved linear distinguishers for SNOW 2.0. In: Fast Software Encryption. FSE 2006. LNCS. 2006. Vol. 4047. P. 144–162.
- Maximov A., Johansson Th. Fast computation for large distribution and and its cryptographic application. In: Advanced in Cryptology-ASIACRYPT 2005. LNCS. 2005. Vol. 3788. P. 313–332.
- Lee J.-K., Lee D.H., Park S. Cryptanalysis of SOSEMANUC and SNOW 2.0 using linear masks. In: Advanced in Cryptology-ASIACRYPT 2008. LNCS. 2008. Vol. 5350. 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.
- Ekdahl P., Johansson T. A new version of the stream cipher SNOW. In: Selected Areas in Cryptography. SAC 2002. LNCS. 2002. Vol. 2295. P. 47–61.
- 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.
- Zhukov A.E., Chistyakov V.P. Matrix approach to the study of the pre-images of the output sequence of a finite state machine. Obozreniye prikl. promyshl. matem. 1994. Vol. 1, Iss. 1. P. 108–117.
