# Secret key ciphers

# Secret key ciphers

### INTRODUCTION

Secret key ciphers are classified into 2 types, block ciphers and stream ciphers. Block ciphers are the time varying transformation of group of data bits and stream ciphers are the time varying transformation of individual or stream of data bits. It includes internal memory in stream ciphers whereas in block ciphers, no internal memory is involved. Stream ciphers are important class of encryption algorithms because of their low hardware complexity and power consumption. They encrypt binary digits of plaintext message at a time, using an encryption transformation that varies with time. They are

fast and more appropriate and in some cases mandatory (example in some communications applications), when buffering is limited or when characters are individually processed during reception. Because of their low error propagation criteria, stream ciphers are advantageous in situations where transmission errors are highly probable.

A binary additive stream cipher is just an XOR operation of plain text and keystream bits. It consists of keystream, plaintext and cipher text in the form of binary sequences. Each secret key K is given as an input to the keystream generator that generates a keystream sequence. Since the secret key K is shared between the transmitter and receiver, the receiver can decrypt by XOR'ing the output of the keystream generator with the cipher text, obtaining the message sequence. Keystream generation plays a major role in the security of the system. Hash functions are commonly used in communication devices, especially for integrity verification and authentication of data and control packets. Basically a hash function is a function that maps a message of variable length to a fixed length hash value that serves as an authenticator. Hence a stream cipher based on hash function is a very good option in reducing hardware complexity of the cryptosystem. So a hash based stream cipher with low hardware complexity is important in the design of many cryptosystems. Based on the usage of hash function the security of PRNG varies.

A cryptographically strong Pseudo Random Number Generator (PRNG) is the heart of any stream cipher. A pseudo random number generator is a deterministic polynomial time based algorithm, which expands short seeds into longer bit sequences. Two methods of producing cryptographically strong PRNG are LFSR schemes and Oneway function based schemes. Linear Feedback Shift Registers are the most commonly used stream ciphers due to the low hardware complexity and less power consumption. The main drawback of LFSR based stream ciphers is susceptibility to attack due to the linearity in the structure. Two major schemes to destroy the inherent linearity in LFSRs are taking output through non-linear Boolean function and irregularly clocking LFSRs (clock controlled generator). Boolean function can be used to combine the outputs of several LFSRs or outputs of different memory elements of a single LFSR giving rise to nonlinear combination generator and filter generator structures respectively. Step1-step2 generators, alternating step generators, shrinking and self-shrinking generators belong to the category of the clock controlled generators (CCG) where the LFSR generating the keystream is clocked at different intervals.The only drawback of irregular clocking is keystream period gets shortened, but as per the security it gives best results.

A class of bit oriented key stream generator Ωk is proposed in this paper and is related to class of the ASG (Alternating Step Generator). ASG belongs to the family of CCG class. Here, the keystreams generated by K generator Gk are of long period, high complexity and nice statistical distribution properties. It uses three feedback shift register R1, R2 and R3 in the generation of keystream. The first register R1 changes state as a usual FSR (Feedback Shift Register) where as the other 2 registers R2 and R3are clocked using a clocking mechanism. After the clocking, the output bit is produced at the output of Gk. Keystreams generated by a Gk are obtained by XOR'ing outputs of all 3 shift-registers R1, R2 and R3. Correlation attack is one of the powerful attacks on stream ciphers based on FSRs and is considered as one of the most serious threat against the security of stream ciphers. If a cryptanalyst manages to detect a correlation between the known keystream segment and the output of one LFSR (when regularly clocked), this can be utilized in a divide and conquer attack on this LFSR. So, proper keystream generation improves the security.

### Design Of Stream Ciphers:

This chapter deals with the proposals of 3 stream ciphers and the hardware analysis, periodicity and attack time of both the stream ciphers.

### STREAM CIPHER1:

Stream cipher 1 is a combination of LFSR based toeplitz hash generation circuit and LFSR based keystream generator circuit.

### LFSR Based Toeplitz Hash Function:

Let a message M consists of length ‘m' bits and the output hash be of ‘n' bits. In order to generate a matrix of order n*m, we need nm elements. By using Toeplitz matrix structure it is possible to achieve the matrix of order m*n by using m+n-1 bits. The Toeplitz matrix is characterized by the property that each column in the matrix is obtained by shifting down the previous column and adding a new element to the top of the column. Let the initial state of LFSR hash be (s0, s1, s2, s3, s4) = (0 0 0 1 0) and the LFSR hash polynomial be h(x)= x5 + x2 + 1. Since the degree of h(x) is 5, n = 5 and the number of message bits be m=9. According to Toeplitz criteria, it needs only m+n-1 bits, (here, 9+5-1=13 bits) in order to generate a matrix. So using the above mentioned feedback polynomial and initial state, the 13 bit output sequence of the LFSR is (s0, s1,., s12) = (0 0 0 1 0 1 0 1 1 1 0 1 1). The Toeplitz matrix is formed by writing the initial sate of the LFSR starting from the bottom as the first column of the matrix. The consecutive columns are obtained by shifting down the previous column by one bit and adding the new bit obtained after each clock to the top of the column. LFSR o/p sequence = [0 0 0 1 0 1 0 1 1 1 0 1 1]

Toeplitz matrix (5 x 9) =

0 1 0 1 1 1 0 1 1

1 0 1 0 1 1 1 0 1

0 1 0 1 0 1 1 1 0

0 0 1 0 1 0 1 1 1

0 0 0 1 0 1 0 1 1

Let the 9 bit message be [0 0 0 0 1 0 0 0 1].

Then the hash value is obtained by reversing the bits obtained by multiplying the Toeplitz matrix with the column matrix of the message. Hash value produced is [1 0 0 0 0].

0 1 0 1 1 1 0 1 1

1 0 1 0 1 1 1 0 1

0 1 0 1 0 1 1 1 0 * (0 0 0 0 1 0 0 0 1)^T

0 0 1 0 1 0 1 1 1

0 0 0 1 0 1 0 1 1

= ( 1 0 0 0 0 )^T

The schematic diagram of LFSR based Toeplitz matrix is shown below. In the figure, the control register and shift register together forms the LFSR, whereas, the control register defines the feedback polynomial of the LFSR. The LFSR changes its state with each message bit. If the message bit is ‘1', the corresponding state is accumulated into an accumulation register and if it is ‘0' the state is not accumulated.

Schematic diagram of LFSR based Toeplitz matrix

### Model Of KeyStream Generator:

Consider a message of length ‘m' bits and output ‘n' bits. Let ‘KEY' be the initial random seed, ‘h' be the hash function and Xi be the hash function output after ith iteration and S1, S2, S3, .. be the sequence of strings generated by a deterministic function ‘F'. The first stage output is X1=h(KEY||S1), i.e., concatenation of KEY and initial string. To get the next string in the sequence of keystream, hash a modified version of the previous output string is concatenated with the new random bits generated by the deterministic function 'F'. The mathematical model of proposed stream cipher is represented as below.

X1=h(KEY || S1)

X2=h((KEYX1)||S2)

X3=h((KEYX2)||S3)

Xn=h((KEYXn-1)||Sn)

Keystream=X1 ||X2 ||X3 ||……..||Xn;

### Construction of stream cipher1:

Stream cipher 1 is a combination of LFSR based toepliz hash generation circuit and LFSR based keystream generator circuit. The structure of lfsr based toeplitz hash is shown below. Algorithm steps: 1) whenever the input is high, the states of LFSR are loaded into the register. 2) If the input is low, the states are discarded. 3) Once again if the input is high, 5 bit register is XORed with current contents in flipflops of LFSR and previous output of register is modified by present XOR output. 5 bit register is clocked only when message is high.

### Hardware Implementation:

A0 to A4 represents the state of the LFSRT and is initialized. The feedback polynomial of the LFSRT block used in the structure is taken as h(x) =x5+x2+ 1. Since the degree of the LFSRT polynomial of the hash block is 5, number of bits in the hash output is n= 5. Therefore m-n=4, i.e., the degree of feedback polynomial of string generating LFSRS is taken as 4. The number of bits in the input of hash function block ‘m=9'. The main blocks in the realization of the LFSR based Toeplitz hash function are LFSRT and accumulator. Thus 9 bits input are serially fed to the hash function block. The LFSRT advances its state with each of the input bits. If the input bit is 1, the corresponding state (A0 to A4) of the LFSR is stored in a 5 bit register. If the input bit is 0, then the corresponding state is discarded. The next time when the input bit is 1 the states of the 5 bit register is XORed with the current contents of the flipflops of the LFSR and the previous output of the register is modified by the present XOR output and is stored as a new output(Y0 to Y4). The 5 bit register is clocked only when the message bit is high. The final content of the register after all the inputs are fed to the hash function block is the final hash value. The keystream bits of the proposed model are the serial output from the hash function block.

### Results:

The platform used is MATLAB (for calculating periodicity and attack time) and XILINX ISE 10.1, FPGA (for hardware design). The periodicity of the model can be defined as n(2n-1)(2(m-n)-1)),where ‘m' is the length of input to the hash function in terms of number of bits and ‘n' is the degree of polynomial. The throughput is defined as the ratio of the number of output random bits to the number of input random bits and is given by [n(2n-1)(2(m-n)-1))]/m, which can be much larger than that of a simple LFSR based stream cipher given as (2m- 1)/m for a proper selection of ‘m' and ‘n'. For example with n=4, m=8, throughput for LFSR based stream cipher is 31.89 while that for the proposed model is 112.5. Period for LFSR is 255 and for the proposed model is 900. Period of the key stream= n(2n-1)(2(m-n)-1)) and attack time = O(2k).

### Periodicity and Attack Time of Stream Cipher 1:

Hash o/p length n(bits) |
Hash i/p length m(bits) |
Period of key stream |
Attack-time |

4 |
7 |
422 |
0.09s |

5 |
8 |
1025 |
0.17s |

5 |
9 |
2325 |
0.81s |

7 |
11 |
13335 |
4.81s |

7 |
13 |
157,619 |
206.9s |

11 |
15 |
337,755 |
1653.3s |

Table1 shows the periodicity and attacktime results for various m,n values

From the above table it is observed that the periodicity increases at a high rate and for high values of m,n the attacktime also increases rapidly. The simulation results of LFSR based Toeplitz hash is shown below.

### STREAM CIPHER2:

Stream cipher 2 is a combination of LFSR based filter circuit and polynomial modulo division circuit. For synchronous stream cipher, CRC hash circuit is generated first and it is combined with well known LFSR filter generator structure in order to increase the periodicity and security of this classic structure. In a filter generator, the Boolean function combines outputs of different memory elements of a single LFSR.

### Structural block diagram of stream cipher2:

An LFSR of length ‘m' produces a keystream of maximum period 2m-1, when the feedback polynomial is primitive. All stream ciphers based on this structure are also limited to this periodicity. The periodicity of generated keystream in conventional LFSR based stream ciphers can be increased by increasing the key size m. The key should be generated by a random source and it is difficult to build a pure random or pseudorandom source to generate a key of large size. Throughput for typical LFSR based stream ciphers is (2m-1)/m. It can be increased to a higher value by using some reseeding mechanism. Reseeding mechanism is generating a new seed after every 2m-1 clock cycles. In stream cipher model, the modular division circuit (CRC hash circuit) is used to reseed the non-linear filter generator at the end of every fundamental period of 2m-1clock cycles. The reseed key is the hash output obtained by passing the stream generated by the LFSR in filter generator as input to the modular division circuit. The CRC circuit should be designed in such a way that the security of the stream cipher can be very high. Considering fundamental period of (2m-1) and stream cipher contains (2n-1) periods of filter generator, a total period of (2m-1)(2n-1) clock cycles, is obtained. At this period, the LFSR in filter generator is to be reloaded with initial key.

### Shift Register Based DivisionCircuit:

The hardware circuit used to perform division modulo polynomial over Galois Field GF (2) can be implemented efficiently using LFSR. (In GF, addition is equivalent to exclusive-OR operation and multiplication is equivalent to logical AND operation). In CRC operation, which is division modulo an irreducible polynomial over GF(2) is used to generate the cryptographic hash code (CRC code). In a normal CRC calculation, the CRC code is calculated as: CRC code = M(x) mod G(x). If g(x) is a polynomial of degree ‘n' over GF(2), then ‘n' is the hash value size in bits. M is the message to be hashed and M(x) is the message polynomial with degree ‘m-1', where ‘m' is the message size, and m >> n. The operation of division modulo a polynomial over GF(2) is implemented through a simple LFSR with taps or connections determined by the division polynomial. The schematic realization of cryptographic CRC hash by taking the division polynomial as G(x) =x5+x4+x2+1 is represented as:

shows the CRC hash using polynomial G(x) =x5+x4+x2+1

### Experimental Results:

The periodicity of proposed structure in comparison with the pairs of polynomials to that of simple LFSR keystream generator for the same number of input random bits (same key size) is given in the table. Table II Pairs of Q (X) keystream generation polynomial, G(X) division Polynomials for Maximum Periodicity.

Table 2 shows the periodicity and attack time calculation for various G(x) and Q(x) polynomials

Results of simulation of 4 bit LFSR with Q(x) = x4 + x + 1 and G(x) = x4 + x3 + 1 are shown in Table II. The entries below each initial key in Table II shows the re-seed keys generated by mod g(x) circuit at the end of every 15 cycles. The fundamental LFSR with feedback polynomial Q(x) = x4+x+1 and initial key (a3 , a2 , a1 , a0 ) = (1 0 0 1) gives output polynomial, aˆ(x) = x14 + x11 + x7 + x6 + x5 + x4 + x2 +1. This polynomial when divided by G(x) = x4 + x3 + 1, in mod G(x) circuit returns the residue R(x) = x + x2 + x3, given as (0 1 1 1) in the first row below column corresponding to key (1 0 0 1). This residue (0 1 1 1) is loaded into LFSR as key for next iteration giving output polynomial, aˆ(x) = x13 + x12 + x11 + x10 + x8 + x6 + x5 + x2.

Table III residues given as keys at different stages for 4 bit LFSR.

KEY=1001 |
KEY=1000 |

0111 |
1011 |

0011 |
1101 |

0110 |
0010 |

1111 |
1010 |

1000 |
0001 |

1011 |
1100 |

1101 |
1110 |

0010 |
0100 |

1010 |
0101 |

0001 |
1001 |

1100 |
0111 |

1110 |
0011 |

0100 |
0110 |

0101 |
1111 |

1001 |
1000 |

Table 3shows residues given as keys at different stages for4-bit LFSR

### Hardware Implementation:

The LFSR polynomial is taken as Q(x)= x9+x4+1 and the division polynomials are taken as G1(x)=x6+x5+x4+x3+1 and G2(x) =x2+x+1. By using these polynomials we can generate a CRC hash. Once a CRC hash is generated, the output is sent through a non linear filter in order to get the stream cipher output. The expected results are shown below. The structure of proposed model is simulated using Verilog on FPGA XILINX XC2S400-5pq208.

The hardware structure of proposed stream cipher2 is simulated in Verilog. The periodicity and security analysis for various key sizes are done using MATLAB. The increased periodicity and security of the proposed structure is clearly visible from experimental results. For the size key size, periodicity and attack time are compared for filter generator.

### Clock controlled Stream Cipher:

Clock controlled stream cipher uses irregular clocking as a non-linear function. The irregular clocking is more effective than other non-linear functions. The main idea behind CCG is to introduce nonlinearity into LFSR-based keystream generators by having the output of one LFSR control the clocking of a second LFSR. Since the second LFSR is clocked irregularly, attacks can be reduced. CCG is classified into two 2 types, the alternating step generator and the shrinking generator. This stream cipher design uses the alternating step generator. The alternating step generator uses an LFSR R1 to control the stepping of two LFSRs, R2 and R3. The keystream produced is XOR of the output sequences of R2 and R3. The following steps are repeated until a keystream of desired length is produced. 1) Register R1 is clocked. 2) If the output of R1 is 1 then: R2 is clocked; R3 is not clocked but its previous output bit is repeated. (For the first clock cycle, the previous output bit of R3 is taken to be 0). 3) If the output of R1 is 0 then: R3 is clocked; r2 is not clocked but its previous output bit is repeated. (For the first clock cycle, the previous output bit of R2 is taken to be 0). The output bits of R2 and R3 are XORed; the resulting bit is part of the keystream.

### Description of a K-generation of modified clock-controlled alternating step generator (Ωk): :

A generator Gk of the class Ωk is a binary keystream generator intended for hardware implementation. Every generator Gk is composed of 3 Feedback Shift Registers R1,R2,R3 of lengths l,m,n respectively. Let H={0,1} and K={l,m,n.del1t,del2t}, be arbitrary vectors, where l,m,n are positive integers and deljt(for j€{1,2}) is a decimation function that acts on R1:{0,1}l à {1,2,3,….,2l}. For any nonnegative integer i, let R1i,R2i and R3i denote the elements of Hl,Hm,Hn respectively and Xi denotes the elements of V= (Hl )*(Hm )*(Hn). Gk=(K, (f0,f1,f2)), where f0: HlàH, f1: HmàH and f2: HnàH are the feedback functions of R1,R2,R3 respectively. If all the feedback functions fj, j€{0,1,2} are linear then Gk is said to be linear. If f0 is nonlinear but f1 and f2 are linear then Gk is said to be mixed.

The first register R1, called the controlling register of Gk, changes its state as a normal Feedback Shift Register whereas the other 2 registers R2 and R3 called the generating registers of Gk are clocked using a clocking mechanism. It works as follows: R1 controls the clocking of both R2 and R3. At one time t, only one of the last two is to be clocked denotes the ith bit of the register R1 by R1i(t). if R10(t)=1, the clocking of R2 is performed and the bits R10(t), R11(t),…. R1w1-1(t) are the inputs of a clocking unit, otherwise the clocking of R3 is to be performed and the bits R1j0(t), R1j1(t)…. ,R1jw2-1(t) are the inputs of a clocking unit. The clocking unit computes the integer value of these bits and returns that value plus 1. I.e., at time t, if R10(t)=1, R2 is clocked del1t times and R3 is not clocked, otherwise R3 is clocked del2t times and R2 is not clocked, where Del1t= R10(t)[1+20 R1i0(t)+ 21 R1i1(t)+……..+ 2w1-1 R1iw1(t)],

Del1t=0(t)[1+20 R1j0(t)+ 21 R1j1(t)+……..+ 2w2-1 R1jw2(t)]

For 0<w1, w2<l, and i0,i1,i2,……iw1-1, j0,j1,…..jw2-1€{1,2,…l-1}, Where (t) denotes the complement of Ri(t). After these clocking, R1 is clocked once. Once the clocking is performed, an output bit of Gk is ready.

The output bit is XOR of the outputs of R1,R2 and R3 if Gk€Ωk1 or the XOR of the outputs of R2 and R3 if Gk€Ωk2. Keystream Z={Zt}0∞ =Z0,Z1,…..Z∞ denote the keystream generated by Gk, and Z is given by

Z= {R1t R2π1(t) R3π2(t) if Gk €Ωk1,

{ R2π1(t) R3π2(t) if Gk€Ωk2.

R2π1(t)= {R2π1(t)} 0∞ ………

From the previous definitions it follows that all state sequences and keystream generated by Gk of Ωk1 U Ωk2 are most periodic. Gk is said to be maximum if and only if all its state sequences are periodic with maximal period equal to Px, where Px= 2l(2m-1)(2n-1) if Gk is mixed or Px= (2l-1)(2m-1)(2n-1) if Gk is linear. The subclasses of mixed and linear K-generators will be denoted by M- Ωk and L- Ωk respectively.

### Generation of delta function and state diagram:

Keystream Z of a K-generator Gk є Ωk2 is a bitwise XOR of the irregular decimation of its generating sequence. R2t and R3t are governed by the decimation function delt1 and delt2. Thus it is difficult to expect a strong correlation especially, if polynomials of high hamming weight are associated with the feedback function of the registers. The secret key K of Gk consists of the initial state of Gk and the decimation functions. The size of the key depends on the desired level of security. To achieve high-level security level, the choice of parameters are: a control register size l≈128, generating registers sizes m,n>80, polynomials of high hamming weights associated with the feedback functions of these registers and decimation functions consisting of small values for w1 and w2 ranging from 1 to 5. Such Gk is resistant against well-known attacks. Eg: For a Gk whose FSR's have length l=128, m=127 and n=125, any combination of the following values for w1 and w2 such that w1, w2 є {1,2,3,4,5} satisfies the necessary conditions (L- Ωkmax) U (M- Ωkmax).

### Hardware Implementation:

delt i function generation and state diagram of clock controlled circuitry.

The hardware implementation is provided in the figures for LFSR based Gk with l=64 (It can easily be extended to handle a size of l=128). For fixed width delt1 and delt2, where the widths are both 2 (i.e., w1=w2=2), the overall output stream of Gk is computed by XOR'ing the outputs of registers R1, R2 and R3 if Gk є Ωk1, or only of registers R2 and R3 if Gk є Ωk2.

Above fig. gives the delti (for i=1,2) function generation circuitry and clock controlled circuitry state diagram and implementation. Here, each one of the two decoders sets exactly one of its 64 outputs based on the 6-bit index value, which is the input of the decoder. The LFSR3 content (i.e., LFSR R1) is ANDed with the decoder output. The single bit output of each AND tree contains the selected bit of the first LFSR. At any time t, to compute the values of delti, the leftmost bit is multiplied by 2, which is affected through a shift-left operation. A subsequent addition of each of the weighted bits yields to the function delti generation. The number of decoders, AND trees are equal to the window sizes. The shift-left operators should also be adjusted in order to multiply each bit with its proper weight.

The state diagram consists of three states, each corresponding to the clocking of one particular LFSR. The sequence of events is as follows: For hardware simplicity, first LFSR3 is clocked once. Based on the value of R10(t), the function delti is generated, which denotes how many times LFSR R2 or LFSR R3 are to be clocked. Subsequent to the clocking of the proper LFSR as many times as dedicated by the delta function. Again, LFSR3 is clocked only once. In implementation, one hot coding scheme is utilized: The 3 states are encoded as “100”, “010” and “001”. In this state, the down-counter is loaded with the proper delta function, depending on the value of the LSB of LFSR3, which also determines the next state. Based on the values of this bit, the circuit transactions to either S2 or S3, wherein it remains as many clock cycles as the function delti. During these clock cycles, the counter is decremented. When the counter content becomes all 0's, which denotes that delta cycles are over, the circuit transactions back to S1, wherein the counter is loaded with a new value of delta. In each state, only the corresponding LFSR is clocked, which is ensured by the 3 clock-gating AND gates next to each other. In the process, clock buffers may be inserted in the proper locations within the clock network.

The RTL schematic of clock controlled generator is shown below.

Hardware implementation of proper clock control of 3 LFSRs (CCG block) is shown below. The entire block CCG is used in the above schematic for the control of LFSRs.

Table IV shows the comparison of various stream ciphers with parameters like periodicity, attacktime, throughput and security are shown below.

Parameter/ stream cipher |
Periodi-city |
Attack-time |
Through-put |
security |

Stream Cipher1 |
High n*(2n-1) *(2m-n-1) |
Medium O(2k) |
High (n(2n-1)(2m-n-1))/m |
Medium |

Stream Cipher2 |
Medium (2n-1)* ( 2m-1) |
High O(2m+c-n) C<1 |
Medium (2n-1)*( 2m-1)/m |
Medium |

Alternating Step Generator |
Medium 2l*(2n-1) *(2m-1) |
high |
Medium 2l*(2n-1) *(2m-1)/m |
High |

Table 4 comparison of various stream ciphers with different parameters

### Conclusion:

The design of two stream ciphers and the modified clock controlled alternating step generator are made using XILINX FPGA. Periodicity, attacktime and throughput are calculated using MATLAB. This paper includes a class of keystream generators Ωk intended for hardware implementation. A complete description of the design of generator is given. The clock control introduced in this paper makes cryptanalytic attacks more difficult. As per the characteristics and properties, it is clear that the K-generator is well suited in stream cipher applications. As per the results, the periodicity of stream cipher 1 is more compared to stream cipher2 and the attack time of stream cipher2 is more compared to that of stream cipher 1. It is shown that keystreams of the K-generator Gk, have large period, large linear complexity, high throughput and provides good security compared to the first 2 stream ciphers. Comparison of stream ciphers has been given in terms of periodicity, attacktime, throughput and security. A proper design exercise on higher length of LFSR can give rise to very attractive stream ciphers for use in handheld communication devices and in other communication applications, which demand low hardware complexity and real time operation.