Printer Friendly

Software stream cipher based on pGSSG generator.

ABSTRACT

Secrecy of a software stream cipher based on p-ary Generalized Self-Shrinking Generator (pGSSG) is examined in this paper. Background information for the generator's algorithm is provided. The software architecture and key management for the cipher initialization are explained. Galois Field GF([257.sup.32])and feedback polynomials are chosen for initialization of the generator. In order to examine the secrecy mathematical model of the software system is made. It is proved that the cipher is not perfect but the empirical tests result in less than 0,0125% deviation of the encrypted files' entropy from the perfect secrecy. At last the proposed cipher is compared to four eSTREAM finalists by key length and period.

KEYWORDS

PRNG, pGSSG, Security, Entropy, Encryption, eSTREAM, Stream Cipher.

1 INTRODUCTION

Recently, computer technologies have started to play a huge role in everyday life as well as at the workplace. As the Internet gains more and more popularity and becomes a major means of communication, the term information security becomes more and more important. Encryption has been studied for centuries and the need to find new and better solutions is still present to date.

When transmitting large amounts of data over communication channels such as mobile and wireless networks, and when high speed, low error propagation and resistance to attacks are needed, the use of stream ciphers is recommended. They encrypt each symbol of the transmitted message with a keystream, which is usually generated by a Pseudo Random Number Generator (PRNG), producing binary Pseudo Random Sequences (PRSs).

The elements of PRNGs that are most used in stream ciphers are Linear Feedback Shift Registers (LFSRs), because LFSR of length n can generate a PRS of maximum length T = [2.sup.n]-1.

Since 1969, when the Berlekamp-Massey algorithm [1] was discovered, scientific researchers are looking for new methods of generating non-linear sequences. Researchers use two basic methods to generate nonlinear sequences [2]: structures based on LFSR registers, such as filter generators, combinatorial generators and clock controlled generators, and generators in finite fields such as GMW (Gordon, Mills and Welch) sequences and Bent function sequences.

Recently some clock controlled generators which use a p-ary PRS [3] to create nonlinear sequences have been proposed [4 - 7]. They summarize the work of the Shrinking Generator proposed by D. Coppersmith, H. Krawczyk and Y. Mansour at Eurocrypt'93 [8], and the self-shrinking generator (SSG) proposed by W. Meier and O. Staffelbach at Eurocrypt'94 in [9].

Such generator that uses LFSR in order to produce its output PRSs is the recently proposed p-ary Generalized Self-Shrinking Generator [10]. It is proved that it has long period, is well balanced, has good statistical characteristics and is resistant against exhaustive search and entropy attacks.

As most of the properties of the sequences generated by pGSSG generator have been studied and proved to give good results, it was decided to build a software encryption system based on it. Its encryption properties are tested using the entropy measure [11, 12], which is the matter of this paper. An entropy measure is usually defined in terms of probability distribution. The entropy H(X) of a random variable X is a measure of its average uncertainty. It is the minimum number of bits required on the average to describe the value x of the random variable X [11]. In this study the entropy of the pGSSG PRSs is considered as well as their influence on the symbol distribution in the source and encrypted files.

The paper is organized as follows. First, the working algorithm of p-ary Generalized Self-Shrinking Generator for Galois Field GF([p.sup.n]) is given. Then the architecture of software encryption system based on a pGSSG stream cipher is described. Then the key management is explained. In Section 4 the mathematical model of the system is designed and the entropy is both evaluated and calculated. Section 5 gives a comparison of the proposed stream cipher with four eSTREAM finalists.

2 ALGORITHM OVERVIEW

The proposed p-ary Generalized Self-Shrinking Generator [10], given in Figure 1, consists of a pLFSR register A, whose length will be denoted by L. It generates a sequence ([a.sub.i])i[greater than or equal to]0 with p-ary digits (i.e. ([a.sub.i])i[greater than or equal to]0,[0[less than or equal to][a.sub.i][less than or equal to]p-1)] and 0[less than or equal to]i[less than or equal to]L-1. The multipliers of the feedbacks are given by coefficients [q.sub.1],[q.sub.2],...,[q.sub.L],[q.sub.L][member of][0,1,...,p-1] of the primitive polynomial in GF([p.sup.L]). Every element can remember one p-ary number. The register is initialized by p-ary sequence ([a.sub.0],[a.sub.1],...[a.sub.L-1]).

The pGSSG selects a portion of the output p-ary LFSR sequence by controlling the p-ary LFSR itself using a six-step algorithm (see Fig. 1):

1. The p-ary LFSR A is clocked with clock sequence with period T.

2. The output pLFSR sequence is split into p-tuples [a.sub.pi],[a.sub.pi+1],...,[a.sub.pi+(p-1)],i = 0,1,...

3. If [a.sub.pi]=0 the whole p-tuple is discarded from the pGSSG output, i.e. the output is shrunken.

4. When [a.sub.pi][not equal to]0, the corresponding digit [a.sub.pi+a.sub.pi] in the p-tuple forms the output of the pGSSG. For example, if [a.sub.pi] = 1, then [a.sub.pi+1] is output and the other digits [a.sub.pi],[a.sub.pi+2],..., [a.sub.pi+p-1)] are discard. If [a.sub.pi] = 2, then [a.sub.pi+2], is output and the other digits [a.sub.pi],[a.sub.pi+1],[a.sub.pi+3],...,[a.sub.pi+(p-1)] are discard and so on. If [a.sub.pi] = p-1, then [a.sub.pi+(p-1)] is output and the other digits [a.sub.pi],[a.sub.pi+1],...,[a.sub.pi+(p-2)] are discard.

5. The shrunken p-ary GSSG output sequence is transformed into binary sequence in which every p-ary number is presented with [[log.sub.2](p-1)] binary digits, where [x] is the smallest integer which is greater or equal to x.

6. Every output number i from 1 to p-1 of p-ary GSSG sequence is depicted with p-ary expansion of the number by the formula:

(i-1)+2[[log.sub.2]p-1]-p-1/2 (1)

7. Every p-ary zero in its [i.sup.-th] appearance (i = 1,2,3,...) of the generated p-ary sequence can be represented binary by number [d.sub.i],

[TEXT NOT REPRODUCIBLE IN ASCII] (2)

and initial condition [d.sub.0] = 0.

3 SOFTWARE STREAM CIPHER

A software encryption system has been built. Its main task is to encrypt the transmitted data in advance using a keystream, generated by the output of pGSSG generator. When needed the encrypted data could be put under second encryption with standard methods, such as DES in CBC mode or AES in CCM mode, which are used in the contemporary wireless networks.

3.1 Architecture

The software encryption system is based on symmetric stream encryption algorithm which is initialized by the value of the secret key K. It encrypts the input data stream (the plain text) as simple XOR operation on each byte of the plain text and the keystream received from the pGSSG generator (see Fig. 2).

The software encryption system uses class libraries for software representation of the LFSR register and the pGSSG generator. Although they are designed to be universal, Galois Field GF([257.sup.32]) was chosen for the implementation because of the ease of byte representation and therefore the possibility of faster implementation. Three of the primitive feedback polynomials used to create a pLFSR register with prime p = 257 and length L = 32 are shown in Table 1.

The result of the encryption with that software system is that the amount of data remains the same before and after sending it into the communication channel. If the communication network provides the option for additional data encryption, it is applied as second level of encryption through a standard block cipher AES or DES. For example in WiMAX WLAN networks where data encryption is mandatory the confidentiality and the security will increase using two levels of encryption (Fig. 3).

3.2 Key management

The architecture of the pGSSG generator allows building a symmetrical stream cipher with flexible key management. The key is multicomponent and consists of several elements:

1. L in count p-ary bit components, giving the initial state ([a.sub.0], [a.sub.1], ..., [a.sub.j], ..., [a.sub.L-1]), where [a.sub.j] = 0, 1, ..., p - 1, j = 0, 1, ..., L-1, of the inner LFSR register.

2. L+1 in count p-ary number components, giving the coefficients of the feedback polynomial ([q.sub.0], [q.sub.1], ..., [q.sub.j], ...,[q.sub.L]), where [q.sub.j] = 0, 1, ..., p - 1, j = 1, 2, ..., L, of the inner LFSR register.

3. The last component is set as the initial value of the 'zero' in the output and is a random p-ary number.

If we consider only the initial state as key of the system, it will have length L in p-ary digits. To present each p-ary digit [[log.sub.2]p] bits are needed. Therefore the key length is [L.sub.K InSt] = L.[[log.sub.2 p]]. It can be seen that with p growing the key length is also growing. Table 4.1 shows the minimum length [L.sub.min] of the pLSFR register that ensures key length [L.sub.Kmin] to be 256, 512 or 1024 bits, required by the contemporary cryptographic applications.

The choice of a feedback polynomial is made between preliminarily calculated primitive polynomials in GF([p.sup.L]). Their count [C.sub.poly] is calculated by the formula [13]:

[C.sub.poly] = [phi](p-1)/L, (3)

where [phi](x) = x(1-1/[q.sub.q1]...(1-1/[q.sub.k]) is the Euler phi function, and x is a positive integer with factorization given by x = [q1.sup.e.sub.1]...[qk.sup.e.sub.k]

The count of primitive polynomials with different base p and register length L is shown in table 3.

In order to determine which one polynomial from the list should be used in the cryptographic system [[log.sub.2] Cpoly] bits are needed as shown in the last column of table 3.

Using the fact that [[log.sub.2] p] bits are needed for presentation of the GF(p) elements the total length [L.sub.K] of the secret key can be calculated as:

[L.sub.K] = (L + 1)[[log.sub.2] p]+[[log.sub.2] Cpoly], (4)

where L is the length of the inner pLFSR register.

L different p-ary digit components for the initial state of pLFSR register and one for the initial state [d.sub.0] of the p-ary zero are used.

The length of the secret key K increases both with the growth of the inner register and the value of the prime p. The vast amount of components and the great length of the key K make more difficult and dramatically slow up the process of searching through all different keys when decrypting the received message by malicious users.

There is negative side on growing the prime p, and that is the decreasing the speed of the software encryption system. This is due to the imperfect software registers and the sequence manner of processor's calculations in contrast of a hardware implementation. For this certain software implementation a tradeoff is made in order to find maximum security with minimum slow down. A prime p = 257 is chosen, where all feedback coefficients, the initial state and the initialization zero can be saved into 9 bits and the output of a 257GSSG is a single byte. The register length may vary from L = 8 to L = 34. When these elements are set the secret key K consists of the following components (fig. 4):

* Initial state - [a.sub.L-1][a.sub.L-2]...[a.sub.1][a.sub.0],[a.sub.i]=0,1, ..., p-1;i= 0,1, ...,L-1([L.sub.min]=8,[L.sub.max]=34);

* Feedbacks - [q.sub.L][q.sub.L-1]...[q.sub.1][q.sub.0],[q.sub.i]=0,1, ...,p-1;i=0,1, ...,L-1([L.sub.min]=8,[L.sub.max]= 34);

* Initial zero-z=0,1, ...,p-1

The minimum key length is calculated for the mentioned above initialization values only for base p = 257

[L.sub.Kmin] = 9.9 + 59 = 140 bits, and the maximum key length is: [L.sub.Kmax] = 35.9 + 266 = 581 bits,

The contemporary symmetrical encryption applications/ systems in wireless communication networks most often use secret key with length up to 256 bits, like 3DES with key-length of 168-bits (3 times 56-bit DES key), AES--working with key sizes of 128, 192 or 256 bits. As it can be seen the pGSSG encryption system can have twice longer secret key.

In order to calculate the time for brute force attack the count of all possible keys should be determined. The speed for conducting each test is also needed. The pGSSG based software encryption system is enabled to use all possible bit combinations with a certain length and therefore the count [N.sub.K] of all possible keys is:

[N.sub.k] = [2.sup.L.sub.k], (5)

where [L.sub.K] is the length of the secret key. Table 4 shows the count [N.sub.K] of all possible keys with different length.

The speed each key is tested is a secondary factor, thus it can be assumed that all keys are tested independently and for equal amount of time. This parameter is closely tight to the budget of the organization conducting the attack. The attack is faster when is held on parallel processors due to the assumptions made so far. Each parallel processor checks part of the keys and no interaction between them is needed except for a stop signal when the correct key is found.

4 EXAMINING THE CIPHER SECRECY

Determining the theoretical secrecy of a cryptographic system is a very complex mathematical task. The use of different extended Galois Fields GF(257.sup.L) makes the mathematical cryptanalysis of the pGSSG generator more difficult. To see if this system is usable, many questions need to be answered. They are related to its robustness and security when the attacker is not limited in time and has access to all possible means to analyze encrypted messages. Another question is could a single solution be found and what amount of data should be intercepted to get this solution.

Due to the nonlinearity of modern encryption algorithms, a comprehensive fully mathematically justified answer could not be given. However, the entropy, suggested by Claude Shannon in "A mathematical theory of communication" [14], has found wide application in analyzing these issues since 1948.

4.1 Mathematical Model

As it can be seen on figure 3, the pGSSG based software encryption system ciphers the entire plain text: both the data and the headers of the files. If we consider the byte organization of stored data, the mathematical model of the pGSSG encryption system can be presented as follows.

The system (see Fig. 5) would work with 256 (1 byte) different symbols [a.sub.0], [a.sub.1], ..., [a.sub.1], ..., [a.sub.255] with corresponding probability for appearance P([a.sub.i]), i = 0, 1, ..., 255. As a result of the encryption, these symbols are mapped into cryptograms [b.sub.0], [b.sub.1],..., [b.sub.j], ...[b.sub.255] with probability for appearance P([b.sub.j]),j=0, 1, ..., 255. The keys [K.sub.0], [K.sub.1], ..., [K.sub.n] are equally possible and their maximum count [N.sub.K] depends on the key length. It is possible that one input symbol is converted to a different output symbol when using different keys.

The required and sufficient condition for the system to be completely secret [14, 15] is:

P([b.sub.j])=P([b.sub.j]/[a.sub.i]),j=0,1,...,255. (6)

i.e. P ([b.sub.j] / [a.sub.i]) should not depend on the input symbol [a.sub.i].

Here P([b.sub.j]/[a.sub.i]) is the conditional probability of the encrypted symbol [b.sub.j], provided that the input symbol is [a.sub.i]. That means that it is the sum of the possibilities of all keys that transform the symbol [a.sub.i] into [b.sub.j].

It is known that the perfect encryption system is achieved when the following three conditions are true [Sha49]:

1. Each message is associated with only one cryptogram.

2. The number of keys is equal to number of messages.

3. All keys are equally possible.

Under these conditions, the entropy H of the system is

H(A)=-[n-1 summation over i=0]P([a.sub.i])[log.sub.2]P([a.sub.i])=-[n-1 summation over i=0]1/n[log.sub.2]1/n=[log.sub.2]n (7)

4.2 Experiments using Shannon Entropy

As evident from the mathematical model of the pGSSG software encryption system, it is not absolutely secret because it does not fulfill conditions 1 and 2. Studies are made to answer the question how close the proposed system is to the perfect case scenario in (7). For this purpose over 100 different files are tested. They are distributed equally in the main types: text documents (.doc, .docx, .txt), images (.bmp, .jpg, .png), executable files (.exe), audio files (.wav, .mp3) and archives (.zip, .rar). The frequencies of occurrence of all characters in input and encrypted files are studied and their entropy is calculated. Furthermore, for image files their three color components R, G and B were analyzed separately. In Table 5 the Shannon entropy of the input and output files for four files from each group are shown. Figure 6 demonstrates the distribution histograms of the plain text and encrypted text for different types of files. The results for the three color components R, G and B of the images are respectively shown in Table 7 and Figure 7.

More than 100 sequences of length 1 000 000 bits were generated for each password in order to check how the password transforms into keystream. They were then tested via NIST [16], [17] test suite to obtain their properties.

It is known that the crypto-analytics can use the existing dependencies in the occurrence of characters in various types of information and the model of the standard headers in different file types. That information can help them decrypt the data. Thus they have blocks of plain text and when capturing the encrypted message and they can map it to the corresponding encrypted text. The use of additional level of encryption with the software encryption system eliminates these possibilities as it uniformly changes the values of the symbols for the whole length of the file, including the header part. This conclusion is confirmed by the results shown in Tables 5 and 7.

Analysis shows that the entropy of encrypted files slightly differs from the perfect encryption system entropy with less than 0,001 bit which is 0,0125 % deviation from the perfect secrecy. The entropy of a perfect secrecy system with 256 equally possible symbols is:

H(A)=-[255 summation over i=0]1/256[log.sub.2][2.sup.-8]=8 bit. (8)

As seen on Figure 6 the distribution of symbols in most file types differs radically from the uniform distribution. Exceptions are the archive files whose distribution is largely similar to the uniform and this is no coincidence, because in the archives different algorithms for compressing data are applied. This feature of the archives determines their entropy, which depending on the compression algorithm can reach up to 7.998. However in the distribution of the symbols there are usually detectable peaks of the symbols having a value of 0 or 255 (see Figure 6.c). These anomalies in the histograms are eliminated by the use of encryption with the pGSSG generator.

5 COMPARISON WITH OTHER CIPHERS

In this section we compare our 257GSSG software stream cipher with four eSTREAM finalists from profile 1 which use large LFSR and a nonlinear filter with memory.

The eSTREAM project was launched in 2004 as part of the EU-sponsored ECRYPT Framework VI Network of Excellence [18]. The primary goal of eSTREAM was to help developers how to analyze and design stream ciphers. To promote research in stream ciphers, a call for new proposals has been made. Two specific stream cipher profiles were identified: Profile 1: Stream ciphers for software applications with high throughput and Profile 2: Stream ciphers for hardware applications with highly restricted resources [19]. In addition, to emphases the importance of providing an authentication method along with encryption, two further profiles were proposed: Profile 1A: Stream ciphers satisfying Profile 1 with an associated authentication method and Profile 2A: Stream ciphers satisfying Profile 2 with an associated authentication method.

The original call provoked significant interest and 34 stream ciphers were submitted by the deadline of April 29, 2005. All candidates are evaluated by some significant criteria like security, performance compared to the AES and to other submissions, justification and supporting analysis, simplicity and flexibility, and completeness and clarity over the tree phases of eSTREAM. Only 16 algorithms were advanced to the final phase of eSTREAM by eight in Profile 1 and 2.

Four of the final eight Profile 1 ciphers use Non-Linear FSR (NLFSR). They are CryptMT v3 [20], DRAGON [21], NLS v2 [22] [TEXT NOT REPRODUCIBLE IN ASCII] SOSEMANUK [23].

CryptMT version 3 is a stream cipher obtained by combining a large LFSR and a nonlinear filter with memory using integer multiplication. Its period is proved to be no less than [2.sup.19937]-1. The key-size can be flexibly chosen from 128 bits to 2048 bits, as well as the IV-size. The authors claim that the security level is the same with the minimum of the Key-size and the IV-size.

Dragon is a word-based stream cipher, which state is initialized with 128- or 256-bit key-IV pairs. Dragon uses a single 1024-bit word based NLFSR and a 64-bit memory M which give a state size of 1088 bits. The period for the sequence produced by a 1024-bit NLFSR is [2.sup.512] and since the counter M has a period of [2.sup.64], the expected Dragon period is [2.sub.576].

NLSv2 is a synchronous stream cipher designed for a secret key that may be up to 128 bits in length. NLSv2's stream generator is constructed from a NLFSR and a non-linear filter. NLSv2 is intended to provide security under the condition that no nonce is ever reused with a single key, that no more than [2.sup.80] words of data are processed with one key, and that no more than [2.sup.48] words of data are processed with one key/nonce pair.

Sosemanuk is a synchronous software-oriented stream cipher with variable key length between 128 and 256 bits. Any key length is claimed to achieve 128-bit security. It uses a non-singular LFSR which operates over elements of GF([2.sup.32]). The output Sosemanuk sequence of 32-bit words is periodic and has maximal period [2.sup.320]-1.

Here we consider only software version of pGSSG that is constructed using a single 257-ary LFSR with length L = 32. For one feedback polynomial the initial state of pGSSG is populated using the key K in conjunction with Initial Vector IV. The initial filling of the 257LFSR is done by 32 clock cycles as follows:

[TEXT NOT REPRODUCIBLE IN ASCII]

For a single feedback polynomial the key K consists of 32 in count 257-ary digits, representing the initial state, and one digit for the initial value of 257-ary zero in binary pGSSG sequence. Due to the fact that a 257-ary digit can be presented binary with [[log.sub.2]257] = 9 bits, the key length for one feedback polynomial in bits is 33.9 = 297 bits. The IV length is 16 257-ary digits, which in bits is 16.9 = 144 bits. Any key length is claimed to achieve 297-bit security. The other 250 bits of the key define which of the feedback polynomials is used to constructs the pGSSG. In this case the maximum key length can be calculated as 297 + 250 = 547 bits.

The period for the sequence of 257-ary digits produced by a 257LFSR with length L = 32 is [257.sup.32] - 1. Due to self-shrinking procedure of pGSSG, the output pGSSG sequence is non-linear and its expected period is T = (p - 1).[p.sup.L - 1] =[256.257.sup.31], assuming the pGSSG sequence of 257-ary digits is pseudo-random [10, 24]. Because every 257-ary digit in pGSSG sequence is transformed into [[log.sub.2](257 - 1)]=8 bits, then the period of pGSSG output binary sequence is greater than [256.256.sup.31].8 = [2.sup.8].[2.sup.8.31].[2.sup.3]=[2.sup.259].

To make the design of pGSSG more robust against cryptanalytic attacks we change the primitive feedback polynomial of used 257LFSR before the pGSSG period is produced. The number of distinct primitive polynomials in GF([257.sup.32]) is shown in Table 3.

The comparison shows that 257GSSG provides 297-bit security which is more than three of the eSTREAM finalists shown in Table 6. Only CryptMT v3 offer variable key length from 128 to 2048 bits, which may provide more than 297-bit security. The period of 257LFSR is less than the period of CryptMT v3 and DRAGON, more than the period of the NLS v2 and similar to the period of SOSEMANUK.

6 CONCLUSIONS AND FUTURE WORK

The secrecy of the software pGSSG encryption system is tested with the aim of its mathematical model using the term Entropy. It is proved that the system does not have perfect secrecy but transforms the data into such with uniform distribution of characters. The analysis shows that the entropy of encrypted files compared to the perfect encryption system differs with less than 0,001 bits, which is 0,0125 % deviation from the perfect secrecy.

The comparison with eSTREAM finalists from profile 1 which use large NLFSR shows that software version of 257GSSG with length L = 32 offer 297-bit security which is more than the security of DRAGON, NLS v2 and SOSEMANUK. The period of the pGSSG stream cipher is compared to those of the eSTREAM finalists and it is stated that it is times longer than NLS, similar to SOSEMANUK, but shorter that the other two. This shortness is compensated by simply changing the primitive polynomial of the generator.

The task of decrypting the received data has been made more complicated for the crypto-analytics when using known dependencies in the occurrence of characters in different types of information.

However, there are some practical issues that need to be addressed. First, to measure the degree of randomness of sequences generated by pGSSG some statistic experiments using approximate entropy [25] must be done. Second, to analyze the problem of finding the secret key in pGSSG software system min-entropy can be used [11], which determines the probability of guessing the correct value at first attempt. Moreover, it is necessary to find the average number of guesses needed to determine the key, which is given by the guessing entropy [11].

7 REFERENCES

[1.] Massey J., Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory, vol. 15, no. 1, pp. 122-127, (1969)

[2.] Gong G., Sequence Analysis, University of Waterloo, p. 137, (1999) http://calliope.uwaterloo.ca/~ggong.

[3.] Golomb S., Shift Register Sequences, Aegean Park Press, Laguna Hills, Calif, USA, revised edition, (1982)

[4.] Kanso, A. Clock-controlled generators. University of London, (1999)

[5.] Tashev, T., Bedzhev, B., Tasheva, Zh. The Generalized Shrinking-Multiplexing Generator, ACM International Conference Proceeding Series 285, Article number 48, Proceedings of the 2007 international conference on Computer systems and technologies CompSysTech '07, (2007)

[6.] Tasheva, Z., Bedzhev, B., Stoyanov, B. P-adic shrinking-multiplexing generator, Proceedings of the Third Workshop - 2005 IEEE Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, IDAACS 2005, pp. 443-448, (2005)

[7.] Tasheva Zh. N. Design and Analysis of 3-ary Generalized Shrinking Multiplexing Generator, International Journal of Advance in Communication Engineering 4 (2), pp. 129-140, (2012)

[8.] Coppersmith D., H. Krawczyk, Y. Mansour, The shrinking generator, Advances in Cryptology--EUROCRYPT'93, vol.773 of LNCS, Berlin, Springer-Verlag, pp. 22-39, (1993)

[9.] Meier W., O. Staffelbach, The self-shrinking generator. In A.De Santis, editor, Advances in Cryptology--EUROCRYPT '94, vol.950 of LNCS, Berlin, Springer-Verlag, pp. 205-214, (1995)

[10.] Tasheva A. T., Tasheva, Zh. N., Milev, A. P., Generalization of the Self-Shrinking Generator in the Galois Field GF(pn), Advances in Artificial Intelligence, vol. 2011, Article ID 464971, 10 pages, (2011) doi:10.1155/2011/464971

[11.] Cachin, C. Entropy measures and unconditional security in cryptography. Konstanz: Hartung-Gorre, (1997)

[12.] Gray R., Entropy and Information Theory, Springer, Second Edition, (2011)

[13.] Lidl, Rudolf. Finite fields. Vol. 20. Cambridge University Press, (1997)

[14.] Shannon, C. E. "A mathematical theory of communication." ACM SIGMOBILE Mobile Computing and Communications Review 5, no. 1, pp. 3-55, (2001)

[15.] Shannon, C. E. "Communication theory of secrecy systems." Bell system technical journal 28, no. 4, pp. 656-715. (1949)

[16.] NIST Statistical Test Suite, Version 2.1.1., August 11, (2010), http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

[17.] Rukhin A., J. Soto, et.al, NIST Special Publication 800-22rev1a: A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications, (2010), http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf.

[18.] Babbage, Steve, et al. "The eSTREAM portfolio." eSTREAM, ECRYPT Stream Cipher Project. April 15, (2008). http://www.ecrypt.eu.org/stream/portfolio.pdf.

[19.] ECRYPT. The eSTREAM project, http://www.ecrypt.eu.org/stream/

[20.] Zhang, Haina, and Xiaoyun Wang. "On the Security of Stream Cipher CryptMT v3." IACR Cryptology ePrint Archive 2009, pp. 110, (2009)

[21.] Chen, Kevin, et al. "Dragon: A fast word based stream cipher." Information Security and Cryptology-ICISC 2004. Springer Berlin Heidelberg, Seoul, Korea, pp. 33-50. (2005)

[22.] Hawkes, Philip, et al. "Specification for NLSv2." New Stream Cipher Designs. Springer Berlin Heidelberg, pp.57-68. (2008)

[23.] Cho, Joo Yeon, and Miia Hermelin. "Improved linear cryptanalysis of SOSEMANUK." Information, Security and Cryptology-ICISC 2009. Springer Berlin Heidelberg, pp. 101-117. (2010)

[24.] Tasheva, A., Nakov O., and Tasheva, Zh. About balance property of thep-ary generalized self-shrinking generator sequence. In Proceedings of the 14th International Conference on Computer Systems and Technologies (CompSysTech '13), ACM, New York, NY, USA, pp. 299-306. (2013)

[25.] Pincus S., B. H. Singer, Randomness and degrees of irregularity, Proc. Natl. Acad. Sci. USA. Vol. 93, pp. 2083-2088 (1996)

Antoniya Tasheva (1) , Zhaneta Tasheva (2) , Ognyan Nakov (1)

(1) Technical University of Sofia, Bulgaria 8 Kliment Ohridski blvd., Sofia 1000, Bulgaria (2) National Military University "Vasil Levski", Faculty of Artillery, Air Defense and Communication and Information Systems, Bulgaria, 1 Karel Shkorpil Str., Shumen 9700, Bulgaria atasheva@tu-sofia.bg, zh.tasheva@mail.bg, nakov@tu-sofia.bg

Table 1. Feedback polynomials used in pGSSG.

No  Feedback Polynomial

1   [x.sup.32] + x + 10
2   [x.sup.32] + 75 [x.sup.2] + 174 x + 33
3   [x.sup.32] + 188 [x.sup.2] + 200 x + 107

Table 2. Minimal length of the pLSFR register to ensure key
length [L.sub.K Inst] of 256, 512 or 1024 bits

p                                      [L.sub.min] of pLSFR for
                                   256 bits   512 bits   1024 bits

2                                  256        512        1024
3                                  128        256        512
5, 7                               85         171        342
11, 13                             64         128        256
17, 19, 23, 29, 31                 52         103        205
37, 41, 43, 47, 53, 59, 61         43         86         171
67, 71, 73, 79, 83, 89, 97,
101, 103, 107, 109, 113, 127,      37         74         147
131, 137, 139, 149, 151, 157,
163, 167, 173, 179, 181, 191,
193, 197, 199, 211, 223, 227,
229, 233, 239, 241, 251            32         64         128

Table 3. Count of primitive polynomials with different powers and bases

 p    L       Count of primitive polynomials                 Bit Count

 17   32    18976458037657197225461286734659584000            124
 61   32    10244854334997082026962604386814833429
            237905489920000000                                183
127   32    13788941890097745057084265918295403933
            4599366308071077551957606400                      217
167   32    85864901880654498516021075274859050725
            9234088656177980910291910656000a                  229
257    8    582729142999449600                                 59
257   10    37204727422640848896000                            75
257   16    5511978689381920798272782377943040000             122
257   24    5446826515491553717757610913610783806
            0351092424704000000                               185
257   32    98767885865554779011732725900114323996
            7117047735833824574876556711690240000             250
257   34    8294326319916878032224707997223353835
            9404412641258708571048665491964779770675200       266

Table 4. Count of possible keys of length [L.sub.K]

   Key length          Count of possible different keys [N.sub.K]
[L.sub.K] [bits]

80                     1208925819614629174706176
96                     79228162514264337593543950336
112                    5,1922968585348276285304963292201.[10.sup.33]
128                    3,402823669209384f6346337460743177.[10.sup.38]
140                    1,3937965749081639463459823920405.[10.sup.42]
256                    1,1579208923731619542357098500869.[10.sup.77]
512                    1,3407807929942597099574024998206.[10.sup.154]
546                    2,3034438628061165479989957159352.[10.sup.164]
581                    7,9145728471393450899360806726287.[10.sup.174]

Table 5. Entropy of input and pGSSG encrypted files.

No  File                 Password

1.  explorer.exe         2345explorer
2.  encryptPhD.exe       Fast2Enc%(!
3.  notepad++.exe        ++[TEXT NOT REPRODUCIBLE IN ASCII]++
4.  WinRAR.exe           KoM[TEXT NOT REPRODUCIBLE IN ASCII]ReC
                         [TEXT NOT REPRODUCIBLE IN ASCII]Q
5.  CompleteSet.docx     2013BCPC
6.  DiplomnaRabota.docx  Info4[TEXT NOT REPRODUCIBLE IN ASCII]
7.  document.docx        [TEXT NOT REPRODUCIBLE IN ASCII]*Tekst
8.  TrainingTasks.docx   Passw0rd
9.  presentation.pptx    Imagine8No
10. IFRToolLog.txt       [TEXT NO REPRODUCIBLE IN ASCII][section]n&
11. leMouse.rar          el^gAto-te
12. Raboti.rar           lANg25cop18%
13. Zadaniq.rar          worry35ePIc^
14. Zadaniq.zip          rAts24mOd=
15. ALARM.WAV            VarY39eRns&
16. cat8.wav             NiX^pEn=Dry1
17. TU.bmp               myUniversit1
18. lenna.bmp            vAN83scoUR@
19. snowman.jpg          faLL!kOR?jiltS
20. sozopol.jpg          idS?OcHRy65

No  File                   Entropy of                Entropy of
                           Input File               Encrypted File

1.  explorer.exe         5.872596706508290        7.999598134607586
2.  encryptPhD.exe       7.631900643959939        7.998833667709484
3.  notepad++.exe        6.091405544356415        7.999648675667926
4.  WinRAR.exe           6.469161170026363        7.999644709803738
5.  CompleteSet.docx     7.948642291913700        7.998595024152175
6.  DiplomnaRabota.docx  7.524045264552306        7.989391747378668
7.  document.docx        7.910834642297916        7.998354864955056
8.  TrainingTasks.docx   7.948642291913700        7.998405935750952
9.  presentation.pptx    7.937660319385949        7.999896904729666
10. IFRToolLog.txt       4.714971677469938        7.999566854515114
11. leMouse.rar          7.986186549835893        7.998523780587349
12. Raboti.rar           7.999329046994613        7.999986138240808
13. Zadaniq.rar          7.999026651474129        7.999558585297283
14. Zadaniq.zip          7.997750400646980        7.999661066662499
15. ALARM.WAV            6.871613007127728        7.997961560964973
16. cat8.wav             4.572460198612183        7.998654459803242
17. TU.bmp               7.735134585817764        7.999598750116132
18. lenna.bmp            5.682224748742369        7.999696018375432
19. snowman.jpg          7.927340915095799        7.995697933926553
20. sozopol.jpg          7.966401975045295        7.997800281093063

Table 6. Comparison of Key length, IV length and Period of
Stream Ciphers

Stream Cipher       Key Length,    IV Length,
                      bits          bits

CryptMT v3          from 128       from 128
                    to 2048        to 2048
DRAGON              128 or 256     128 or 256
NLS v2              up to 128
SOSEMANUK           from 128       128
                    to 256
pGSSG, p = 257      from 297       144
                    to 547

Stream Cipher       Period

CryptMT v3          [greater than or equal to][2.sup.19937] - 1

DRAGON              [2.sup.576]
NLS v2              [less than or equal to][2.sup.80] words
SOSEMANUK           [less than or equal to][2.sup.320] - 1

pGSSG, p = 257      256.[257.sup.31].8 > [2.sup.259]

Table 7. Entropy of the colour components R, G and B of the input and
pGSSG encrypted images.

                                              Input Image
No  Image             Password             R       G       B

1.  medal.bmp         *&^%^%sG           6.0038  5.9726  6.0043
2.  banner.bmp        *&*B"}@E           7.3162  6.9769  6.8664
3.  DarkDoor.bmp      Poiuytr^B&         7.2023  7.0943  7.0060
4.  pepper.bmp        M*b%V)JY           7.3388  7.4962  7.0583
5.  lenna.bmp         12345678           5.0465  5.4576  4.8001

                                            Encrypted Image
No  Image             Password            R       G        B

1.  medal.bmp         *&^%^%sG        7.99928 7.99943  7.99937
2.  banner.bmp        *&*B"}@E        7.99977 7.99973  7.99974
3.  DarkDoor.bmp      Poiuytr^B&      7.99934 7.99935  7.99924
4.  pepper.bmp        M*b%V)JY        7.99930 7.99924  7.99935
5.  lenna.bmp         12345678        7.99914 7.99918  7.99904
COPYRIGHT 2014 The Society of Digital Information and Wireless Communications
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

 
Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:p-ary generalized self-shrinking generator
Author:Tasheva, Antoniya; Tasheva, Zhaneta; Nakov, Ognyan
Publication:International Journal of Cyber-Security and Digital Forensics
Article Type:Report
Date:Apr 1, 2014
Words:6016
Previous Article:Online handwritten signature recognition by length normalization using Up-Sampling and Down-Sampling.
Next Article:The consequences of state-level intrusions: a risk worth taking?
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters