DOI
10.34229/KCA2522-9664.25.2.3
UDC 004.056:519.2
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
alexm1710@ukr.net
|
ANALYTICAL EXPRESSION OF THE PROBABILITY OF ADJACENT SIGNS’
COINCIDENCE OF THE OUTPUT SEQUENCE OF A COMBINATION
KEYSTREAMGENERATOR BASED ON SHIFT REGISTERS MOVING WITH IDLE
Abstract. A theorem that establishes an explicit expression of the probability of two adjacent signs’ coincidence of the output sequence of an arbitrary combination keystream generator based on linear shift registers, each of which is either idle or shifts by one step in each clock cycle is proved. The obtained result allows us to calculate this probability directly from the known laws of the linear shift registers’ motion and the Walsh–Hadamard transform of the combination function.
Keywords: stream cipher, combinational gamma generator with non-uniform motion, correlation attack, Walsh–Hadamard transform, A5/1, Alpha1.
full text
REFERENCES
- 1. Goli J. Cryptanalysis of alleged A5 stream cipher. Proc. 16th annual international conference on Theory and application of cryptographic techniques (EUROCRYPT’97) 11–15 May 1997, Konstanz, Germany). Konstanz, 1997. P. 239–255. https://apps.dtic.mi/ .
- 2. Komninos N., Honary B., Darnell M. An efficient stream cipher Alpha1 for mobile and wireless devices. Proc. 8th IMA International Conference on Cryptography and Coding (17–19 December 2001, Cirencester, UK). Cirencester, 2001. LNCS. 2001. Vol. 2260. P. 294–300. https://doi.org/10.1007/ .
- 3. Ekdahl P., Johansson T. Another attack on A5/1. IEEE Transactions on Information Theory. 2003. Vol. 49, Iss. 1. P. 284–289. https://doi.org/10.1109/ .
- 4. Maximov A., Johansson T., Babbage S. An improved correlation attack on A5/1. Proc. 11th International Workshop (SAC 2004) (9–10 August 2004, Canada). Waterloo, 2004. LNCS. 2005. Vol. 3357. P. 1–18. https://doi.org/10.1007/ .
- 5. Alekseychuk A., Proskurovsky R. Lower bound of probability of distinguishing internal states of a combining gamma generator with non-uniform motion. Legal, regulatory and metrological support for the information protection system in Ukraine. 2006. Iss. 2(13). P. 159–169. https://ela.kpi.ua/ .
- 6. Proskurovsky R.V. Analytical evaluations of the effectiveness of the statistical method of cryptanalysis of a combinatorial gamma generator with non-uniform motion. Collection of scientific works of VITI NTUU “KPI”. 2006. N 1. P. 65–74.
- 7. Oleksiychuk A.M., Proskurovsky R.V., Shevtsov A.S. Analytical estimates and sufficient conditions for the stability of block ciphers and combinational gamma generators with non-uniform motion with respect to statistical cryptanalysis methods. Prykladna radioelektronika. 2007. Vol. 6, N 2. P. 264–273.
- 8. Oleksiychuk A.M., Proskurovsky R.V. Estimation of the average probability of error of the Bayesian criterion for testing hypotheses in the problem of cryptanalysis of a combinatorial gamma generator with non-uniform motion. Teoriya ymovirnostey ta matematychna statystyka. 2008. Iss. 78.P. 152–159. https://probability.knu.ua:tims/ .
- 9. Mitchell C.J. Remarks on the security of the Alpha1 stream cipher. Technical Report RHUL–MA–2001–8. 2001. 7 p. https://www.researchgate.net/ .
- 10. Wu H. Cryptanalysis of stream cipher Alpha1. Proc. 7th Australasian Conference on Information Security and Privacy (ACISP 2002) (3–5 July 2002, Australia). Melbourne, 2002. LNCS. Vol. 2384. 2002. P. 169–175. https://doi.org/10.1007/ .
- 11. Chen K., Simpson L., Henricksen M., Millan W., Dawson E. A complete divide and conquer attack on the Alpha1 stream cipher. Proc. 6th International Conference on Information Security and Cryptology (ICISC 2003) (27-28 November 2003, Korea). Seoul, 2003. LNCS. 2004. Vol. 2971. P. 418–431. https://doi.org/10.1007/ .
- 12. Xu Y., Hao Y., Wang M. Revisit two memoryless state-recovery cryptanalysis methods on A5/1. IET Information Security. 2023. P. 626–638. https://doi.org/10.1049/ .
- 13. Carlet C. Boolean functions for cryptography and error correcting codes. In: Boolean models and methods in mathematics, computer science, and engineering. Encyclopedia of mathematics and applications. Cambridge University Press, 2010. P. 257–397. https://doi.org/10.1017/ .
