FIELD OF THE INVENTION

The present invention relates to a computer implemented and/or a -hardware implemented method and apparatus for data encryption and/or decryption using "Synchronous Stream Cipher" (SSC) and/or "Block Cipher"

BACKGROUND AND THE PRIOR ART

In computer science, "encryption" denotes alteration of data using a code and a secret key to make the data unintelligible. Decryption is its reverse processes. This prevents unauthorized access of the data. In other words, encryption is a process of transforming information using an algorithm, called as a cipher to make it unreadable to anyone except those possessing special knowledge or a key. In the present days number of industries carries out data encryption and/or decryption as a routine to increase the security of data transmitted via the Internet.

A cipher is a combination of a cryptographic algorithm and a secret key that decides the encryption details in the specific case. Encryption systems are divided into two branches, symmetric using a secret-key or, asymmetric using a public-key and private-key pair. In a symmetric system, the sender and receiver have the same secret key used for both encryption and decryption. In an asymmetric system the sender uses the receiver' s publicly available public-key to encrypt but the receiver decrypts the encrypted data with a private-key. Symmetric cryptosystems are usually divided into block ciphers and stream ciphers. The block ciphers operate with a fixed transformation of a large block of plaintext data such as 64 bits or 128 bits blocks. The stream ciphers operate on stream of plain-text and cipher-text one bit or at a time. The stream cipher can be synchronous or asynchronous.

Block ciphers operation involves encryption of a plaintext block into a ciphertext block using a secret key (key is initialized through initialization phase) . The encryption phase comprises core, a sequence of cryptographically nonlinear reversible operations to mix the plaintext with the initialized key. During decryption all the operations are performed in reverse order to get the plaintext back. The core operates in any of the standard modes like electronic-code- book (ECB) , cipher block chaining (CBC) , output feedback (OFB) etc. The core during encryption takes plaintext blocks as its input and generates the corresponding ciphertext blocks in each round of operation. During decryption phase the core, in decryption mode, takes ciphertext blocks as its input and generates the corresponding plaintext blocks in each round of operation.

Another general method for block encryption is a cascaded method. This is similar to normal block encryption except that the encryption and/or decryption comprise more than one core, which are cascaded. Due to presence of cascades, the ciphertext generation becomes more random and complex. US4078152 discloses a block-cipher cryptographic system in which a unique user key and a means for modifying an input data block are used. The cipher performs a prior, key- controlled transformation operation of the input data by using the means. The means comprises components for extracting a segment of data and combining said segment with the input data block. A discrete valued function is used for combining process A means for detecting and cryptographically transforming short blocks of data is also disclosed in this document .

US6243470 discloses a method and apparatus for encryption and decryptions using a block cipher algorithm and an advanced symmetric key. In each round of operation different block sizes and key sizes are used. The patent also discloses a different sub-key. Encryption is computed using a variable number of rounds of mixing, permutation, and key-dependent substitution. Decryption uses a variable number of rounds of key-dependent inverse substitution, inverse permutation and inverse mixing. According to this, the variable length sub- keys are data-independent and precomputed.

Stream cipher algorithm is based on generating a pseudorandom keystream to encrypt a stream of plaintext to generate a stream of incomprehensible text known as ciphertext. Examples on stream ciphers are: RC4, SNOW, ECSC-128 and many other ciphers. The core of those ciphers are basically based on simple logical operations and bit manipulation as in RC4, Linear Feed-Back Shift Registers as in SNOW or complex mathematical problems as in ECSC-128. The encryption phase is designed to encrypt the given plaintext by applying XOR operation between the keystream bits and the plaintext bits. -

A synchronous stream cipher encrypts and/or decrypts one or few bits of message every time. It generates a pseudo random key-stream, which is of the same length as of the message, which has to be encrypted or decrypted, and XOR it with the message .

Key-stream generator comprises a core, which works under a secret key. The key-stream generator operates repeatedly until the output key-stream is sufficient to encrypt the total plaintext. The core comprises an internal state, output function, and an update function. In every round of key-stream generation, the output function computes the output as a function of internal state and the update function updates the internal state to the next step. In this manner all the internal-states and output keystreams are connected through the output function and update functions

US6587562 discloses a method and apparatus for a clock- controlled encryption using a synchronous stream cipher. The diagrammatic plan of the key stream generator is shown in Fig. 1. Here the key-stream generator comprises plurality of cores. These cores are arranged in parallel. Associated with each core there will be a number selector and a set of integer numbers corresponding with each of the number selectors. The key-stream generator also contained a control sub-generator, which is a linear feedback shift register, a finite state machine. According to this document, in a particular round of key-stream generation, the control sub-generator generates its output into the number selectors and gets updated. Depending on the input value from control sub-generator and the associate set of integers, each number selector selects at least one core to operate in each round of key-stream generation. According to this patent, the output of the entire cores, independent of whether they are selected or not in the particular round, will be combined by a function means to generate output of key-stream. The function can be a linear function or nonlinear function. This document discloses that the output from such function means is combined or XORed with a bit of plaintext to generate corresponding bit of ciphertext .

The drawbacks of the above disclosed method and apparatus is that the operation of different number of cores in different rounds gives clear information of how many numbers of cores are under operation in a particular round of key-stream generation through side-channels. This allows the attacker to implement attacks on control sub-generator and get knowledge of the key. Another drawback is the low performance of the method, because of average number of cores under operation in a particular round of key-stream generator is more than one. The requirement of additional hardware for control sub- generator is another disadvantage, when the method has to be implemented on restricted resource environment like smart cards. Again control sub-generator is a finite state machine its output will have a period in turn the selection of cores consists a period. As the internal size of sub-generator is small, size of this period is also small. This knowledge can be useful to implement attacks on this system. US6415032 discloses an encryption technique using both stream cipher and block cipher. These ciphers used a method for generating a pseudo-random sequence of integers, and the method is applied to the encryption of messages. The disclosed method uses a key K and a pair of prime numbers p and q, where q=2p+l. According to this document, segment of a least significant bit is selected from each preformed integer value. This segment of bits is then used to encrypt a message using a selected encryption algorithm such as the XOR algorithm. According to it, the prime numbers p and q are larger than key K hence the repeating period of the sequence of integers is larger than that permitted by the bit length of K.

The drawbacks associated with the key-stream generator of synchronous stream ciphers are that they lack ambiguity at how the internal-states and key outputs are connected with each •other. They also lack ambiguity at how a particular key output is generated from the internal-state. In the disclosed ciphers, the success rate of the statistical attacks does not decrease with the increase of number of key-stream outputs required by the attack rather success rate of the attacks increases with the increase in number of key-stream outputs available to the attacker. Also, in block encryption different messages are encrypted identically, under a same key, which allows an attacker to collect enough message blocks to implement his attack. The disclosed methods, also, do not allow taking the advantage of capacity of parallel computation available on hardware and software implementations using multi-core processors. The present invention is aimed in overcoming the drawbacks present in existing encryption ciphers. The present invention can be used both for block cipher and stream ciphers and can also be used as PRNG (pseudo random number generator) . The new principle underlying the present invention is to introduce more ambiguity in the process of ciphertext generation. The encryption phase comprises a number of parallel cores but uses algorithms by which a single core is selected to be used at each round in generating ciphertext. Encryption processes uses a key dependent output mask to add further ambiguity. The present ciphers show resistance to shortcut attacks without compromising at the performance.

Again the proposed block cipher and stream cipher encryption methods has feature like ambiguity in the relation between a plaintext block and corresponding ciphertext block. Again the proposed cipher shows decrease of success rate of attacks with the increase in number of message blocks required by the attack. These are compatibleness to software and hardware implementations and capable of using parallel computation.

OBJECTS OF THE INVENTION

Accordingly one object of the present invention is to obtain an apparatus for the key generation of SSC with features to overcome the drawback of prior art.

Another object of the present invention is to provide of a block cipher for encryption and/or decryption of data with high resistance. Another object of the present invention is to provide a computer-implemented and/or hardware-implementable block cipher and/or stream cipher method for data encryption and/or decryption.

Yet another object of the present invention is to provide a PRNG.

SUMMARY OF THE INVENTION

According to one aspect of the present invention there is provided

an apparatus for encryption and/or decryption of data comprising:

plurality of cores, each of said cores includes an input in form of plaintext and an output data which is a function of key and plaintext/ wherein said each core comprises set of first variables corresponding to said input and output; and

a set of second variables being updated for each round of encryption/decryption;

control means comprising respective input of said variables and respective outputs

wherein said control means selects any one core in each round of encryption/decryption so as to generate core outputs; and means for combining generated data items of each of the cores comprising core outputs as inputs and outputs the result as keystream in case of SSC and as ciphertext in case of block ciphers .

According to another aspect of the present invention there is provided a method for encryption and/or decryption of data comprising:

plurality of cores, each of said cores includes an input in form of plaintext and an output data which is a function of key and plaintext; wherein said each core comprises set of first variables corresponding to said input and output; and

a set of second variables being updated for each round of encryption/decryption;

control means comprising respective input of said variables and respective outputs

wherein selection of any one core in each round of encryption/decryption is done by said control means so as to generate core outputs; and

means for combining generated data items of each of the cores comprising core outputs as inputs and outputs the result as keystream in case of SSC and as ciphertext in case of block ciphers. According to the aspect of present invention there is provided a method for stream cipher encryption and/or decryption, said method comprising the steps of: ,

receiving an input comprising a stream of data including at least one bit at a time, and a key generated by said apparatus of claim 1; combining said key with said stream of data comprising at least one bit at a time by combining means; and outputting a corresponding encrypted stream of data comprising at least one bit at a time.

According to the aspect of present invention there is provided a method for block cipher encryption and/or decryption, said method comprising the steps of:

receiving an input comprising a block of data expressed as a block of bits as one input to the apparatus of claim 1; combining said key with said block of data; outputting a corresponding encrypted block of data expressed as a block of bits.

The other objects and advantages of the present invention will be apparent from the description provided hereinbelow with reference to the accompanying figures and description of preferred embodiment.

BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS

Figure 1 illustrates Key stream Generator of Prior art US6587562. Figure 2 illustrates encryption and decryption method using a Block Cipher.

Figure 3 illustrates encryption and decryption method using a Stream Cipher.

Figure 4 illustrates the Core of a Stream Cipher

Figure 5 showing sequential steps involved in operation of a Synchronous Stream Cipher (SSC)

Figure 6 illustrates keystream generation using a SSC of present invention

Figure 7 illustrates method of Encryption and Decryption using Stream Cipher of present invention

Figure 8 illustrates method of Encryption using block Cipher of present invention

Figure 9 illustrates method of Decryption using block Cipher of present invention

Figure 10 illustrates Flow Chart for Block cipher encryption using the present invention

Figure 11 illustrates Flow Chart for Stream Cipher Encryption using the present invention Figure 12 illustrates the Blue tooth Key Stream Generator.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

Synchronous stream ciphers: A general method of encryption and decryption of a plaintext, Pti, is depicted in Fig.3. The synchronous stream cipher comprises a key-stream generator. The generator in its i ^th round generates an output key-stream, ki, in both encryption and decryption. During encryption output ki is XORed with Pt ₁ to generate corresponding ciphertext Cti- During decryption the ciphertext Cti is XORed with ki to get Pti.

As shown in Fig 3 the key-stream generator comprises a core, which is working under a secret key K and a nonce N. The key- stream generator operates repeatedly till the output key- stream is sufficient to encrypt the total plaintext. The core of key-stream generator is shown in Fig.4. The output cycle of a synchronous stream cipher core can be described by the equations

S _t+ i = f (St),

K _t = g(S _t ),

Ctt = h(K _t ,Pt _t )

The core comprises an internal-state S _t (in round t) , output function g, and an update function f. In every round of key- stream generator g computes the output k _t as a function of S _t and f updates St as S _t+ i. In this way all the internal-states and outputs are connected through g and f as shown in Fig 5. The plaintext bits Pt _t are XORed with the corresponding output key-stream bits, k _t , to generate ciphertext bits Ctt. Block encryption: A general method and apparatus for block encryption and decryption is as shown in Fig.2. It depicts the encryption of a plaintext block (pt) into a ciphertext block (ct) using the secret key (K) . The "encryption phase" or "E- phase" comprises a core in encryption mode. The core can be operated in any of the standard modes like electronic-code- book (ECB) , cipher block chaining (CBC) , output feedback (OFB) etc. The core of E-phase takes pt as its input and it outputs the corresponding ct. The E-phase encrypts a block of plaintext in every round and outputs the corresponding ciphertext block. During "decryption phase" or "D-phase" the core will be in decryption mode. The core of D-phase takes ct as its input and it outputs the corresponding pt . The D-phase decrypts a block of ciphertext in every round and outputs the corresponding plaintext block.

Another general method for block encryption is cascaded method. This scheme is almost same as the above scheme, mentioned in Fig.2, except that the E-phase and/or D-phase of cascaded method comprises more than one core, which are cascaded. Now the first core encrypts a plaintext block and the next core and so on till the last core in the cascade will encrypt its output. The output of the last core is the corresponding cipher text block. In general, cores in the cascade use statistically independent keys. The encryption of a plaintext block (Pt) into a cipher text block (Ct) by a cascaded block encryption scheme where, different cores Cl, C2, C3, ... Cn uses statistically independent keys Kl, K2, K3, ... Kn respectively. The Apparatus

The present invention provides a novel synchronous stream cipher and/or block cipher to carryout encryption/decryption processes .

The apparatus comprises, a plurality of cores (Ci where i = 0, 1, 2...), and these cores are arranged in parallel. Each core of the method and apparatus performs their operations under a secret key (K) and a nonce (N) or also known as initialization vector (IV) . Where, N/IV is a preferable optional for block encryption.

Corresponding to each core there will be a "set of numbers (S- Ci where, i = 0, 1, 2...)". The apparatus also comprises a variable called "access-value (av) " which belongs to another "set of numbers" AV. The value of av is initialized as a function of K, N and it get updated for every round of encryption/decryption .

The apparatus involves a "selection process (SP) " which takes av as its one input and all the "set of numbers" associated with cores as other inputs. The apparatus further comprises of a control means which comprises selection functionality SP which selects a core to generate its output in the particular round of encryption/decrytption. All S-Cis and av are the inputs to SP. The selection of different cores by SP, to generate their outputs, is preferably a balanced selection. When there are more than two cores, arranged parallel, and if parallel computation is available, ^' SP can be designed to select two different cores to generate their outputs in parallel.

In addition to cores and SP the method also comprises an output function (OF) . It is key dependent and preferably nonlinear function with or without memory. OF takes the output of the core, which is under operation in the particular round and it generates its output. In case of SSC the output of OF is the output key-stream in the particular round of key- stream generator. OF can be constructed in such a way that it takes parts of outputs from cores, which are under operation in two successive rounds of key-stream generator, to generate the output key-stream. This output from OF is used to XOR with the plaintext to generate ciphertext. In case of block encryption the output of OF is the ciphertext.

Method of Encryption Using Stream or Block Cipher:

The proposed method and apparatus for SSC and/or block encryption, with two cores (which is a minimum number) is shown in Fig. 6.

The apparatus (100) comprises two cores, which are arranged in parallel. The Corel (102) and Core2 (101) are cores under K, N. The set of numbers S-Cl (105) and S-C2 (106) are respectively associated with 102 and 101. The variable av (107) belongs to the set of numbers AV (108). The selection process SP (103) takes 107, 105 and 106 as its inputs and selects a core 102 or 101 to generate its output. The output of the core selected by 103 is the input to OF 104. The output of 104 is the output of 100 in that particular round. This output is XORed with the plaintext to generate corresponding ciphertext when the apparatus is used as SSC, where as in case of block encryption output of 104 is the ciphertext. The value of 107 gets updated, key dependent, for every round of 100. The sets 105, 106, 108, the update of 107 and design of 103 is in such a way that the selection of cores by 103 is preferably equally likely in any round of 100.

The encryption and decryption of a plaintext, Ptj _. , by the apparatus proposed in Fig.6, when it is used as SSC is given in Fig.7. The method and apparatus depicted in Fig.6 can be used as PRNG with output key-stream as the pseudo random number sequence. The encryption and decryption of a plaintext blocks by the apparatus proposed in Fig.6, when it is used for block encryption are shown in Fig.8 and Fig.9 respectively. The apparatus proposed in Fig.6 can also be used to produce MAC in standard modes of operation like CBC-MAC, OMAC (one-key CBC-MAC) etc. In addition, the method and apparatus depicted in Fig.6 can be used as CPF to produce MAC/HMAC of a message.

The flow charts of the encryption processes are provided in Flow diagrams. These diagrams are self-evident. As the method developed mentions, a way of arranging the cores of the cipher and the way of choosing these cores in a particular round of encryption the method supports both hardware and software development as the core and selection process are compatible to the both. These methods are computer implemented using appropriate language like C and/or hardware commonly used in the art. No specific preference is provided as the method works with all commonly the available software and hardware components .

As the method allows the cores to be parallel, if more than one core is chosen in a particular round (in this case the minimum number of cores to be in parallel is three) of encryption the two encryptions can run in parallel because of complete independence of one core from the other. In this way with three cores, performance will double almost.

This method and apparatus for encryption and/or decryption of data using synchronous stream ciphers and/or block ciphers can be used in many industries and in many devices, which includes mobile phones, telephones, faxes, CDs, DVDs, smart-cards, sim- cards, encryption/decryption software for information security, encryption protocols, personal banking, online credit-card transactions, ATM transactions, and e-commerce.

Conventional synchronous stream cipher

The key-stream output generated by the conventional synchronous stream cipher represented as

Ko= g(So)

K ₁ , where i belongs to {0,1,2,3,4,5,6,..} is the key-stream output from the generator in the i ^th round and Si is the internal state of the key-stream generator in that round.

The functions g, f are the output and update functions of the key-stream generator respectively. Cipher text in a particular round is the XOR of plaintext and the key-stream output in the particular round.

This set off equations holds good with probability "1" and these equations clearly shows the unambiguous relations between key-stream outputs, internal states of the generator.

Where as in the method proposed by the present inventors, there exists ambiguity in these relations as explained below.

(i) Let AB is a sample SSC of the proposed model with two cores

A and B arranged in parallel.

(ii) Let the output of SP is C _τ (1 bit) at round T. (iii)Let core A generates output when C _τ is "zero (0)" and B when C _τ is "one (I)". (iv) Let {So ^a , So ^b } are the initial internal states, {g ^a , g ^b } are the output functions and {f ^a , f ^b } are the update functions of core A and core B respectively, v) Now design OF so that it takes a part of output from the previous round and a part form present round. Now the output key-stream at round T can be one of the following The four possibilities combinations of {C _τ -i , C _τ } are Casel: {0, 0} then K _τ = OF(g ^a (S _n ^a ) , g ^a (S _n+1 ³ )) Case2: {0, 1} then K _τ = OF(g ^a (S _n ^a ) , g ^a (S _m ^b ) ) Case3: {1, 0} then K _τ = OF(g ^b (S _m+1 ^b ) , g ^a (S _n- ^ ₁ ³ )) Case4: {1, 1} then K _τ = OF(g ^b (S _m+1 ^b ) , g ^b (S _m ^b ) )

Now K _τ has four valid equations each holds well with a probability of 1/4. In this way ambiguity introduced. Where as in the conventional synchronous stream cipher K _τ have an equation as shown in (1) which holds with probability 1.

This introduces a big difference of success rate of attacks on the cipher as follows in the conventional scheme all the equations of the case, as in (1) , valid with the probability 1 the result gained from solving these equations, by means of finding some weakness, is valid 100% with some attack complexity. Where as, in the case of the cipher proposed each equation valid with success probability only 1/4 (for the above example) so when more equations considered the success probability of the outcome reduces drastically.

In the following flow diagram, the update of internal state of key-stream generator is shown Conventional :

S ₀ "> Si ^■ » S ₂ "> S ₃ -» S ₄ -» S ₅ -» S ₆ -* S ₇ -» S ₈ -> S ₁₀ -> Update from one state other is done by update function g. the sequence is valid with probability 1. Where as the update of internal state in the method proposed for the above example will be as

( S ^ua || S ^υb )

^l S ^/D )

In this way, the path followed by the internal states is highly unpredictable. The introduction of ambiguity is clearly illustrated here.

Alternatively, the encryption method using block cipher (both single-core & multi-core cascade) plaintext and the ciphertext are connected as

Ciphertext = DES (plaintext, key)

Or

Ciphertext = DES-d (DES-c (DES-b (DES-a (plaintext, key-a) , key-b) , key-c) , key-d)

In this way in conventional block ciphers, either single core and multi-core cascaded, no ambiguity exists in the relation between the ciphertext generated and the plaintext fed to the block cipher. Ambiguity in the relation between the ciphertext and plaintext is achieved in the method, by encrypting the plaintext by one of block cipher's cores depending on the output of selection process. If A and B are two cores arranged in parallel in a cipher which is like the method proposed in particular round

Ciphertext = A (plaintext, key-a) or B (plaintext, key-b) In a particular round, each equation is valid with probability 1/2. One of the two equations generates the cipher block in that round. More complicated ways of generating the ciphertext are also possible when we consider OF into account.

A number of experiment are carried out to test the strength of the proposed method and apparatus against the cryptanalysis techniques the following method adopted

1) Select an attacked cipher.

2) Study the attack.

3) Observe the success probability and/or complexity of the attack.

4) Put the cipher core in the proposed method with 2 cores

5) Neglect "OF" for time being. β) Assume the random access of cores.

7) Study the attack on the new algorithm.

8) Find the variation in success probability or complexity of the attack. Example 1 :

Attack on Blue tooth Key Stream Generator

Figure 12 showing the Blue tooth Key Stream Generator. According to this figure the KSG consists of regularly clocked Linear Feedback Shift Registers (LFSR) and four memory bits. With each clock, an output bit Z _t proposed depending on the output a _t , b _t , c _t and dt of the four LFSRs and the four memory bits (Qt, Pt, Qt-i, Pt-i ) • Then, the next memory bits C _t+ i _: = (Qt ₊ i, Pt ₊ i) are calculated and so on. The exact definitions are

Zt = at θb _t θc _t θd _t (D

C _t+I = St ₊ i θ C _t ΦT (C _t _i) (2)

Where T (X ₁ , x ₀ ) := (x ₀ , x _o ®Xi) and

St _+I =(S ¹ ^i, SVi) = I (a _t + b _t + ct + d _t + 2Q _t + Pt) /2 IJ (3) l_

Building a system of nonlinear equations for the key stream generator

Z _t = a _t θb _t θc _t θd _t θ Pt (4)

Q _t+ i =π ₄ (t) θ π ₃ (t) θπ ₂ (t) θπi(t) PtQtθQt θp _t -i (5)

Pt ₊ i =π ₂ (t-) θ πi (t) P _t θ Qt θ Qt-i ΦPt-i © Pt (6)

Here, π _k (t) is the XOR over all possible products in {at, bt, c _t , dt} of degree k. E.g. ,

Ih (t) = a _t θb _t θc _t θd _t

IMt) = a _t bt θ a _t c _t θ a _t d _t θ b _t c _t θ b _t d _t θ c _t d _t If we define the following additional variables A(t) = π ₄ (t) θ π ₃ (t)P _t θP _t -i

Equation (5) and (6) can written to

Qt ₊₁ = A(t) ® B (t) Qt (7)

Pt ₊₁ = B(t) θ 1 θ Pt-iθ P _t ® Q _t θ Q _t -i (8)

By multiplying (7) with B(t) we get another equation

0 = B(t) (A(t) θ Q _t θ Q _{t +1} ) (9)

Equation (8) is equivalent to

Qt © Qt-i = B(t) ® 1 θ Pt-iθ Pt ® P _t+1 (10)

Now we insert (10) into (9) with index t+1 instead of t and get

0 = B(t) (A(t) ® B(t+1) © 1© P _t θ P _{t +1} Θ P _t+2 )

Using (4), we eliminate all memory bits in the equation and get the following equation, which holds for every clock t:

0 = 1 © zt-i θ zt © zt+i © z _t+2

© U ₁ U) (zt z _t+2 © zt zt+i θ z _t zt-i © zt-i © z _t+ i © z _t+2 © D

© π ₂ (t) (l© z _t -i © z _t © zt ₊ i © Zt ₊₂ ) © π ₄ (t) Φ π ₃ (t) z _t Φ rii(t-i) © πi (t-i) rii(t) (l® z _t ) © πi (t-i)π ₂ (t) Θ rii(t+l) z _t+1 ® IT ₁ (t+1) πi(t) z _t+ i (I© z _t ) θ θ π ₂ (t+i) θ π ₂ (t+i) πi (t) (iθ z _t ) ® π ₂ (t+i)π ₂ (t) ® πi(t+2) θ π _x (t+2) πi(t) (l® z _t ) ® πi(t+2)π ₂ (t)

With every clock t we get additional equation, which holds with probability 1. This makes it possible to compile a system of nonlinear equations degree 4. As the unknowns are just the bits of the initial value of the four LFSRs, the secret key can recover by solving the SNE.

The maximum number of possible occurring terms in the SNE is T= 2 ²³ ' ⁰⁷ . The fastest practical method we are aware of solve a SNE is Strassen' s algorithm. It requires about 7. T ^ln7 operations. In this case, secret key can be recovered with approximately 2 ⁶⁷ - ⁵⁸ operations if at least 2 ²³ -° ⁷ linear independent equations are available.

Modefied algorithm:

The attack on a modified algorithm and normal cipher algorithm are compared below. a. Modified Algorithm =

{

If(Xi=O) { a-EO };

If(Xi=I) { EO }; /* attack on a-E0 does not applicable to the others*/

OF ( ) ; /*it does not do any thing in the present case */

} Attack : To implement the same attack on the modified algorithm we can use the same equation

0 = 1 θ zt-i θ z _t θ Zt+i θ Zt ₊₂

® rii(t) (Zt Z _t+2 © Zt Z _t+l θ Z _t Zt-I θ Z _t _ _! ® Zt ₊ I θ z _t+2 θ D

® π _z (t) (1® zt-i ® Zt ® zt+i ® Zt ₊₂ ) © IMt) θ π ₃ (t) z _t

© πi(t-i) © iMt-u U ₁ It) (l© zt) © πi(t-i)π ₂ (t) ® πi(t+i) z _t+1 ® πi(t+i) πi(t) z _t+x (iθ z _t ) ©

® π ₂ (t+i) ® π ₂ (t+i) πi(t) (l® z _t ) © π ₂ (t+i).π ₂ (t) © πi(t+2) θ πi(t+2) πi(t) (i© z _t ) © πi(t+2)π ₂ (t)

Now clearly the "probability of success" of the solution to the above equation depends on the core which generates the outputs z _t -i, Zt ₊ 2. If all the outputs are from core a-EO the above equation is valid. So probability of the first, t=l, valid equation is H * H * H * ^. When the first equation is valid then the probability of the second, t=2, equation to be valid is Η. When first and second equations are valid (with success probability (^) ⁵ ) the probability of a third equation to be valid is H and so on.

So, the probability for getting 2 ²³ ' ⁰⁷ (say k) sequential valid equations is (1/2) ^k+3 . This is nothing but the probability of success of the attack, which sounds meaning less in the present case. Example 2 : Distinguish attack on PY.

Algorithm: Single Round of Py

Input: Y [-3; :;:/ 256], P[O; :;;; 255], a 32-bit variable s Output: 64-bit random output

/*Update and rotate P*/

1: swap (P [0], P [Y [185] &255] ) ;

2: rotate (P) ;

/* Update s*/

3: s+ = Y [P [72]] - Y [P [239]];

4: s = ROTL32{s _f ((P[116] + 18)&31));

/* Output 8 bytes */

5: output ({ROTL32(s; 25) (xor) Y [256]) + Y [P[26]]);

6: output (( s (xor) Y [-1]) + Y [P[208]]);

/* Update and rotate Y */

7: Y [-3] = (ROTL32{s; 14) (xor) Y [-3]) + Y [P[153]]; 8: rotate [Y);

ATTACK:

0\; ϊ (θ) - O ₂ ; ₃ (o) if the following six condi tions on the elements of the S-box P are simul taneously sa tisfied. 1. P ₂ [116] =-18 (mod 32) ('event A) ,

2. P ₃ [116] = 7 (mod 32) (event Bj ,

3. P ₂ [72] = P ₃ [239] + 1 ("event C) ,

4. P ₂ [239] = P ₃ [72] + 1 (event D) ,

5. Pi [26] = 1 (event E) ,

6. P ₃ [208] = 254 (event F).

Bias in the Distribution of the 1st and the 3rd Outputs;

p [A n B n c n o n E n F ] = 2 -41.9

The required number of samples is to distinguish the key- stream from the random is n = 0.4624 M ² n = 0.4624 (2 ⁴² - ⁹ ) ² = 2 ⁸⁴ " ⁷

Modified Algorithm:

Input: Yl, Pl, Y2, P2 and 32-bit variables si, s2. Output: 64-bit random output

Algorithm:

{

If(X=O) (PYl };

If(X=I) {PY }; /*attack on PYl does not applicable to others*/

OF ( ) /*it does not do any thing in the present case

*/

}

Attack on "Modified Algorithm": Qi _{/ K} O) = Oz; 3(o) if the following six conditions on the elements of the S-box Pl are simultaneously satisfied.

1. P ₂ [116] =-18 (mod 32) (event A) ,

2. P ₃ [116] = 7 (mod 32) (event B) ,

3. P ₂ [72] = P ₃ [239] + 1 (event C) ₁ .

4. P ₂ [239] = P ₃ [72] + 1 (event D) ,

5. Pi [26] = 1 (event E) ,

6. P ₃ [208] = 254 (event F).

(Event G) And the additional condition that all the first three outputs are from PYl

Now the probability of all the 7events to occur simultaneously is

P [AnBnCnDnE(IFnG] = 2 ^~41 - ⁹ (1/2) (l/2) (l/2) = 2 ^~44 - ⁹

The required number of samples to distinguish the key-stream from the random

n = 0.4624 M ² n = 0.4624 (2 ⁴⁵ - ⁹ ) ² = 2 ⁹⁰ " ⁷

In the above analysis, we assumed that OF does not do any thing. If OF is considered the attack cannot be implemented. A 8*36 key dependent S-box can be a very good choice here as OF.

From the above it can be clearly observed that the requirement of a very few output keystreams increases complexity of the attack a lot. As the attacks on SSC, in general, requires a very huge amount of output keystream in these cases the method proposed makes the success probability negligible.

Example 3 :

Distinguisher for TPypy and TPy.

Algorithm: Single Round of TPypy and Tpy

Input: Y [-3, 256], P[O, 255], a 32-bit variable s

Output: 64-bit random output

/*Update and rotate P*/

1: swap (P [0] , P [Y [185] &255] )

2: rotate (P) ;

/* Update s*/

3: s+ = Y [P [72]] - Y [P [239]] ;

4: s - ROTL32{s, ((P[116] + 18)&31));

/* Output4 or 8 bytes */

5: output {(ROTL32(s, 25) (xor) Y [256]) + Y [P[26]]);

/* This step 5: is skipped for TPypy */

6: output (( s (xor) Y [-1]) + Y [P[208]]);

/* Update and rotate Y */

7: Y [-3] = {ROTL32{s, 14) (xor) Y [-3]) + Y [P[153]]; 8: rotate (Y); It shows a distinguish attack when a set of 14 conditions, please see the attachment for further details of the attack, are satisfied. The order of the distinguish attack is O(2 ^~281 ) .

Modified Algorithm:

Algorithm:

{

If(X ₁ =O) { TPypyl };

If(X ₁ =I) { TPypy }; /* attack on TPpyl does not applicable to the others*/

OF ( ) ; /*it does not do any thing in the present case */

}

Attack on "Modified Algorithm":

To implement the above attack for the modified algorithm in addition to the 14 conditions mentioned above another condition should fulfilled

15) X ₁ = 0, X ₂ =O, X ₃ =O, X ₉ =O (event L)

P(L)= 2 ^"9

Now P(R ₀ =O) = H (1+ 2 ^"149 - ⁵ )

So, the number of key-stream outputs required to distinguish the output from the random is 0 (262144 * 2 ^k ) .

A Linearization attack on similar application shows that the block ciphers designed by the method resists to shortcut attacks .