Design and Implementation of a Statistical Testing Framework for a Lightweight Stream Cipher

A. Alamer, B. Soh


The Shrinking Generator (SG) is a popular synchronous, lightweight stream cipher that uses minimal computing power. However, its strengths and weaknesses have not been studied in detail. This paper proposes a statistical testing framework to assess attacks on the SG. The framework consists of a d-monomial test that is adapted to SG by applying the algebraic normal form (ANF) representation of Boolean functions, a test that uses the maximal degree monomial test to determine whether the ANF follows the proper mixing of bit values, and a proposed unique window size (UWS) scheme to test the randomness properties of the keystream. The proposed framework shows significant weaknesses in the SG output in terms of dependence between the controlling linear-feedback shift register (LFSR) and non-linearity of the resulting keystream. The maximal degree monomial test provides a better understanding of the optimal points of SG, demonstrating when it is at its best and worst according to the first couple of results. This paper uses UWS to illustrate the effect of the LFSR choice on possibly distinguishing attacks on the SG. The results confirm that the proposed UWS scheme is a viable measure of the cryptographic strength of a stream cipher. Due to the importance of predictability and effective tools, we used neural network models to simulate the input data for the pseudo-random binary sequences. Through the calculation of UWS, we obtained solid results for the predictions.


stream ciphers; randomness testing; shrinking generator; cryptanalysis

Full Text:



C. Paar, J. Pelzl, Understanding Cryptography: a textbook for students and practitioners, Springer Science & Business Media, 2009

A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of applied cryptography, CRC Press, 1996

W. Meier, O. Staffelbach, “The self-shrinking generator”, in: Communications and Cryptography, Springer, 1994

S. D. Cardell, A. Fuster-Sabater, “Cryptanalysing the shrinking generator”, International Conference on Computational Science, Reykjavík, Iceland, June 1-3, 2015

D. Maimut, K. Ouafi, “Lightweight cryptography for RFID tags”, IEEE Security & Privacy, Vol. 10, No. 2, pp. 76-79, 2012

P. Caballero-Gil, A. Fuster-Sabater, M. E. Pazo-Robles, “New attack strategy for the shrinking generator”, Journal of Research and Practice in Information Technology, Vol. 41, No. 2, 2009

D. Coppersmith, H. Krawczyk, Y. Mansour, “The shrinking generator”, 13th Annual International Cryptology Conference on Advances in Cryptology, Berlin, Germany, August 22-26, 1993

J. D. Golic, “Towards fast correlation attacks on irregularly clocked shift registers”, International Conference on the Theory and Applications of Cryptographic Techniques, Saint-Malo, France, May 21-25, 1995

L. Simpson, J. D. Golic, E. Dawson, “A probabilistic correlation attack on the shrinking generator”, Information Security and Privacy, 3rd Australasian Conference, Brisbane, Queensland, Australia, June 21, 1998

B. Zhang, H. Wu, D. Feng, F. Bao, “A fast correlation attack on the shrinking generator”, Topics in Cryptology-CT-RSA 2005, The Cryptographers’ Track at the RSA Conference, San Francisco, CA, USA, February 14-18, 2005

A. H. Al-Omari, “Lightweight dynamic crypto algorithm for next internet generation”, Engineering, Technology & Applied Science Research, Vol. 9, No. 3, pp. 4203-4208, 2019

E. Filiol, “A new statistical testing for symmetric ciphers and hash functions”, 4th International Conference on Information and Communications Security, London, UK, December 9-12, 2002

M. J. O. Saarinen, Chosen-IV statistical attacks on eSTREAM stream ciphers, eSTREAM, ECRYPT Stream Cipher Project, Report 2006/013, 2006

H. Englund, T. Johansson, M. S. Turan, “A framework for chosen IV statistical analysis of stream ciphers”, 8th International Conference on Progress in Cryptology, Berlin, Germany, December 9-13, 2007

S. Boztas, A. Alamer, “Statistical dependencies in the self-shrinking generator”, 7th International Workshop on Signal Design and its Applications in Communications, Piscataway, USA, September 14-18, 2015

D. Erdmann, S. Murphy, “An approximate distribution for the maximum order complexity”, Designs, Codes and Cryptography, Vol. 10, No. 3, pp. 325-339, 1997

C. J. A. Jansen, D. E. Boekee, “Modes of blockcipher algorithms and their protection against active eavesdropping”, Workshop on the Theory and Application of Cryptographic Techniques EUROCRYPT 1987, Amsterdam, The Netherlands, April 13-15, 1987

K. Gurney, An Introduction to Neural Networks, CRC Press, 2014

S. S. Baboo, I. K. Shereef, “An efficient weather forecasting system using artificial neural network”, International Journal of Environmental Science and Development, Vol. 1, No. 4, pp. 321-326, 2010

E. Guresen, G. Kayakutlu, T. U. Daim, “Using artificial neural network models in stock market index prediction”, Expert Systems with Applications, Vol. 38, No. 8, pp. 10389-10397, 2011

B. Gold, N. Morgan, D. Ellis, Speech and audio signal processing: Processing and perception of speech and music, John Wiley & Sons, 2011

A. Esteva, B. Kuprel, R. A. Novoa, J. Ko, S. M. Swetter, H. M. Blau, S. Thrun, “Dermatologist-level classification of skin cancer with deep neural networks”, Nature, Vol. 542, No. 7639, pp. 115-118, 2017

A. Klimov, A. Mityagin, A. Shamir, “Analysis of neural cryptography”, International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1-5, 2002

L. B. Salah, F. Fourati, “Systems modeling using deep Elman neural network”, Engineering, Technology & Applied Science Research, Vol. 9, No. 2, pp. 3881-3886, 2019

W. Kinzel, I. Kanter, “Interacting neural networks and cryptography”, in: Advances in solid state physics, Springer, 2002

T. Godhavari, N. Alamelu, R. Soundararajan, “Cryptography using neural network”, 2005 Annual IEEE India Conference - Indicon, Chennai, India, December 11-13, 2005

E. Volna, M. Kotyrba, V. Kocian, M. Janosek, “Cryptography based on neural network”, ECMS 2012, Koblenz, Germany, May 29-June 1, 2012

A. El-Zoghabi, A. H. Yassin, H. H. Hussien, “Survey report on cryptography based on neural network”, International Journal of Emerging Technology and Advanced Engineering, Vol. 3, No. 12, pp. 456-462, 2013

R. J. Rasras, Z. A. AlQadi, M. R. A. Sara, “A methodology based on steganography and cryptography to protect highly secure messages”, Engineering, Technology & Applied Science Research, Vol. 9, No. 1, pp. 3681-3684, 2019

W. Diffie, M. E. Hellman, “New Directions in Cryptography”, IEEE Transactions on Information Theory, Vol. 22, No. 6, pp. 644-654, 1976

eISSN: 1792-8036     pISSN: 2241-4487