Statistical attack on combination keystream generators with irregular clocking
DOI:
https://doi.org/10.20535/2411-1031.2025.13.1.328762Keywords:
cryptographic information protection, combination keystream generators with irregular clocking, statistical attack, Walsh-Hadamard transform, A5/1, Alpha1Abstract
Combination keystream generators with irregular clocking are the basis for constructing of stream ciphers, the most famous of which are A5 and Alpha1. Each such generator consists of several binary linear feedback shift registers, a Boolean combination function, and a register clocking control unit that defines the rules by which registers are shifted in the process of keystream generating. Despite certain weaknesses of known stream ciphers based on combination keystream generators with irregular clocking, such generators still arouse theoretical and applied interest due to the simplicity of their structure and the potential ability to provide security to a wide class of attacks, provided that their components are properly selected. Combination keystream generators, each register of which is either shifted by one step or is idle in each clock cycle, with one of the registers clocking regularly, are investigated in the article. Previously, the authors of the article showed that the mentioned generators have an inherent weakness, which consists in statistical dependence between each neighboring signs of their output sequences. The main result of this article is a statistical attack based on the mentioned weakness. The proposed attack is aimed at restoring the initial state of the register clocking uniformly by a known output sequence of the generator or several such sequences produced by the generator in the chosen IV mode. It is shown that in the latter case the complexity of the attack depends linearly on the length of the mentioned register. An analytical bound of the amount of keystream required to implement the proposed attack with the required success probability is obtained. In particular, it is shown that for Alpha1 the corresponding amount is approximately 300 keystream frames along with their corresponding initialization vectors. Conditions that weaken the security of generators with irregular clocking against the proposed attack are formulated. They consist in the fact that the Walsh-Hadamard coefficients of the combination function take zero values on all vectors of weight 0 or 1 and non-zero values on certain vectors of weight 2. It is shown that these conditions are fulfilled for the keystream generator of Alpha1. In this case, the average amount of keystream required to recover the initial state of an arbitrary keystream generator that satisfies the above conditions is of the same order as for Alpha1.
References
J. Golic’, “Cryptanalysis of alleged A5 stream cipher”, in Proc. Advances in Cryptology – EUROCRYPT’97, Lecture Notes in Computer Science, vol 1233. Springer, Berlin, Heidelberg, 1997, pp. 239-255, doi: https://doi.org/10.1007/3-540-69053-0_17.
N. Komninos, B. Honary, and M. Darnell, “An Efficient Stream Cipher Alpha1 for Mobile and Wireless Devices”, in Cryptography and Coding, Lecture Notes in Computer Science, vol. 2260. Springer, Berlin, Heidelberg, 2001, pp. 294-300, doi: https://doi.org/10.1007/3-54045325-3_25.
P. Ekdahl, and T. Johansson, “Another attack on A5/1”, IEEE Trans. Inf. Theory, vol. 49, iss. 1, 2003, pp. 284-289, doi: https://doi.org/10.1109/tit.2002.806129.
A. Maximov, T. Johansson, and S. Babbage, “An Improved Correlation Attack on A5/1”, in Selected Areas in Cryptography – SAC 2004, Lecture Notes in Computer Science, vol. 3357. Springer, Berlin, Heidelberg, 2004, pp. 1-18, doi: https://doi.org/10.1007/978-3-540-30564-4_1.
A. Biryukov, A. Shamir, and D. Wagner, “Real Time Cryptanalysis of A5/1 on a PC”, in Fast Software Encryption, Springer, Berlin, Heidelberg, 2001, pp. 1-18, doi: https://doi.org/10.1007/3-540-44706-7_1.
E. Biham, and O. Dunkelman, “Cryptanalysis of the A5/1 GSM Stream Cipher”, in Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 2000, pp. 43-51, doi: https://doi.org/10.1007/3-540-44495-5_5.
T. Gendrullis, M. Novotný, A. Rupp, “A Real-World Attack Breaking A5/1 within Hours”, in Cryptographic Hardware and Embedded Systems – CHES 2008, Lecture Notes in Computer Science, vol 5154. Springer, Berlin, Heidelberg, 2008, pp. 266-282, doi: https://doi.org/10.1007/978-3-540-85053-3_17.
C. J. Mitchell, “Remarks on the security of the Alpha1 stream cipher”, Technical Report RHUL– MA–2001-8, 2001. [Online]. Available: https://www.academia.edu/55846558/Remarks_on_the_security_of_the_Alpha1_stream_cipher. Accessed on: Apr. 7, 2025.
Y. Xu, Y. Hao, and M. Wang, “Revisit Two Memoryless State-Recovery Cryptanalysis Methods on A5/1”, Cryptology ePrint Archive, Paper 2023/1557. [Online]. Available: https://ia.cr/2023/1557. Accessed on: Apr. 7, 2025.
A. Alekseychuk, and A. Matiyko, “Analytical expression of the probability of coincidence of adjacent signs of the output sequence of a combinational gamma generator built on the basis of shift registers moving with idle”, Cybernetics and Systems Analysis, vol. 61, iss. 2, pp. 27-32, 2025, doi: https://doi.org/10.34229/KCA2522-9664.25.2.3.
A. Alekseychuk, and R. Proskurovsky, “Lower bound of probability of distinguishing internal states of a combinatorial gamma generator with non-uniform motion”, Legal, normative and metrological support of the information protection system in Ukraine, iss. 2(13), pp. 159-169, 2006.
R. Proskurovsky, “Analytical evaluations of the effectiveness of the statistical method of cryptanalysis of a combinatorial gamma generator with non-uniform motion”, Coll. of scien. pap. of MITI NTUU “KPI”, no. 1, pp. 65-74, 2006.
A. Alekseychuk, R. Proskurovsky, and A. Shevtsov, “Analytical estimates and sufficient conditions for the stability of block ciphers and combinational gamma generators with nonuniform motion with respect to statistical cryptanalysis methods”, Applied Radio Electronics, vol. 6, iss. 2, pp. 264-273, 2007.
A. Alekseychuk, and R. Proskurovsky, “Estimation of the average error probability of the Bayesian criterion for hypothesis testing in the cryptanalysis problem of a combinatorial gamma generator with non-uniform motion”, Probability Theory and Mathematical Statistics, iss. 78, pp. 152-159, 2008.
H. Wu, “Cryptanalysis of Stream Cipher Alpha1”, in Information Security and Privacy, Springer, Berlin, Heidelberg, 2002, pp. 169-175, doi: https://doi.org/10.1007/3-540-454500_14.
K. Chen, L. Simpson, M. Henricksen, W. Millan and E. Dawson, “A Complete Divide and Conquer Attack on the Alpha1 Stream Cipher”, in Information Security and Cryptology – ICISC 2003, Springer, Berlin, Heidelberg, 2004, pp. 418-431, doi: https://doi.org/10.1007/978-3-54024691-6_31.
A. Alekseychuk, and О. Kurinnyi, Methods of cryptanalysis of stream ciphers. Educational edition. Kyiv, Ukraine: Igor Sikorsky Kyiv Polytechnic Institute, 2023. [Online]. Available: https://ela.kpi.ua/server/api/core/bitstreams/a16bc1db-07a3-4d38-b9e7-a331ef2cc111/content.Accessed on: Apr. 7, 2025.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Collection "Information Technology and Security"
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors that are published in this collection, agree to the following terms:
- The authors reserve the right to authorship of their work and pass the collection right of first publication this work is licensed under the Creative Commons Attribution License, which allows others to freely distribute the published work with the obligatory reference to the authors of the original work and the first publication of the work in this collection.
- The authors have the right to conclude an agreement on exclusive distribution of the work in the form in which it was published this anthology (for example, to place the work in a digital repository institution or to publish in the structure of the monograph), provided that references to the first publication of the work in this collection.
- Policy of the journal allows and encourages the placement of authors on the Internet (for example, in storage facilities or on personal web sites) the manuscript of the work, prior to the submission of the manuscript to the editor, and during its editorial processing, as it contributes to productive scientific discussion and positive effect on the efficiency and dynamics of citations of published work (see The Effect of Open Access).
