Scalable Method of Searching for Full-period Nonlinear Feedback Shift Registers with GPGPU : New List of Maximum Period NLFSRs

• Autorzy: Augustynowicz P. , Kanciak K.

Identyfikatory

DOI

10.24425/119365

• Języki publikacji: EN

Abstrakty

EN

This paper addresses the problem of efficient searching for Nonlinear Feedback Shift Registers (NLFSRs) with a guaranteed full period. The maximum possible period for an n-bit NLFSR is 2ⁿ - 1 (an all-zero state is omitted). A multi-stages hybrid algorithm which utilizes Graphics Processor Units (GPU) power was developed for processing data-parallel throughput computation. Usage of the abovementioned algorithm allows giving an extended list of n-bit NLFSR with maximum period for 7 cryptographically applicable types of feedback functions.

Słowa kluczowe

EN

NLFSR; GPGPU; CUDA; nonlinear feedback shift registers; de Bruijn sequences

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2018
• Tom: Vol. 64, No. 2
• Strony: 167--171
• Opis fizyczny: Bibliogr. 18 poz., rys., wykr.

Twórcy

autor

Augustynowicz P.

• Faculty of Cybernetics, Military University of Technology, Warsaw, Poland

autor

Kanciak K.

• Faculty of Cybernetics, Military University of Technology, Warsaw, Poland

Bibliografia

• [1] J.-P. Aumasson, L. Henzen, W. Meier, and M. Naya-Plasencia, “Quark: A lightweight hash,” in Proceedings of the 12th International Conference on Cryptographic Hardware and Embedded Systems, ser. CHES’10. Berlin, Heidelberg: Springer-Verlag, 2010, pp. 1-15. [Online]. Available: http://dl.acm.org/citation.cfm?id=1881511.1881513
• [2] M. Hell, T. Johansson, and W. Meier, “Grain: a stream cipher for constrained environments,” Int. J. Wire. Mob. Comput., vol. 2, no. 1, pp. 86-93, may 2007. [Online]. Available: http://dx.doi.org/10.1504/IJWMC.2007.013798
• [3] H. H. Vahid Amin Ghafari and Y. Chen, “Fruit-v2: Ultra-lightweight stream cipher with shorter internal state,” 2016. [Online]. Available: http://eprint.iacr.org/2016/355
• [4] S. Golomb, Shift Register Sequences, 1967, portions co-authored with Lloyd R. Welch, Richard M. Goldstein, and Alfred W. Hales.
• [5] A. Canteaut, “Open problems related to algebraic attacks on stream ciphers,” in Proceedings of the 2005 International Conference on Coding and Cryptography, ser. WCC’05. Berlin, Heidelberg: Springer-Verlag, 2006, pp. 120-134. [Online]. Available: http://dx.doi.org/10.1007/11779360 10
• [6] H. Zhang and X. Wang, “Cryptanalysis of stream cipher Grain family,” 2009. [Online]. Available: http://eprint.iacr.org/2009/109.
• [7] C. D. Canniere and B. Preneel, “Trivium specifications,” eSTREAM, ECRYPT Stream Cipher Project, vol. 2006.
• [8] B. M. Gammel, R. Gottfert, and O. Kniffler, “The achterbahn stream cipher,” 2005.
• [9] C. De Canniѐre, O. Dunkelman, and M. Knežević, KATAN and KTANTAN - A Family of Small and Efficient Hardware-Oriented Block Ciphers. Springer Berlin, 2009.
• [10] N. T. Courtois and W. Meier, Algebraic Attacks on Stream Ciphers with Linear Feedback. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003, pp. 345-359.
• [11] P. Dabrowski, G. Labuzek, T. Rachwalik, and J. Szmidt, “Searching for nonlinear feedback shift registers with parallel computing,” 2013.
• [12] E. Dubrova, “A scalable method for constructing galois NLFSRs with period 2ⁿ - 1 using cross-join pairs,” 2011. [Online]. Available: http://eprint.iacr.org/2011/632
• [13] T. Rachwalik, J. Szmidt, R. Wicik, and J. Zablocki, “Generation of nonlinear feedback shift registers with special-purpose hardware,” 2012. [Online]. Available: http://eprint.iacr.org/2012/314
• [14] N. Poluyanenko, “Development of the search method for non-linear shift registers using hardware implemented on field programmable gate arrays,” 2017.
• [15] E. Dubrova, “Generation of full cycles by a composition of nlfsrs,” Des. Codes Cryptography, vol. 73, no. 2, pp. 469-486, nov 2014. [Online]. Available: http://dx.doi.org/10.1007/s10623-014-9947-3
• [16] CURAND Library: Programming Guide, Version 7.0, NVIDIA, 2015. [Online]. Available: http://docs.nvidia.com/cuda/curand
• [17] M. Afzal and A. Masood, “Algebraic cryptanalysis of a nlfsr based stream cipher,” in 2008 3rd International Conference on Information and Communication Technologies: From Theory to Applications, 4 2008, pp. 1-6.
• [18] E. Dubrova, “A list of maximum period NLFSRs,” 2012.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).