Design of Modified Exclusive-128 Bit NLFSR Stream Cipher and Randomness Test

International Journal of Computer Applications (0975 – 8887) Volume 91 – No.12, April 2014 Design of Modified Exclusive-128 Bit NLFSR Stream Cipher and Randomness Test K. Rajam I. Raja Mohamed K.J. Jegadish Kumar B.S. AbdurRahman University B.S.AbdurRahman University S.S.N. College of Engineering Chennai – 600 048 Chennai – 600 048 Chennai – 603110 India India India ABSTRACT The study of cryptanalysis method in analysing information In this paper, we describe modified Exclusive-128 NLFSR system (encrypted) is to study the hidden aspects of the stream cipher which generates 128 bit keystreams using only system andto finda secret key [3]. The most common NLFSR element as its main function and XOR operation. It cryptanalysis attacks are: (1) Brute force attacks, (2) consists of different sizes of NLFSRs both in Fibonacci and Algebraic attacks and (3) Linear attacks.Brute force attack is a Galois configurations which offer better trade off between the strategy that involves systematically checking all possible algorithm security and hardware capability. Further, using keys until the correct key is found. The key length used in the this modified version of Exclusive-128 NLFSR stream cipher, encryption determines the practical feasibility of performing a analysis has been done for pseudorandom test to prove that brute-force attack, with longer keys are exponentially more this stream cipher is highly non-linear and truly randomness difficult to crack than shorter ones. when all the initial key inputs are either zero and/or one. Table 1.Key size (vs) Brute Force Time estimation Keyword Key Cryptography, Stream cipher, NLFSR, Fibonacci Permutations Brute Force Time Size configuration, Galois configuration, NIST Randomness Test. 8 8 2 0 milliseconds 1. INTRODUCTION 40 2 40 0.015 milliseconds Cryptography is a technique that is used to protect information 56 256 1 second confidentially from unauthorised person and is associated with 56 secrecy, authentication and integrity. Cryptographic systems 64 2 4 minutes 16 seconds are classified as secret key (Symmetric) cryptosystems and 128 2128 149,745,258,842,898 years public key (Asymmetric) cryptosystems. In secret key cryptosystems, a single key is used for both encryption of the The table 1 shows that the Key size verses Brute Force time plaintext and decryption of the ciphertext. In public key estimation of exhaustive key search attack. A key size of 8, cryptosystem, two different keys are used to transform a 40, 56, 64 bit can be attacked and cracked easily through message into an unreadable form, decryptable only by using Brute Force attack cryptanalysis since the number of adifferent but matching private key. permutations and also the Brute Force time is considerably Symmetric cryptosystems are further classified as block very less compared to 128 bit key size[4]. ciphers and stream ciphers. Block ciphers are memoryless The hardware implementationismainly used in providing the algorithms that permute N-bit blocks of plaintext data under security needed for various cryptographic applications. Some the influence of the secret key and generate N-bit blocks of of the stream cipher using NLFSRs to generate random encrypted data. Stream ciphers containinternal states of key sequences are GRAIN[5] and VEST[6]. Grain stream and a shift register operate serially by generating a cipherusestwo types of shift registers, Non Linear Feedback pseudorandom bit and bitwise XORed with the data for Shift Register (NLFSR)andFeedback with Carry Shift encryption/decryption. Stream ciphers have no standard model Registers (FCSR).The NLFSRs are generally used to for their construction design, which leads cryptographers to eliminate and destroy the linearity found in LFSRs. The construct various models for stream cipher. It is totally NLFSR design applies a non-linear function in the shift different from block ciphers. register to ensure the non-linearity in the output values from Stream ciphers belong to the family of symmetric key ciphers the corresponding shift register. Several stream cipher thatare important in securing streaming information.The designs useNLFSR, and one such stream cipher is the Grain stream ciphers are classified into three main categories [1] stream cipher. It was developed in 2004 and submitted to hardwarebased stream ciphers, softwarebased stream ciphers eSTREAM project for evaluation in 2005[5]. However, Grain and hybrid designs of stream ciphers. The hardwarebased was attacked in 2006 by two different cryptanalysis as stream cipher includes Feedback Carry Shift Register (FCSR) reported byMaximov, 2006 and Kucuk,2006.Some method of / Non Linear Feedback Shift Register (NLFSR) based stream transforming LFSRs to NLFSR are clock controlled generator cipher, Clock Control based stream cipher and Linear and stop and go generators [2]. Feedback Shift Register(LFSR) [2]based stream ciphers.Stream ciphers do not affectthe error propagation, as in the block ones, because each bit is independently encrypted/decrypted from any other. The stream cipherfeatures have been used for several communication protocols, especially wireless ones, like Bluetooth. 32 International Journal of Computer Applications (0975 – 8887) Volume 91 – No.12, April 2014 2. IMPLEMENTATION OF THE The circuits in which number ofcomponents required for implementing feedback functions of individual bits is STREAM CIPHER usually smaller than the circuits implementing the As discussed in the previous section, a stream cipher is a feedback function of the Fibonacci NLFSR, and the symmetric key cipher where plaintext digits are combined propagation time can potentially be reduced [8]. with a pseudorandom cipher digit stream (keystream). In this stream cipher each plaintext digit is encrypted one at a time This makes Galois NLFSRs attractive for stream cipher with the corresponding digit of the key stream, to give a digit applications in which high key stream generation speed is of the ciphertext stream. The pseudorandom key-stream is important. typically generated serially from a random seed value using The proposed stream cipher is a 128 bit stream cipher which digital shift registers. The seed value serves as the generates 128 bit key stream. The 128 bit key stream is cryptographic key for decrypting the ciphertext stream. A XORed with the plaintext to produce the ciphertext. The 128 stream cipher generates successive elements of the key stream bit key stream is produced using six non-linear feedback shift based on an internal state. This state is updated essentially in registers each used in either Fibonacci or Galois two ways: either the state changes independently the plaintext configuration. The idea of implementing this new modified or ciphertext messages. By contrast, self-synchronizing stream stream cipher is adopted from the A5/1 and modified A5/1 ciphers update their state based on previous ciphertext digits. stream ciphers [9]. The A5/1 stream cipher is modified by Shift Registers are nothing but a simple register which shifts adding a few shift registers to the existing ones and changing the values and employs some functions to update its bits. the feedback functions so as to make it more secure and less Generally a shift register is a cascade of flip-flops, sharing the susceptible to attacks. Since our proposed stream cipher is same clock, which has the output of anyone but the last flip- constructed by adding more number of variant sizes of flop connected to the "data" input of the next one in the chain, NLFSRs,it is more secure specifically resistant to linear resulting in a circuit that shifts by one position the one- cryptanalysis. dimensional "bit array" stored in it. The shifting in the data Fig.3 shows internal view of Exclusive-128 bit NLFSR stream present at its input and shifting out the last bit in the array, is cipher.The Exclusive-128 NLFSR stream cipher generates a done at the transition of the clock input. Shift registers can 128 bit keystream and this string valuesare used as a seed have both parallel and serial inputs and outputs. These are value for each NLFSR shift register. The choice of the often configured as Serial-In Parallel-Out (SIPO) or Parallel- feedback function of different lengths 32bit, 31bit, 25 bit, 4 bit In Serial-Out (PISO). In order to improve the non-linearity of NLFSR configuration is based on the function non linearity shift registers, a feedback function with a definite feedback that generates truly random sequences[2,4]. polynomial is used. A linear feedback shift register (LFSR) is a shift registerwhose input bit is a linear function of its previous state. Mostly used linear function of single bits is XOR, thus normally it is a shift register whose input bit is driven by XOR of some bits of the overall shift register value. Three methods of implementing NLFSR namely(a) Simple configuration, (b) Fibonacci configuration and (c) Galois configuration are discussed below. 1. In a simple configuration, XNOR gates are used as feedback function. 2. In Fibonacci configuration, feedback is applied only to the last bit.It is a Non-linear combination of taps to produce long periodic states [7] as shown in fig.1. Feedback function n–1 n–2 n–3 0 Output Figure 3: Internal view of Exclusive-128 bit NLFSRstream Figure1: Fibonacci configuration cipher[2] 3. In Galois configuration, feedback is applied to each and every bit [7] as shown in fig.2. The feedback functions of each NLFSR are described as follows. A detailed description can be found in the literature[2,10]. 32 bit Fibonacci non-linear feedback function is defined as f31 = X0 ⊕ X2⊕ X6 ⊕ X7 ⊕ X12 ⊕ X17 ⊕ X20 ⊕X27 ⊕ X30 fn – 1 n–1 fn – 2 n–2 f0 0 ⊕ X3X9 ⊕ X12X15⊕X4X5X16. Output The corresponding feedback functions of 32 bit Galois Figure 2: Galois configuration configuration are In the Galois type of NLFSR each bit i isupdated f29 = X30⊕ X0 according to its own feedback function. f28 = X29⊕ X0X6 f27 = X28⊕ X0X1X12 33 International Journal of Computer Applications (0975 – 8887) Volume 91 – No.12, April 2014 f25 = X26⊕ X0 32 Bit NLFSR Fibonacci f24 = X25⊕ X0 f19 = X20⊕ X0⊕ X0X3 31 Bit NLFSR Galois f14 = X15⊕ X0 f12 = X13⊕ X1⊕ X8⊕ X11 25 Bit NLFSR Fibonacci 31 bit Galois non-linear feedback function is defined as Initial Key 128 Bit Seed f30= X0⊕ X3⊕ X5⊕ X7⊕ X10⊕ X16⊕ X17⊕ X18⊕ X19⊕ X20⊕ X21⊕ X24⊕ X30⊕ X5 X15⊕ X11X18⊕ X16X22⊕ X17X21⊕ X1X2X19⊕ X1X12X14X17⊕ X2X5X13X20. 32 Bit NLFSR Galois The corresponding feedback functions of 31 bit Galois 4 Bit NLFSR Fibonacci configuration are 4 Bit NLFSR Galois f28 = X29 ⊕ X0X3X11X18 128 f29 = X30⊕ X0X11X13⊕ X0X1X18 f27 = X28 ⊕ X0 Plain Text/Cipher Text (128 Bit) f25 = X26 ⊕ X0X10 ⊕ X0 f23 = X24 ⊕ X0 f20 = X21 ⊕ X0 f19 = X20 ⊕ X0X7 Plain Text/Cipher Text (128 Bit) f18 = X19 ⊕ X5X9 ⊕ X4X10 ⊕ X18 ⊕ X12 ⊕X9 ⊕ X8 ⊕ X7 ⊕ X6 ⊕ X5 ⊕ X4 Figure 4: Internal view of modified Exclusive-128 bit 25 bit Fibonacci non-linear feedback function is defined as NLFSR stream cipher f24 = X0 ⊕ X1⊕ X3⊕ X5⊕ X6⊕ X7⊕ X9 ⊕ X 12⊕ X14⊕ The architecture of modified Exclusive-128 bit Nonlinear X15 ⊕X 17⊕ X18⊕ X22⊕X1X6⊕ X4X13⊕ X8X16⊕ X12X15⊕ Feedback Shift Register based stream cipher is shown in X5X11X14⊕ X1X4X11X15⊕ X2X5X8X10 figure (4),which is to enhance randomness. In this modified stream cipher, each configuration of NLFSR is arranged 4 bit Fibonacci non-linear feedback function is defined as alternately, and their initial state is the seed value which is the complement of the initial key using an interleaver. An f3= X0 ⊕X1X30 interlever is used to separates the odd and even bits in a given 4 bit Galois non-linear feedback function is defined as binary sequence. f2=X3⊕ X0X2 3. RANDOM NUMBER TESTING The first 32 bits of this string is assigned to the 32 bit non- In this section, we discuss the analysis of randomness test for linear feedback shift register used in Fibonacci configuration the pseudorandom number generators. In many cryptographic and the next 31 bits are given to the 31 bit non-linear feedback applications,generators are used to generate random sequences shift register used in Fibonacci mode. Similarly the next bits and may need to meet stronger than for other applications. are assigned to each of the other registers used. The stream These generators are classified as random number cipher is implemented in such a way that each configuration is generators(RNG) and pseudorandom number generators sandwichedbetween the other two configurations either the (PRNG), both these produce a stream of zeros and ones that Fibonacci or the Galois configuration. The variant size of each may be divided into substreams or blocks of random numbers. configuration is 32 bitFibonacci, 31 bit Galois, 25 bit The outputs of such generators may be used to determine Fibonacci, 32 bit Galois, 4 bit Fibonacci and 4 bit Galois whether or not a generator is suitable for a particular NLFSRs. cryptographic application. However, no set of statistical tests can absolutely certify a generator as appropriate for usage in a particular application, i.e., statistical testing cannot serve as a substitute for cryptanalysis. Therefore, a pseudorandom number generator (PRNG) is required as an alternative to RNG but a PRNG requires a RNG as a companion.A pseudorandom number generator (PRNG) inputs are called seeds and outputs are typically deterministic functions of the seed; i.e., all true randomness is confined to seed generation. It should obtain its seeds from the outputs of a RNG. The National Institute of Standard Technology (NIST) Test Suitewas developed to test the randomness of arbitrarily long binary sequences produced by either hardware or software based cryptographic algorithm or pseudorandom number generators. These NIST tests [11] focus on a variety of different types of a randomness that could exist in a sequence. Some tests are decomposable into a variety of subtests. The tests are: (1) The Frequency (Monobit) Test, (2) Frequency Test within a Block, (3) The Runs Test and (4) Discrete Fourier Transform(DFT) Test.Frequency Mono-bit 34 International Journal of Computer Applications (0975 – 8887) Volume 91 – No.12, April 2014 Testfocuseson the number of zeroes and ones for the entire Table 2.Random Test Results sequence. The purpose of this test is to determine whether the number of ones and zeros in the sequence are approximately Modified the same as would be expected for a truly random sequence. Exclusive 128 exclusive 128 Frequency Test within a Block determines the proportion of Random Test bit NLFSR bit NLFSR ones within the M-bit block is approximately M/2, as would Stream cipher Stream cipher be expected under an assumption of randomness. The purpose Frequency Test Passed Test Passed of Run test is to determine whether the number of runs of ones Monobit (0.5959) (0.8597) and zeros of various lengths is expected for a truly random sequence. Discrete Fourier Transform Test focuses on the Frequency Test Passed Test Passed peak heights in the Discrete Fourier Transform of the within a Block (0.9981) (0.9862) sequence and the purpose of this test is to detect periodic features in the tested sequence that would indicate a deviation Test Passed Test Passed from the assumption of randomness. Using this test, if the P- Run (0.2766) (0.5164) value is ≥ 0.01, then the sequence is random, otherwise the sequence is non random[11]. Test Passed Test Passed DFT 4. RESULT AND DISCUSSION (0.0744) (0.8575) The analysis of modified exclusive-128 bitNLFSRhas been donefor the fourstandard types of pseudorandom test like Example 2:Initial Key is expressed in Hexadecimal as: frequency Mono-Bit, Frequency Test within a Block, Run Test and Discrete Fourier Transform Testand the results are “00000000000000000000000000000000” shown in Table2, Table3 and Table4. P-values are calculatedfor proposed stream cipher and it is observed that all The initial key of all „zeros‟ is applied to the conventional P-values are the much greater than 0.01. Hence our stream Exclusive 128 bit NLFSR stream cipher and also the modified cipheris highly random. As, the number of permutations to one. In table 3, for the Frequency Monobit Test on both the crack a 128 bit key is quite larger equal to 2128 and even the stream ciphers, the P-value of Exclusive-128 bit NLFSR time devoted for brute force attack is also larger, our proposed stream cipher is << 0.01 while for modified Exclusive -128 bit stream cipher is a secure one.The tables2,3 and 4 below NLFSR stream cipher is 0.7237. For Frequency Test within a describe the various test conducted to determine the Block on both the stream ciphers, the P-value of Exclusive- Randomness and strength of the proposed algorithm against 128 bit NLFSR stream cipher is << 0.01 while for modified linear cryptanalysis.In the following, we describe with Exclusive -128 bit NLFSR stream cipher is 0.9994. For Run examples how to determine the randomness using the above Test on both the stream ciphers, the P-value of Exclusive-128 mentioned tests for different initial keys. bit NLFSR stream cipher is <<< 0.01 while for modified Exclusive-128 bit NLFSR stream cipher is <<0.01. For DFT Example 1:Initial Key is expressed in Hexadecimal as: test on both the stream ciphers, the P-value of Exclusive-128 bit NLFSR stream cipher is 0.0744 while for modified “8997C67B596354C619E5C6C2B9E376C6” Exclusive-128 bit NLFSR stream cipher is 0.0541. Hence, the The initial key is applied to the conventional Exclusive 128 bit table 3 clearly states that the generated sequence by the NLFSR stream cipher and also the modified one. In table 2, modified Exclusive 128 bit stream cipher is highly random. for the Frequency Monobit Test on both the stream ciphers, The table 3shows the test analysis for the initial key the P-value of Exclusive-128 bit NLFSR stream cipher is vector“00000000000000000000000000000000”. 0.5959 while for modified Exclusive -128 bit NLFSR stream cipher is 0.8597.For Frequency Test within a Block on both Table 3.Random Test Results the stream ciphers, the P-value of Exclusive-128 bit NLFSR stream cipher is 0.9981 while for modified Exclusive -128 bit Modified Exclusive 128 NLFSR stream cipher is 0.9862.For Run Test on both the exclusive 128 Random Test bit NLFSR stream ciphers, the P-value of Exclusive-128 bit NLFSR bit NLFSR Stream cipher stream cipher is 0.2766 while for modified Exclusive -128 bit Stream cipher NLFSR stream cipher is 0.5164.For DFT test on both the Frequency Test Failed Test Passed stream ciphers, the P-value of Exclusive-128 bit NLFSR Monobit (1.1224 e-29) (0.7237) stream cipher is 0.0744 while for modified Exclusive-128 bit NLFSR stream cipher is 0.8575. Hence, the table 2clearly Frequency Test Failed Test Passed states that the modified stream cipher generates highly random within a Block (1.3294 e-05) (0.9994) sequence. But, the key streams generated by the modified stream cipher claims to be highly random.The table 2 shows Test Failed Test Failed Run the test analysis for the initial key vector ------ (1.5388 e-15) “8997C67B596354C619E5C6C2B9E376C6” Test Passed Test Passed DFT (0.0744) (0.0541) Example 3:Initial Key is expressed in Hexadecimal as: “FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF” The initial key of all „ones‟ is applied to the conventional Exclusive 128 bit NLFSR stream cipher and also the modified one.In table 4, for the Frequency Monobit Test on both the 35 International Journal of Computer Applications (0975 – 8887) Volume 91 – No.12, April 2014 stream ciphers, the P-value of Exclusive-128 bit NLFSR Computational Intelligence and Modern Heuristics, stream cipher is << 0.01 while for modified Exclusive -128 bit ISBN: 978-953-7619-28-2. NLFSR stream cipher is 0.8597. For Frequency Test within a Block on both the stream ciphers, the P-value of Exclusive- [2] Jegadish Kumar, K.J. et.al., 2013 “Exclusive-128 Bit 128 bit NLFSR stream cipher is << 0.01 while for modified NLFSR Stream Cipher for Wireless Sensor Network Exclusive-128 bit NLFSR stream cipher is 0.9932. For Run Applications,” International Journal of Engineering and Test on both the stream ciphers, the P-value of Exclusive-128 Technology (IJET), pp:3668 – 3675. bit NLFSR stream cipher is <<< 0.01 while for modified [3] Maximov, A.2006“Some Words on Cryptanalysis of Exclusive-128 bit NLFSR stream cipher is << 0.01. For DFT Stream Ciphers”, Ph.D. Thesis, Lund University. test on both the stream ciphers, the P-value of Exclusive-128 bit NLFSR stream cipher is 0.0744 while for modified [4] Elena Dubrova,2010”Finding Matching Initial States for Exclusive -128 bit NLFSR stream cipher is 0.0744. The table Equivalent NLFSRs in the Fibonacci and the Galois 4 clearly states that the generated sequence by the modified Configurations”, IEEE transactions on information cipher is highly random. The table4shows the test analysis for theory, vol. 56, no. 6. the initial key [5] Hell,M. Johansson,T. and Meier,W. “Grain - a stream vector“FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF”. cipher for constrained environments,” citeseer.ist.psu.edu/732342.html. Table4.Random Test Results [6] Gittins,B. Landman, H. A. O‟Neil, S. andKelson,R. 2005 Modified “A presentation on VEST hardware performance, chip Exclusive 128 area measurements, power consumption estimates and exclusive 128 Random Test bit NLFSR benchmarking in relation to the AES, SHA-256 and bit NLFSR Stream cipher SHA-512.” Cryptology ePrint Archive, Report Stream cipher 2005/415.Http://eprint.iacr.org/. Frequency Test Failed Test Passed Monobit (1.7920 e-15) (0.8597) [7] Elena Dubrova,2009”ATransformation From the Fibonacci to the Galois NLFSRs”, IEEE transactions on Frequency Test Failed Test Passed information theory, vol.55,(November 2009) no.11,pp. within a Block (2.5625 e-05) (0.9932) 5263-527. Test Failed Test Failed [8] Dubrova.E, 2009 “How to speed up your NLFSR based Run ------ (5.2889 e-09) stream cipher,” Design, Automation and test in Europe Test Passed Test Passed Conference and Exhibition,pp: 878 – 881. DFT (0.0744) (0.0744) [9] NurHafizaZakaria, KamaruzzamanSeman and Ismail Abdullah, 2011 “Modified A5/1 Based Stream Cipher 5. CONCLUSION For Secured GSM Communication”, IJCSNS We proposed a Modified Exclusive-128 Non Linear Feedback International Journal of Computer Science and Network Shift Register (NLFSR) based stream cipher which is a simple Security, vol.11 No.2. architecture with basic elements likes shift register, flipflop and XOR. The tables 2, 3 and 4 show that calculated P- [10] Tarannikov,Y.2001 “New constructions of resilient valuefor using various Initial key lengths and in this modified Boolean function with maximum nonlinearity”, Lecture stream cipher, tests have been done to prove that the stream Notes in Computer Science, vol. 2355, pp. 66–77. cipher is highly non-linear with full pseudo randomness.The [11] Andrew Rukhin, Juan Soto, 2010 “A Statistical Test implementation of FPGA and various attacks models based Suite for Random and Pseudorandom Number studies are to be made as future works. Generators for Cryptographic Applications”, National Institute of Standards and Technology (NIST), US 6. REFERENCES department of Commerce, (April 2010). [1] KhaledSuwais, AzmanSamsudin, 2010 “NewClassification of Exiting Stream Ciphers,” In Book: IJCATM : www.ijcaonline.org 36