THEREFOR

FIELD OF THE INVENTION

The present invention relates to a system and a method for encrypting and decrypting data. BACKGROUND ART

It is a long-familiar fact that all ciphers, including block and stream ciphers, are emulating a one-time pad OTP. However, for provable security, the key bits have to be used only once for each encrypted plaintext bit. Obviously, with present day technology this is not a practical solution. Alternatively, one resorts to computational complexity security. In this case, the key bits are used more than once. Unfortunately, this provides a cipher cryptanalyst with the means to launch feasible statistical attacks.

It is difficult to reprogram these existing ciphers to prevent such attacks. The template for the prior art algorithm is always fixed. It can leave statistical clues to an attacker. Pattern linkage can be easily identified and the sequence of operations can also be easily guessed. This makes it easy for an algorithm designer to predict in advance the operations that may be involved in these ciphers, resulting to such attacks later.

The structure usually adopted in an existing cipher is a partially sequential one. As such, the encryption speeds of these existing ciphers are often slower, i.e. more than 8 cycles per byte.

A method and a system for encrypting data that have improvements that can overcome drawback mentioned above are therefore very much needed.

SUMMARY OF THE INVENTION Accordingly, there are provided a method for encrypting and decrypting data and a system therefor.

According to one aspect of the present invention, the method comprises the steps of: generating a plurality of subkeys from an encryption key by using a pseudo random number generator component; the pseudo random generator comprising an encrypt function and a one-way hash function; and the encrypt function is in cascade with the hash function; and shufflmg _. the _. djta^

According to another aspect of the present invention, the present invention relates to a system for encrypting and decrypting data. The system comprises: a pseudo random number generator component having an encrypt function and a one-way hash function; the encrypt function is in cascade with the hash function; the pseudo random number generator component is for generating a plurality of subkeys from an encryption key; and the data is shuffled for a number of rotations depending on the encryption key.

It is an object of the present invention to provide a method and a system of the present invention that can dynamically change and meta-morph a cipher with different user key. With different user keys, we end up with a different "morph" of the cipher, therefore, it is totally infeasible to launch attacks by varying keys or parts of the key. As such, most known cipher attacks can be avoided. The cipher furnishes concepts of key-dependent pseudo-random sequence of operations that even the cipher designer cannot predict in advance. The cipher is self-modifying, therefore provides an algorithm metamorphism and adequate security.

It is also an object of the present invention to provide an algorithm as a pseudo random sequence of operations. A user key, also known as the encryption key, determines the sequence of operations. The pseudo random selection of operations provides the metamorphic nature of the cipher. As such, it is difficult to launch most known attacks since there are no statistical clues left to the attacker. The algorithm utilized is randomly selected. Even the cipher designer has no clear idea what is the sequence of bitwise operations would be. The pseudo random selection of operations and key-dependent number of rotations provide a barrier against pattern leakage and block replay attacks. The selective operations also allow the cipher to encrypt images with no traces of the original image.

It is also an object of the present invention to provide a pseudo random number generator component that uses the encrypt function as a first stage in a cascade of the encrypt function and the one-way hash function. Because of this, it is unmanageable to launch most known attacks. Particularly, it provides the required security against known key attacks. On the other hand, it easily allows the replacement of the hash function if successfully attacked. It also produces an unexampled key-dependent encryption algorithm. Finally, it provides a negligible probability of guessing the correct form of the algorithm utilized.

It is further an object of the present invention to provide encryption low-level operations that are selected to be bit-balanced. The operations do not provide any bias to the number of zeroes or ones in the output cipher. The result of such an approach is the creation of an immense number of wrong messages that conceal the only correct one.

It is further an object of the present invention to provide a cipher that provides adequate and improved security and throughput with a simple parallelizable structure. If all the operations employed are parallelized, the process conducted in the system can be further simplified and became appreciably faster and more riotously secure. Also, the simplicity of this algorithm readily lends itself to parallelism. Depending on the word or the block size required, this parallelism can be achieved using superscalar multi-threading capabilities or multiple data paths on a specialized hardware such as FPGA with their contemporary vast gate count. The advantage obtained from such a configuration is saving memory and communication bandwidth on the chip and the channel levels. In addition, when four Crypto Logic Units (CLUs) are used in parallel, the average delay can be reduced to almost one cycle per byte.

The present invention consists of certain novel features and a combination of parts hereinafter fully described and illustrated in the accompanying drawings and particularly pointed out in the appended claims; it being understood that various changes in the details may be made without departing from the scope of the invention or sacrificing any of the advantages of the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

For the purpose of facilitating an understanding of the invention, there is illustrated in the accompanying drawings the preferred embodiments from an inspection of which when considered in connection with the following description, the invention, its construction and operation and many of its advantages would be readily understood and appreciated.

FIG. 1 shows the structure of the cipher of the present invention.

FIG. 2 shows the basic crypto logic unit (CLU) of the present invention.

FIG. 3 shows the rotation operation (ROR) implementation using multiplexer of the present invention.

FIG. 4 shows the proposed key format where the location of the selection bits is shown.

FIG. 5 shows the proposed parallel configuration of the cipher of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The present invention relates to a method and a system (500) for encrypting data. Hereinafter, the method and the system (500) shall be described according to the preferred embodiments of the present invention and by referring to the accompanying description and drawings. However, it is to be understood that limiting the description to the preferred embodiments of the invention and to the drawings is merely to facilitate discussion of the present invention and it is envisioned that those skilled in the art may devise various modifications without departing from the scope of the appended claim.

The method and the system (500) according to the present invention are as represented in the drawings.

Introduction

The Stone Cipher- 192 (500) is a metamorphic cipher that utilizes a variable word size and variable-size user's key. In the preprocessing stage, the user key is extended into a larger table (not shown) or bit-level S-box using a specially developed one-way function (30). However for added security, the user key (40) is first encrypted using the cipher encryption function (20) with agreed-upon initial values. The generated table is used in a special configuration to considerably increase the substitution addressing space. Accordingly, the table is called the S- orb. Four bit-balanced low level operations are pseudo-randomly selected to generate the sequence of operations constituting the cipher (500). These operations are: XOR, INV, ROR, NOP for bitwise xor, invert, rotate right and no operation respectively. The resulting key stream is used to generate the bits required to select these operations, as will be hereinafter described further.

The cipher (500) furnishes concepts of key-dependent pseudo random sequence of operations that even the cipher designer cannot predict in advance. In this approach, the sub-keys (50) act as program instructions not merely as a data source.

Moreover, the parameters used to generate the different S-orb words (50) are likewise key- dependent. The self-modifying proposed cipher (500), based on the aforementioned key- dependencies, provides an algorithm metamorphism and adequate security with a simple parallelizable structure.

The estimated cipher maximum and average processing delays are 6 and 4.3 cycles per byte respectively. The ideas incorporated in the development of this cipher (500) pave the way for key-driven encryption rather than merely using the key for sub-key generation. The cipher (500) is adaptable to both hardware and software implementations.

Potential applications include voice and image encryption.

The present invention relates to a metamorphic encryption and decryption method and a system therefor.

An encryption method is utilized to encrypt variable-size blocks of data X to Y based on encryption user key K _u (40), and four low level bit-balanced operations (XOR, INV, ROTR, NOP) consisting of the following steps: a. Generating subkey table from K _u (40) using a pseudo random number generator PRG (10) consisting of the encryption function (also known as encrypt function) (20) cascaded with a one way hash function (30). b. Shuffle the data bitwise for a variable number of rounds depending on the key (20). However, the minimum number of rounds is taken equal to 8. A Crypto Logic Unit (CLU) (120) is built, as shown in FIG. 2, using one OR gate (60), four AND gates (70), five INVERTERS (80), one XOR gate (90), and a rotation unit ROR (110).

The Rotation unit ROR (Rotation right operation) (1 10) is built using two (source and destination) n-bit registers and a number of multiplexers (130) equal to n depending on the word size utilized. This unit is shown in FIG. 3. The encryption key _u is used to determine the following: c. The number of rounds (Taken at least 8 rounds) d. The order of the low level enciphering operations. e. To create a bit-balanced cipher (500) that is hardly statistically distinguishable from communication white noise. The cipher (500) includes flexible design; accepts keys and data blocks of different lengths and provide variable size S-orb depending on changing security requirements. This, in turn, facilitates the digital circuit design.

The key setup time is kept to a minimum using a specially designed hash function (30).

The cipher (500) uses simple construction and simple round function with minimum internal looping.

The pseudo random selection of operations provides the metamorphic nature of the cipher (500). This, in turn, hides most statistical traces that can be utilized to launch these attacks.

Different keys will produce completely different forms (meta-forms) of the cipher (500). Even the cipher designer cannot predict in advance what these forms are.

SC-192 Building Blocks

A metamorphic reaction takes place in a rock when various minerals go from amphibolites facies to some color schist facies. Some of the minerals such as quartz may not take place in this reaction. The process in its essence follows certain rules; however the end result provides a pseudo random distribution of the minerals in the rock or stone. The metamorphic natural process results in thousands or even millions of different shapes of the rock or stone. Based on this, a new metamorphic cipher has been conceived and implemented, and named as "Stone Cipher- 192". The internal sub-keys (50) are generated using a combination of the encryption function (20) itself and a 192-bit specially-designed one-way function (30). The idea of this cipher (500) is to use four low level operations that are all bit-balanced to encrypt the plaintext bit stream based on the expanded stream of the user key (40). The key stream is used to select the operation; thus providing a random however recoverable sequence of such operations.

A bit-balanced operation provides an output that has almost the same number of ones and zeroes. These operations are XOR, INV, ROR and NOP. Respectively, these are, xoring a key bit with a plaintext bit, inverting a plaintext bit, exchanging one plaintext bit with another one in a given plaintext word using a rotation right operation and producing the plaintext bit without any change. In fact, these four operations are the only bit-balanced logic operations.

The conceptual block diagram of the proposed cipher (500) is shown in FIG. 1. It is constructed of two basic functions; the encryption function (20) and the sub-key generation one-way hash function (30). The pseudo random number generator (10) is built using the same encryption function (20) and the one-way hash function (30) in cascade. Two large numbers (a, b) are used to iteratively generate the sub-keys (50). The user key (40) is first encrypted then the encrypted key is used to generate the sub-keys (50).

In the next few sections, the design rationale, the structure of the cipher, the one-way function (30) employed to generate the sub-keys (50), the software and hardware implementations of the cipher (500), a comparison with a polymorphic cipher and a discussion of its security against known and some probable cryptanalysis attacks are hereinafter discussed.

Initialization

The sub-key (50) generation of this cipher (500) is performed before enciphering begins using the following recursive equation: hi= h (a . h _i- i + b) Where h, is the hash function (30) of the S-orb word (i) (50). The total number of words of the S-orb (m) varies depending on the available memory and degree of security required. This value is taken equal to 6 resulting in an S-orb of six 192-bit words. The process is initialized with ho = h (k), where k is the user key (40), and a and b are two large secret integer numbers. These two numbers can be also obtained from the user key (40). The initial vector of the hash function (IV) (30) is not necessarily to be kept secret. An assigned field is used in the round keys (50) or S-orb words (50) to determine the location of the center of what is called the "x- blocks" (not shown). The contents of each block are used to perform the required substitution additions. The next step is to divide the plain text 192-bit block into six 32-bit words, 12 16- bit words or 24 eight-bit words. The same procedure is applied to different round keys (50). Now, the selective XOR operation can be performed, as shown in detail in the block diagram, in order to realize the required homophonic substitution. The next step is to perform a number of rotations to the partially ciphered words (not shown) where this number is determined by a five-bit secret field of the round key (50). Finally, to perform the poly-alphabetic substitutions, the xor operation is used between the resulting partially ciphered word and the round key (50). The operation is repeated an additional number of rounds depending on the value obtained from the original user key (40).

The combination of the encryption function (20) and the one-way hash function (30) is used to generate the sub-keys (50). The cipher designer has to select which one should precede the other. Based on previous works where it was proven that a cascade of two ciphers (20 & 30) is as strong as its first cipher. Therefore, the encryption function (20) is started first. The oneway hash function (30) is then used recursively to generate the sub-keys (50) based on two large numbers that are derived from the user key (40). In this case, the encryption function (20) requires some initial agreed-upon vector value (IV) to complete the encryption process.

This IV can be regarded as a long-term key or even a group-key that can be changed on a regular basis or when a member leaves the group. The combination of the encryption function (20) and the one-way function (30) are used as the required pseudo random number generator PRG (10). It is worth pointing out that the design of the cipher (500) intentionally allows the change of the one-way hash (30) if successfully attacked.

The Structure of the Cipher

The encryption function (20) or the cipher engine is built using four low-level operations, as shown in FIG. 1. These are XOR, INV, ROR and NOP operations. Table 1 demonstrates the details of each one of these operations.

Table 1: The basic cipher engine (encryption function) operations

The basic crypto logic unit (CLU) (120) is shown in FIG. 2. All operations are at the bit level. The encryption process in the unit (120) is to be repeated a number of times depending on the required word or block size. The rotation operation, referred to by the circular arrow, is performed using multiplexers (130) as shown in FIG. 3. In the software version these multiplexers (130) are replaced by "case" or "switch" statement. This CLU (120) is used as the encryptor or the decryptor. If the output cipher bit is changed to an input plain text bit, the new output will be the same as the old plain text bit. Obviously, this is a feature of the applied functions namely XOR, INV or NOP. The only exception is in the case of ROR, the decryptor will use ROL (rotation to left operation). 10 000271

- 11 -

As shown in FIG. 4, the operation selection bits (Si S ₀ ) can be chosen from any two sub-key (50) consecutive bits. The same applies for the rotation selection bits (S' i S' ₀ ).

The Algorithm In the next Table 2, a formal description of the algorithm round structure is provided.

Table 1: The algorithm round structure

The round structure

1. Read user key; ^" - ^■ · ^'· . ^■ ■ ^' ■■[ ,

2. Encrypt user key by calling encrypt function and using the initial agreed-upon

As seen from the above formal description of the algorithm (Table 2), it simply consists of a series of pseudo random calls of the encryption function. However, each call will trigger a different bitwise operation.

The simplicity of this algorithm readily lends itself to parallelism. This parallelism can be achieved using superscalar multi-threading capabilities or multiple data paths on a specialized hardware such as FPGA with their contemporary vast gate count.

Software Implementation

The pseudo C-function [19] that represents such a table is given by:

encrypt (plain-text-bit, key-bit, selection-bitO, selection-bit 1 , rot-bit)

{ al= plain-text-bit ^A key-bit; el = al & (~selection-bitO) & (-selection-bit 1); bl= ~ plain-text-bit; fl= bl & (selection-bitO) & (-selection-bit 1); gl= rot-bit & (-selection-bitO) & (selection-bit 1); hl = plain-text-bit & (selection-bitO) & (selection-bit 1); cipher-bit = el |fl|gl|hl ; return (cipher-bit); Hardware Implementation The hardware version of the CLU (120), previously shown in FIG. 2, is FPGA-implemented. The average delay per byte was found to be 4.33 cycles per byte. Straightaway, if four CLUs (120) are used in-parallel, this delay will be approximately equal to one cycle per byte. This proposed parallel configuration is shown in FIG. 5. As an example, a representative code of the Verilog file used to FPGA-implement the CLU (120) is given by:

module metamorph (pl,kl,s0,sl,p2,cl);

input pi, kl,s0,sl,p2;

output cl ;

xor(al,pl,kl);

and(el,al,~s0,~sl);

assign bl= ~pl;

and(fl,bl,s0,~sl);

and(gl,p2,~s0,sl);

and(hl,pl,s0,sl);

or(cl,el,fl,gl,hl);

endmodule

Security Analysis

One claims that differential cryptanalysis, linear cryptanalysis, Interpolation attack, partial key guessing attacks, and side-channel attacks, barely apply in this metamorphic cipher (500). The pseudo random selection of operations provides the metamorphic nature of the cipher (500). This, in turn, hides most statistical traces that can be utilized to launch these attacks. Each key (40) has its own unique "weaknesses" that will affect the new form of the algorithm utilized. Thus, different keys (40) will produce completely different forms (meta-forms) of the cipher (500). Even the cipher designer cannot predict in advance what these forms are. It can be easily shown that the probability of guessing the correct sequence of operations is of l

the order of 2 ^{3 iV} , where w is the word size and N is the number of rounds. That is for, say, a

1

word size of 8 bits, the probability of guessing this word only is 2 ^1βΛ ' . For a block size of 64

1

bits, this probability is 2 ^{12s V} . Consequently, statistical analysis is not adequate to link the plain text to the cipher text. With different user keys (40), it is ended up with a different "morph" of the cipher (500); therefore, it is totally infeasible to launch attacks by varying keys (40) or parts of the key (40). The only option left to the cryptanalyst is to attack the key (40) itself. To thwart this type of attacks, the encryption function (40) have been used as a first stage in a cascade of the encryption function (20) and the one-way function (30). Regarding the key collision probability, it was shown in section 4 that the key collision probability is negligible when a 192-bit hash is applied. Moreover, the cryptanalyst has a negligible probability of guessing the correct form of the algorithm utilized. As was previously discussed, the simple, structure of the proposed cipher (500) provides a foundation for efficient software and hardware-based implementation. Depending on the word or the block size required, it is relatively easy to parallelize the data path either using multithreading on a superscalar processor or by cloning this path on the FPGA material. Undeniably, using the same encryption process and sub-keys (50) for each block is a disadvantage from a security point of view. Still, this is exactly the same issue with block ciphers (500) in general. The advantage obtained from such a configuration, similarly to block ciphers (500), is saving memory and communication bandwidth on the chip and the channel levels. The pseudo random selection of operations and the key-dependent number of rotations provide a barrier against pattern leakage and block replay attacks. These attacks are quite frequent in multi-media applications. Using ECB mode, when encrypting images with conventional ciphers, a great deal of the structure of the original image is preserved. This contributes to the problem of block replay. However, the selective operations allow the cipher (500) to encrypt images with no traces of the original image. This is a major advantage of the Stone Metamorphic Cipher bit-level operations when applied to multimedia files.

A metamorphic cipher (500) that is altogether key-dependent. The four bit-balanced operations are pseudo-randomly selected. Known statistical attacks are barely applicable to crypt-analyze this type of ciphers (500). The proposed simple structure, based on the crypto logic unit CLU (120), can be easily parallelized using multi-threading superscalar processors or FPGA-based hardware implementations. This presented CLU (120) can be viewed as a nonlinearity-associated filtering of the data and key streams. The PRG (10), constructed from a cascade of the encryption function (20) and the one-way hash function (30), provides the required security against known key attacks. On the other hand, it easily allows the replacement of the hash function (30) if successfully attacked. The cipher (500) is well- adapted for use in multi-media applications. This approach will pave the way for key-driven encryption rather than simply using the key for sub-key generation.

While in the foregoing specification this invention has been described in relation to certain preferred embodiments thereof and many details have been set forth for purpose of illustration, it will be apparent to those skilled in the art that the invention is susceptible to additional embodiments and that certain of the details described herein can be varied considerably without departing from the basic principles of the invention.