STREAM BLOCK STARTING WITH ZERO BITS

Get Complete Project Material File(s) Now! »

Key generator

Stream key is a sequence of ‘n’ bits, which is determined by het key generator function. If the key generator function generates the same stream key length at each iteration, the function is called fix length key generator otherwise variable key generator. Random stream cipher can use both fix and variable length key generator functions. Later on, it will be discussed that using variable key generator makes cipher stronger to breakdown.
Due to the fact that random stream cipher does not have its own method to generate stream key, so current methods such as rabbit stream cipher, vest stream cipher and so forth are used to undertake generating stream key. In the present work, fixed length stream key methods are discussed.

Fixed length key generator

There is variety of stream cipher methods working with fixed length stream keys. Each of them has a number of vulnerabilities plus a number of advantages that makes it considerable. For instance, RC4 (also known as ARC4 or ARCFOUR) is widely used owing to its high speed. Somehow, there are a number of known attacks to break down RC4, which can be enumerated as its disadvantages.
As another example, rabbit stream cipher [1] is a pretty new method, which was invented in 2003. Rabbit stream cipher is very fast and reliable in comparison with other methods. Besides, the key length which rabbit generates is suitable and can easily be integrated with random stream cipher. Taking to account that there are no stream cipher method without vulnerability, rabbit stream cipher has been chosen as the fixed length key generator of current implementation of random stream cipher.
Table 2.1 depicts stream ciphers methods and compares them using some criteria such as speed, best known attack and so forth. The table has been taken from reference [2] which is an online dictionary and free encyclopedia. As it can be seen in the table, rabbit stream cipher is a pretty new method (it was invented in 2003). By considering speed and best known attacks columns in the table and making a simple comparison, it is obvious that rabbit stream cipher is one of the fastest and most reliable methods.

Rabbit stream cipher in general

The following explanation of rabbit stream cipher is a summarization of reference [1]. Briefly, it uses a 128-bit secret key to initialize the internal state and iterates the system 4 times. Rabbit stream cipher generate 128-bit stream key at each iteration which is a combination of each internal state bits. The size of the internal state is 513 bits divided between eight state variables. The variables are updated by eight coupled non-linear integer valued functions. The counters guarantee that the stream keys will not be repeated during the iterations.

Stream Block

Due to the fact that length of blocks is independent from stream keys, hence, Stream Blocks determination can be done at the first step. A proper block should have the following criteria:
• Blocks are taken from binary digits of the plain text.
• Blocks length should be dividable by 8(if the plain text is not dividable by 8 we can modify it by adding 0 bit to the end of the plain text to make it dividable by 8 and it does not affect the original plain text)
• The first bits of block should be nonzero.
• Blocks length should be generated randomly.
• Every plain text must at least have two stream blocks

Stream block starting with zero bits

Note that, for zero stream blocks, regardless of the stream key, the cipher would be zero (it can be a weakness in cipher) and for stream blocks that start with zero bits or in another word the stream blocks which their first byte is smaller than 128 in decimal, after decryption, the first zero bits would be lost, because zeros in the left of binary digits are not counted. Hence, the firs bits of stream blocks should not be zero.
The solution is to XOR the first byte of such stream blocks with 255 (11111111 in binary) and informs another party by modifying the cipher (one bit can be allocated in each stream cipher).

Number of stream blocks in a plain text

A plain text that has been divided into one stream block is vulnerable when an attacker has access to encryption machine, thus, he can encrypt his own plain text then compare the plain text with the cipher to find the stream key. When the plain text has more than two blocks and its length is big enough, owing to the fact that the stream block are chosen randomly, even if the attacker has the plain text with the cipher he will not be successful to find the stream keys. Therefore, increasing the block numbers and plain text length would result in high uncertainty probability.
Stream blocks length is independent from stream key; however, stream blocks number depends on stream key length despite the fat that it is randomly determined. Let MRL be the minimum stream key length that stream key generator function can generate which in fix length key generator it would be constant and in variable key generator that generates stream keys with the length in the rage [j, k] (where j<k), it would be j. ML and M are plain text length and the plain text. Therefore:
MRL=min ({len (r)})
ML=len(M)
2 < SBN < 2*ML/MRL
Where, SBN is stream block number. The above formula is suggestive of the fact that SBN should be at least 2 and 2*ML/MRL is the maximum value of SBN. Hence, the rang to random SBN; depends on both ML and MRL.

Plain text normalization

As it is mentioned the maximum value of SBN is 2*ML/MRL. But consider the case in which ML < MRL, so, the maximum value would be less than 2. In this case the plain text should be normalized by adding E zero byte to the end of the plain text so that the plain text length will be increased. E can be obtained randomly from the following range: MRL-ML < E < 2*MRL-ML
Where MRL-ML is the minimum number of zero bytes that should be added to the end of the plain text to yield ML>=MRL. Randomly choosing E would increase uncertainty probability.

Overall process of generating stream blocks

The first step in random stream cipher is stream blocks determination. Stream block generator should feed back the information such as:
● Stream blocks number
● Stream blocks length
● XOR state
● Plain text normalization (if necessary)
First of all, plain text should be checked for normalization. If the plain text length was less than the minimum stream keys length, adding enough zero bytes to it would normalize the plain text.
The next step is randomly determination of stream blocks number from the range depending on the minimum value of the stream keys. As it was mentioned the range that SBN should be chosen from should be: 2 < SBN < 2*ML/MRL
After ward, stream blocks are specified one by one with a random length .Let LS be the remaining size of the plain text after taking i-1 stream blocks. i-th stream block length would be randomly taken from the range [1, LS-1].
Eventually, the first bits of stream blocks were zero or in another word, the first byte of stream block was smaller than 128 in decimal, the first byte is xored with a number bigger than 128.
Here is the Stream block generator Pseudo code:
random_stream_block_number()
for i 0 to stream_block_number-1
do
random a number from 0 up to data_size
if it is not repeated before
add it to array r[]
sort out array r[]
for I 0 to stream_block_number
do
stream_block[i]= r[i-1]- r[i]
First random_stream_block_number randomly selects a number in the mentioned range of stream block number and loads stream_block_number with that value. Afterward, a number is obtained randomly from 0 up to data_size (the plain text size) and it is added to a temporary array if and only if it’s not repeated before. In order to find out that the number has not been chosen before a simple binary search is performed on the temporary array r[]. After loading r[] with not repeated numbers between 0 to data_size, it should be sorted by a fast sorting algorithm in order to achieve stream_block. Using sorted r[], stream_block[i] (i-the stream block size) can be acquired by subtracting i-1-th element of r[] by its next element.

Stream cipher generator

This part is responsible for combing the stream block and stream key and generates the stream cipher. Unlike usual stream cipher the function does not use XOR operation, instead it uses division to generate cipher in the way that stream block is the dividend, stream key is the divisor and finally the quotient will be the cipher.
Considering a plain text divided into n stream blocks, the function simply divides each block by the stream key, which is used in decryption as well.
The message is divided into n stream blocks (b1, b2,.., bn). Let (r1, r2,.., rn) be a sequence of stream keys in which ri is corresponded to bi. And (c1, c2… cn) is the sequence of generated stream ciphers. Each stream block is combined with its stream key at i-th iteration:
ci = bi / ri
h (bi , ri )=ci
The stream block can be retrieve from the cipher by:
bi = ci * ri

READ  The Efficient Market Hypothesis

Fraction part

The problem in the formula using to encrypt the stream blocks is usage of division and therefore the result might have fraction part. It is possible to limit the fraction part, for example considering only n digits for the fraction part that both parties agree on the value of n. But fraction parts do not give an integer most of time:
b1=20
r=3
n=4
Encrypt: c1=20/3=6.6667
Decrypt: b1=6.6666*3=19.9998
As it can be seen in the above example another party gets 19.9998 after decryption, whereas the actual stream block was 20. At this point, it is feasible to guess the actual number by rounding up the result to the closest integer number. It is better not to have a small n as a matter of fact it makes it hard to round up the stream cipher when the stream key and stream block get bigger.
When n was chosen properly (not to small) it is guaranteed that another party can obtain the correct message by rounding up the achieved result from decryption.

Size of fraction part

The size of the fraction should be equal to maximum length of stream keys. It should be constant for every fraction part in the cipher even if the actual fraction part is less than the maximum length of the stream keys.
FPZ= fraction part size
FPZ=max({len(r1),…,len(r2)})
Considering the following division formula, the goal is to have b0 in the rang [b-1, b] so that it can be rounded up to obtain b:
a = b/c
b0 = a*c
len(a) = n
a = i . f
Where, i is the integer part of the quotient, f is the fraction part and len (x) function returns the size of x. if len(f) < len(c), so b can be gained without needing b0 to be rounded up. Assume that len (f) is infinite or len(f) > len(c). It can be shown that counting only len(c)-1 first digits of ‘f’ would be sufficient to obtain b in the rang [b-1, b]. 0
Lemma 1: the j-th fraction part digit multiplying by a number with size n results in a number with size n-j (in binary). K is the number in the rang (0, 1) with only a 1 bit at the j-th place of the fraction part.
n+1
0 =< a <2
a * k= b
0=<b< 2n-j+1 len(b) = n-j
Using the above lemma and replacing n-1 by j, it can be concluded that having n-1 digits for quotient fraction part after multiplying it with the dividend will result in a number with the same size as the dividend, in another world, it gives a number in the range [b-1, b], where b is the dividend.

Stream cipher format

Generated cipher should contain all information that another party has to know to decrypt it.
The information to be contained is as following:
1. Xor state
2. Integer part
3. Fraction part
Xor state can be shown by allocating a first bit of stream cipher to it. Bit 1 can be suggestive of a xored stream block and in the contrast, bit 0 shows that the stream block has not been xored.
Integer part can be represented immediately after the xor state bit by allocation some bytes as its offset. Besides, there is a need to have and offset to determine the end of integer part so that the integer part can end in the middle of a byte.
Due to the fact that fraction parts have the same length (maximum length of stream keys) and both parties aware of that, hence, there is no need to have an offset to show its length and can follow the integer part to complete the stream cipher.

Analysis of Random stream cipher

In random stream cipher, stream blocks play an important role. As it was mentioned, Stream blocks number and stream blocks length are both determined randomly, and this random factor results in high uncertainty probability to obtain the stream key having the plain text and the cipher text. In another word, chosen plain text and chosen cipher text attacks would be disabled for random stream cipher. In addition to variety of cipher having one message, the generated ciphers can differ in their length too. Here are two different ciphers for one plain text:
Plain text: Hello Random Stream Cipher!
Cipher number 1: ## #Žèª€#òÝJUA•„#Š´# ##@## # ##jñ#vÁîã
Cipher number 2: ## # #;¢ª#òÝJUA”## #“À »C»i›¸Ò¾úJ »ueŸp:
Note that, the ciphers differ with each other whereas the plain text is the same.

Differences with other types of stream cipher

The differences between random stream cipher and current types of stream cipher are mentioned here.
1. The most important difference is that in usual stream cipher cryptography, the function to combine stream key and plain text uses XOR operator. But in random stream cipher, the function uses division on the plain text blocks and the corresponding stream keys.
2. In usual stream cipher cryptography, length of key should be equal to length of plain text blocks, but in random stream cipher, it does not matter, and key length can be varied from plain text blocks.
3. In usual stream cipher cryptography, length of cipher text is equal to its plain text, but in random stream cipher, the cipher is different from its plain text.
4. In random stream cipher, for the same plain text and secret key, there are many ciphers to be corresponded to. In another word, the cipher is obtained randomly from a wide range depending on the plain text. It is the thing that does not exist in current cryptography methods.
The first one, referring to the difference in plain text and stream key combination method, is suggestive of the fact that random stream cipher needs more calculation than other methods using xoring method. Hence, random stream cipher works slower than other stream cipher types.
The rest of the differences all refers to the generated cipher and the random factor that causes the cipher to be obtained randomly (but in a specific wide range depending on the plain text). Focusing on the random cipher will clarify the differences.

Random cipher

In random stream cipher, randomly generating stream blocks results in different ciphers with the same secret key. It is simply because of the fact that, changing the dividend value results in changing the quotient by having the same divisor, here the dividend is the stream block, the quotient is the stream cipher and the divisor is the stream key. Therefore, random factor affects the cipher when it comes to separate the stream blocks, which is done randomly.
c= b / r
r is constant, b is variable c is variable
Let’s determine how many different ciphers can be generat ed for a plain text with a constant key. Consider that fixed length key generator is used and the length of stream block is 128-bit. M is the plain text with the length N. If K is the variable containing the stream blocks number; therefore for every N we have the following equation: b1+b2+…+bk=N Where bi is the i-th stream block size.

Table of contents :

1. INTRODUCTION
1.1. CLASSIFICATION
1.2. RANDOM STREAM CIPHER IN GENERAL
1.3. PROBLEMS AND DIFFICULTIES
1.4. REPORT OUTLINES
2. KEY GENERATOR
2.1. FIXED LENGTH KEY GENERATOR
2.1.1. Rabbit stream cipher in general
3. STREAM BLOCK
3.1. STREAM BLOCK STARTING WITH ZERO BITS
3.2. NUMBER OF STREAM BLOCKS IN A PLAIN TEXT
3.3. PLAIN TEXT NORMALIZATION
3.4. OVERALL PROCESS OF GENERATING STREAM BLOCKS
4. STREAM CIPHER GENERATOR
4.1. FRACTION PART
4.2. SIZE OF FRACTION PART
4.3. STREAM CIPHER FORMAT
5. ANALYSIS OF RANDOM STREAM CIPHER
5.1. DIFFERENCES WITH OTHER TYPES OF STREAM CIPHER
5.2. RANDOM CIPHER
5.3. SUBSTITUTION ATTACK ON RANDOM CIPHER
6. RANDOM STREAM CIPHER IMPLEMENTATION
6.1. RSC.CPP
6.1.1. Key generator part
6.1.2. Stream blocks generator part
6.1.3. Encryption and decryption part
6.2. BIT_VECTOR.CPP
6.3. ARRAY_UTIL.CPP
7. CONCLUSION
7.1. ADVANTAGES AND DISADVANTAGES
7.2. USABILITY
8. REFERENCES
APPENDIX A
A.1. RANDOM STREAM CIPHER SOURCE CODE

GET THE COMPLETE PROJECT

Related Posts