لارين
07-27-2009, 10:43 AM
Randomness Test for Binary Stream Cipher Sequence
Based on Frequency of Slide Door Sectors
Mustafa A Salman
Ajman University for Science and Technology Network
Email : mustafasalman70@hotmail.com (mustafasalman70@hotmail.com)
Hasan L Nasir and Ali M Kadhim
University of Technology – Baghdad – Iraq
Abstract
In this paper, a Randomness Test based on Frequency of Slide Door Sectors for a binary sequence produced from stream cipher systems, is presented. The test has been implemented on binary sequences produced from known stream cipher systems and shown be very reliable.
Key words: randomness, stream cipher, slide door sectors, local complexity.
Introduction
Randomness of a binary sequence produced from stream cipher systems is very essential in determining the security level of the system and then the validity of the design of such systems. Rueppel [4] studied the relation between randomness of a
binary sequence and the linear complexity profiles of such sequence. Carter [1] also studied the Randomness of a binary sequence in association to the jumps of linear complexity profiles of the sequence. Salman et al. [5] presented Randomness test
of binary sequence based on frequency of linear complexity profile of the sequence. Niederreiter [3] studied the probabilistic theory of linear complexity profile.
A binary sequence S = s0 s1 s2 . . .sn of period p is called pseudo-random [2] if
1- Number of 0’s differ by 1 from number of 1’s .
2- The number of runs of length i is 1 / 2i .
3- If S* is the produced sequence after shifting S, t-places then the auto-correlation C ( t ) = [A ( t ) – D ( t ) ] / p is two-valued function , where A( t ) and D( t ) are the number of places that the sequence S agree and disagree respectively with S*. Since all sequences in this article are finite, a random sequence will mean pseudo-random sequence.
One of the most important devices that produces random binary sequences is the
Linear Feedback Shift Register ( LFSR) . A linear feedback shift register of length n
[2] is a finite state machine consists of n tubes, storage, or delay units such that the content of each unit is either 0 or 1. A linear feedback function is a function of the form
f ( t ) = c0 st + c1 st+1 + c2 st+2 + . . . + cn-1 st+[n-1] = st+n , t = 1, 2, . . .
Where ci ε GF[2] .Otherwise the feedback is non-linear .
If the characteristic polynomial associated to the above feedback function is
Primitive, then the sequence produced [2 , 4] will have maximal period 2n - 1
and it is well known that a maximal period sequence is pseudo-random.
Theorem :- [2]
The binary sequence produced by LFSR of length n is periodic with period
P ≤ 2n –1
If a binary sequence is random then the frequency of each subset of a fixed length
will have the same value. That is by computing the frequency of each subset of a
binary sequence and compare them with the expected value will determine the
randomness of the sequence. It is well known that the complexity of a binary
sequence is associated to the randomness of such sequence [1,3,4] since the linear
complexity of a binary sequence is the length of the shortest LFSR that generates the
sequence . The linear complexity of part of a sequence is called a local complexity of
the sequence .The length of a binary sequence produced from stream cipher systems
must be very long so that encryption process never use the keys twice which means
that the encryption process never exhaust the whole sequence. Hence the local
complexity of the used part of the sequence is very effective and essential in
determining the practical security of such systems. This is why an intensive study
of the used part of the sequence, which admitted in this paper, is very important.
These facts are considered in the randomness test presented in this paper, in which a slide door sectors are used with some care in determining the length of the sectors.
m - bit Slide door Sectors
Consider a random binary sequence of length n, s1 s2 . . .sn .
The m-bit slide door sectors ki , i = 1, 2, 3, …, r where m + r – 1 = n are
Ki = si si+1 si+2 … s[i-1]+m , where i – 1 + m ≤ n
That means
K1 = s1 , s2 , . . . , sm ,
K2 = s2 , s3 , . . . , sm+1 ,
.
.
.
Kr = sr , sr+1 , . . . , sm+[r-1] , m+[r-1] = n .
Clearly m-bit slide door sector has 2m possible, and if r is the number of these sectors then the expected value should be r / 2m . In a random sequence, if fk is the
frequency of the sector k then fk must be near r / 2m , that is
( fk - r / 2m ) must be near zero . Hence the statistical value will be
ST = Σ [ ( A – E )2 / E ] , from k = 0 to k = r , where
A = Actual = fk , and E = Expected = r / 2m that is
ST = (2m / r ) . Σ [ fk - r /2m ]2 from k = 0 to k = r .
The binary sequence pass the test of randomness if ST ≤ ki-square value with
degree of freedom 2m –1. Notice that r / 2m for all sectors must be large enough .
Analysis
For a maximal period sequence of length n , if m = L = the length of the LFSR that generate the sequence then the frequency of each m-bit slide door sector ( except blank state ) is 1 but if m < L then the frequency will be 2(L-m) while choosing m > L cause improper result due to choosing 2m state out of 2L state.
Each binary sequence will pass the test if the statistical value ST is near zero. That is
the randomness test for a binary sequence of length n with m-bit slide door sectors will be accomplished by computing the frequency of each slide door Sectors, fi , computing ST and then checking with the value of ki - square test with degree of
freedom 2m – 1 . In short, the binary sequence pass the test if ST ≤ the value of ki-square test with degree of freedom 2m – 1 , otherwise the sequence is not random.
Algorithm of the Randomness Test
1- Set m to be the length of the slide door sector of a binary sequence
S = s1 s2 . . . sm sm+1 . . .sn .
2- Set r = n – m + 1 and determine
K1 = s1 s2 . . . sm ,
K2 = s2 s3 . . . sm+1 ,
.
.
.
Ki = si si+1 . . . s[i-1]+m ,
.
.
.
Kr = sr sr+1 . . . sm+[r-1] ,
3- Compute the frequency fi of each ki , i = 1, 2, . . . , r .
4- Compute
ST = ( 2m / r ) . Sum [ fj - ( r / 2m )]2 from j = 0 to j = r .
5- If ST ≤ the value of ki-square test with degree of freedom 2m -1 then the
sequence pass the test otherwise it is not .
Applications
The randomness test implemented on maximal period binary sequences
(max system) and binary sequences produced from pless, Geffe, Threshold,
“XOR”,and “AND” systems. Each of the last two systems consists of two LFSR
that produces maximal period sequences combined by “XOR” and “AND”
operations respectively. Clearly the binary sequence produced from the “XOR”
system is random while the binary sequence produced from “AND” system is
non-random.
n chosen to be 1024 while m chosen to be 4, 5, and 7 ( m = 5 = the length of the
letter in ITA2 code). The output of the test is given by the following table where d7 , d5 , d4 are the values of ki-square test with degree of freedom127,31,15 respectively.
n = 1024
m = 7
m = 5
m = 4
ST
d7
ST
d5
ST
d4
Binary
Sequences
Produced
from
Max System
0.12
154
0.03
45
0.01
25
Pless
125.5
154
33.31
45
19.9
25
Geffe
131.25
154
32.37
45
15.9
25
Threshold
144.5
154
20.36
45
7.39
25
“XOR” system
95.2
154
29.3
45
16.7
25
:AND” system
4595.1
154
2271.7
45
6189.1
25
Clearly all, except the last, pass the test of randomness.
Conclusion
Slide door sectors of the binary sequence under consideration play an essential
role in constructing reliable test of randomness since slide door sectors explore
most of the characters of the binary sequence . This test reduces the length of the sequence needed for the test. Although the test is reliable, a binary system produced from stream cipher systems should pass all the known tests together with the test presented in this paper.
REFERENCES
1- Carter, G. “ Statistical tests for randomness”, EISS , karlsruhe,England , 1989.
2- Golomb, S.w “ Shift Register Sequences “ Aegean park press, 1982
3- Niederreiter, H “ The probabilistic theory of linear complexity “ Advances in
Cryptology, Eurocrypt 88 proceeding , vol 330 [ 1988].
4- Rueppel, R.A “ Analysis and design of stream cipher “ , London, 1986.
5- Salman, M.A, Nasir, H.L, and Kadhim, A.M “ Randomness test based on
frequency of LCP of binary sequence , International Journal of Applied Science
and Computations, vol. 12 , No. 2 August 2005 USA
Based on Frequency of Slide Door Sectors
Mustafa A Salman
Ajman University for Science and Technology Network
Email : mustafasalman70@hotmail.com (mustafasalman70@hotmail.com)
Hasan L Nasir and Ali M Kadhim
University of Technology – Baghdad – Iraq
Abstract
In this paper, a Randomness Test based on Frequency of Slide Door Sectors for a binary sequence produced from stream cipher systems, is presented. The test has been implemented on binary sequences produced from known stream cipher systems and shown be very reliable.
Key words: randomness, stream cipher, slide door sectors, local complexity.
Introduction
Randomness of a binary sequence produced from stream cipher systems is very essential in determining the security level of the system and then the validity of the design of such systems. Rueppel [4] studied the relation between randomness of a
binary sequence and the linear complexity profiles of such sequence. Carter [1] also studied the Randomness of a binary sequence in association to the jumps of linear complexity profiles of the sequence. Salman et al. [5] presented Randomness test
of binary sequence based on frequency of linear complexity profile of the sequence. Niederreiter [3] studied the probabilistic theory of linear complexity profile.
A binary sequence S = s0 s1 s2 . . .sn of period p is called pseudo-random [2] if
1- Number of 0’s differ by 1 from number of 1’s .
2- The number of runs of length i is 1 / 2i .
3- If S* is the produced sequence after shifting S, t-places then the auto-correlation C ( t ) = [A ( t ) – D ( t ) ] / p is two-valued function , where A( t ) and D( t ) are the number of places that the sequence S agree and disagree respectively with S*. Since all sequences in this article are finite, a random sequence will mean pseudo-random sequence.
One of the most important devices that produces random binary sequences is the
Linear Feedback Shift Register ( LFSR) . A linear feedback shift register of length n
[2] is a finite state machine consists of n tubes, storage, or delay units such that the content of each unit is either 0 or 1. A linear feedback function is a function of the form
f ( t ) = c0 st + c1 st+1 + c2 st+2 + . . . + cn-1 st+[n-1] = st+n , t = 1, 2, . . .
Where ci ε GF[2] .Otherwise the feedback is non-linear .
If the characteristic polynomial associated to the above feedback function is
Primitive, then the sequence produced [2 , 4] will have maximal period 2n - 1
and it is well known that a maximal period sequence is pseudo-random.
Theorem :- [2]
The binary sequence produced by LFSR of length n is periodic with period
P ≤ 2n –1
If a binary sequence is random then the frequency of each subset of a fixed length
will have the same value. That is by computing the frequency of each subset of a
binary sequence and compare them with the expected value will determine the
randomness of the sequence. It is well known that the complexity of a binary
sequence is associated to the randomness of such sequence [1,3,4] since the linear
complexity of a binary sequence is the length of the shortest LFSR that generates the
sequence . The linear complexity of part of a sequence is called a local complexity of
the sequence .The length of a binary sequence produced from stream cipher systems
must be very long so that encryption process never use the keys twice which means
that the encryption process never exhaust the whole sequence. Hence the local
complexity of the used part of the sequence is very effective and essential in
determining the practical security of such systems. This is why an intensive study
of the used part of the sequence, which admitted in this paper, is very important.
These facts are considered in the randomness test presented in this paper, in which a slide door sectors are used with some care in determining the length of the sectors.
m - bit Slide door Sectors
Consider a random binary sequence of length n, s1 s2 . . .sn .
The m-bit slide door sectors ki , i = 1, 2, 3, …, r where m + r – 1 = n are
Ki = si si+1 si+2 … s[i-1]+m , where i – 1 + m ≤ n
That means
K1 = s1 , s2 , . . . , sm ,
K2 = s2 , s3 , . . . , sm+1 ,
.
.
.
Kr = sr , sr+1 , . . . , sm+[r-1] , m+[r-1] = n .
Clearly m-bit slide door sector has 2m possible, and if r is the number of these sectors then the expected value should be r / 2m . In a random sequence, if fk is the
frequency of the sector k then fk must be near r / 2m , that is
( fk - r / 2m ) must be near zero . Hence the statistical value will be
ST = Σ [ ( A – E )2 / E ] , from k = 0 to k = r , where
A = Actual = fk , and E = Expected = r / 2m that is
ST = (2m / r ) . Σ [ fk - r /2m ]2 from k = 0 to k = r .
The binary sequence pass the test of randomness if ST ≤ ki-square value with
degree of freedom 2m –1. Notice that r / 2m for all sectors must be large enough .
Analysis
For a maximal period sequence of length n , if m = L = the length of the LFSR that generate the sequence then the frequency of each m-bit slide door sector ( except blank state ) is 1 but if m < L then the frequency will be 2(L-m) while choosing m > L cause improper result due to choosing 2m state out of 2L state.
Each binary sequence will pass the test if the statistical value ST is near zero. That is
the randomness test for a binary sequence of length n with m-bit slide door sectors will be accomplished by computing the frequency of each slide door Sectors, fi , computing ST and then checking with the value of ki - square test with degree of
freedom 2m – 1 . In short, the binary sequence pass the test if ST ≤ the value of ki-square test with degree of freedom 2m – 1 , otherwise the sequence is not random.
Algorithm of the Randomness Test
1- Set m to be the length of the slide door sector of a binary sequence
S = s1 s2 . . . sm sm+1 . . .sn .
2- Set r = n – m + 1 and determine
K1 = s1 s2 . . . sm ,
K2 = s2 s3 . . . sm+1 ,
.
.
.
Ki = si si+1 . . . s[i-1]+m ,
.
.
.
Kr = sr sr+1 . . . sm+[r-1] ,
3- Compute the frequency fi of each ki , i = 1, 2, . . . , r .
4- Compute
ST = ( 2m / r ) . Sum [ fj - ( r / 2m )]2 from j = 0 to j = r .
5- If ST ≤ the value of ki-square test with degree of freedom 2m -1 then the
sequence pass the test otherwise it is not .
Applications
The randomness test implemented on maximal period binary sequences
(max system) and binary sequences produced from pless, Geffe, Threshold,
“XOR”,and “AND” systems. Each of the last two systems consists of two LFSR
that produces maximal period sequences combined by “XOR” and “AND”
operations respectively. Clearly the binary sequence produced from the “XOR”
system is random while the binary sequence produced from “AND” system is
non-random.
n chosen to be 1024 while m chosen to be 4, 5, and 7 ( m = 5 = the length of the
letter in ITA2 code). The output of the test is given by the following table where d7 , d5 , d4 are the values of ki-square test with degree of freedom127,31,15 respectively.
n = 1024
m = 7
m = 5
m = 4
ST
d7
ST
d5
ST
d4
Binary
Sequences
Produced
from
Max System
0.12
154
0.03
45
0.01
25
Pless
125.5
154
33.31
45
19.9
25
Geffe
131.25
154
32.37
45
15.9
25
Threshold
144.5
154
20.36
45
7.39
25
“XOR” system
95.2
154
29.3
45
16.7
25
:AND” system
4595.1
154
2271.7
45
6189.1
25
Clearly all, except the last, pass the test of randomness.
Conclusion
Slide door sectors of the binary sequence under consideration play an essential
role in constructing reliable test of randomness since slide door sectors explore
most of the characters of the binary sequence . This test reduces the length of the sequence needed for the test. Although the test is reliable, a binary system produced from stream cipher systems should pass all the known tests together with the test presented in this paper.
REFERENCES
1- Carter, G. “ Statistical tests for randomness”, EISS , karlsruhe,England , 1989.
2- Golomb, S.w “ Shift Register Sequences “ Aegean park press, 1982
3- Niederreiter, H “ The probabilistic theory of linear complexity “ Advances in
Cryptology, Eurocrypt 88 proceeding , vol 330 [ 1988].
4- Rueppel, R.A “ Analysis and design of stream cipher “ , London, 1986.
5- Salman, M.A, Nasir, H.L, and Kadhim, A.M “ Randomness test based on
frequency of LCP of binary sequence , International Journal of Applied Science
and Computations, vol. 12 , No. 2 August 2005 USA