Full Paper View

 

LFSR Next Bit Prediction through Deep Learning

Sanchit Gupta, Priyansh Singh, Noopur Shrotriya, Tanvi Baweja
Research Paper | Journal Paper
Volume 2 , Issue 2: Special Issue on Artificial Intelligence (ICAI-2021) , PP 1-9
DOI: https://doi.org/10.54060/JIEEE/002.02.022

Abstract

Pseudorandom bit sequences are generated using deterministic algorithms to simulate truly random sequences. Many cryptographic algorithms use pseudorandom sequences and the randomness of these sequences greatly impacts the robustness of these algorithms. Important crypto primitive Linear Feedback Shift Register (LFSR) and its combinations have long been used in stream ciphers for the generation of pseudorandom bit sequences. The sequences generated by LFSR can be predicted using the traditional Berlekamp Massey Algorithm, which solves LFSR in 2√ón number of bits, where n is the degree of LFSR. Many different techniques based on ML classifiers have been successful at predicting the next bit of the sequences generated by LFSR. However, the main limitation in the existing approaches is that they require a large number (as compared to the degree of LFSR) of bits to solve the LFSR. In this paper, we have proposed a novel Pattern Duplication technique that exponentially reduces the input bits requirement for training the ML Model. This Pattern Duplication technique generates new samples from the available data using two properties of the XOR function used in LFSRs. We have used the Deep Neural Networks (DNN) as the next bit predictor of the sequences generated by LFSR along with the Pattern Duplication technique. Due to the Pattern Duplication technique, we need a very small number of input patterns for DNN. Moreover, in some cases, the DNN model managed to predict LFSRs in less than 2n bits as compared to the Berlekamp Massey Algorithm. However, this technique was not successful in cases where LFSRs have primitive polynomials with a higher number of tap points.

Key-Words / Index Term

Linear Feedback Shift Register (LFSR); Multilayer Perceptron (MLP); Deep Neural Net-works (DNN); Next bit prediction

References

  1. Menezes, P. van Oorschot, and S.Vanstone (1996). Handbook of Applied Cryptography, CRC Press.
  2. C. Hernandez, J. M. Sierra, C. Mex-Perera, D. Borrajo, A. Ribagorda, P. Isasi (2000). Using the General Next Bit Predictor Like an Evaluation Criteria. proceedings of NESSIE workshop Leuven, Belgium.
  3. S. Khan (2004). Classificatory Prediction and Primitive Polynomial Construction of Linear Feedback Shift Registers using Decision Tree Approach. KBCS-2004, fifth International Conference On Knowledge Based Computer Systems.
  4. Kant and S. S. Khan (2006), "Analyzing a Class of Pseudo-random Bit Generator through Inductive Machine Learning Paradigm", Int. J. Intelligent Data Analysis, Vol. 10, NO.6, pp 539-554.
  5. Shri Kant, Naveen Kumar, Sanchit Gupta, Amit Singhal, Rachit Dhasmana (2009). International Conference on Methods and Models in Computer Science, 2009 “Impact of Machine Learning Algorithms on Analysis of Stream Ciphers”
  6. Tom Mitchell (1997). Machine Learning, McGraw Hill.
  7. Casey, Erin (2000). Berlekamp-Massey Algorithm. REU Summer Report, University of Minnesota, Minneapolis, MN.
  8. Watson, E. J. (1962). Primitive polynomials (????????????2). Mathematics of Computation 16.79: 368-369.
  9. Lin, (1995). Shift and add' property of m-sequences and its application to channel characterisation of digital magnetic recording, in IEE Proceedings - Communications, vol. 142, no. 3, pp. 135-140, June 1995, doi: 10.1049/ip-com:19951842.