WO2003065629A2

WO2003065629A2 - Super des

Info

Publication number: WO2003065629A2
Application number: PCT/IL2002/000086
Authority: WO
Inventors: Shalom Bronner
Original assignee: Razel & Shalom Encryptions Ltd
Current assignee: Razel & Shalom Encryptions Ltd
Priority date: 2002-01-30
Filing date: 2002-01-30
Publication date: 2003-08-07
Anticipated expiration: 2004-07-30

Abstract

Super DES is a method for data encryption, derived from the DES encryption standard, further including the use of randomized round-keys. An alternative embodiment of the method for encrypting data comprises having at least two exclusive-or operations in at least some rounds of the encryption process.

Description

SUPER DES

Field of the Invention:

The present invention relates to data encryption. More specifically, the present invention is related to a method for encrypting data, based upon the Data Encryption Standard (hereinafter "DES") algorithm.

Background of the Invention

The DES algorithm is one of the most widely used encryption algorithm in the world today. The DES algorithm is a bit level encryption method, which means that the DES algorithm encrypts 64 bits of plaintext at a time. In order to encrypt each 64 bits of plaintext, DES uses a private key, which is also 64 bits long. The DES encryption method may be referred to as a block cipher, meaning it operates on plaintext of a given size, and returns cipher text blocks of the same size.

The standard DES encryption algorithm accepts an input key of 64 bits from the user, which may also be referred to as a private key. An algorithm referred to as the DES key schedule generates a 48 bit long round key for each round of the DES encryption algorithm. These round keys are derived from 56 bits of the said input key, ignoring every 8^th bit, using permutations and other logical calculations. Since all keys are generated in the same manner, and in accordance with the same permutations and logical calculations, it is possible for an attacker, given knowledge of one round key, to derive other round keys.

An alternative method of implementing the DES algorithm is by using bit-slicing.

The sole purpose of using this implementation is to expedite the encryption process. A key-matrix is created for each round, by repeating the round key 32 times. The encryption algorithm encrypts 64 integers of text at a time, and not 64 bits, as in regular

DES without bit-slicing. DES is susceptible to a number of attacks. Most noticeable among these attacks and one which becomes easier and more practical to perform as technology advances and computers get stronger is the brute force attack. This attack involves going through every possible combination of 56 bits, which is 256 combinations, until the proper key is found. Only 56 bits are actually used in the encryption process, since every 8^th bit of the key is ignored. Most recently, a computer belonging to the Electronic Frontier Foundation cracked DES in a day, using the brute force attack. The bit-slicing implementation does not influence the effectiveness of the brute force attack. This is because all the rows in the key-matrix are identical, and the key is essentially only 56 bits long, like in the regular DES implementation without bit-slicing. Other attacks that may be performed successfully upon DES encrypted ciphertext are the linear analysis attack, the improved Davies attack and the differential attack.

Summary and Objects of the Invention

Thus, it is an object of the present invention, to present an encryption method, which is less susceptible to brute force attack and the other attacks mentioned hereinabove.

It is yet another object of the present invention to make it impossible to deduce key-integers based on the knowledge of any of the other key-integers.

These objects, and others, not specified hereinabove are achieved by an exemplary embodiment of the present invention, which is an encryption method, based on the DES encryption method, which uses randomized round keys and a possible second XOR in certain stages of the cipher algorithm.

Brief Description of the Drawings

FIG. 1 is a flow diagram, presenting an overview of the present invention;

FIG. 2 is a flow diagram representing an exemplary method for the generation of a dynamically created randomizing table; FIG. 3 is a flow diagram describing the proposed method of the randomized key table generation;

FIG. 4 is a flow diagram detailing a couple of initial calculations to be performed prior to the generation of the randomized key table;

FIG. 5 is a flow diagram detailing the process of calculating each individual key integer. During generation of the randomized key table, this process is repeated in a loop, running once for each integer in the key table;

FIG. 6 is a flow diagram illustrating the bit-slice implementation of the present invention for deriving Round function C, wherein S1-S8 represents the bit-slice functions ;

FIG. 7 is a flow diagram illustrating the input integers to and the output integers from the prior art bit-slice function, wherein I are input integers, and S is the bit-slice function; and

FIG. 8 is a flow diagram illustrating the creation or generation of an integer to be sent as input to the bit-slice function in accordance with an exemplary embodiment of the present invention.

Detailed Description of Exemplary Embodiments

In the following detailed description the following terms shall be understood as having the definitions specified, wherein:

Key Array - a storage array that contains the private key integers, the secondary keys integers, where applicable, and the round keys integers.

Private Key - from four to ninety six key-integers forming a private key, that is input by a user into the key generation algorithm; Round Key - an example of an encryption key used to XOR with the plaintext, which in an exemplary embodiment comprises forty-eight key-integers generated using the key generation algorithm for a specific round;

Secondary Key - another example of an encryption key used to XOR with the

Result (defined hereinbelow), which in an exemplary embodiment comprises 48 key- integers selected from an array of 295 key-integers generated using the key generation algorithm for use in the second XOR;

Key-Integer - one of the integers comprising a key;

Ciphertext - a block of data that has been encrypted.

Plain Text - a block of data to be encrypted.

X - the number of key integers consisting the private key.

R - the number of times the round function C is performed

Described herein is an encryption method derived from the DES encryption method using bit-slicing. The encryption method described uses an integer-based algorithm, which means that blocks of 64 integers are being encrypted at a time. It should be noted that an integer is usually 32 or 64 bits long.

The encryption method of the present invention defers from the regular DES encryption method in two key respects. The first difference between the regular DES and the present invention relates to the method in which the round keys are generated. The present invention uses a randomized round key generation method, which makes it impossible for an attacker to derive any round key-integer based on any other round key-integers. Amongst other advantages, this randomized method affects the effectiveness of the brute force attack on the algorithm of the present invention since in order to decipher the algorithm of the present invention said attacker would have to seperately figure out each of the round keys, as opposed to algorithms in accordance with the prior art, where it would suffice just to discover one of the round keys, and the other round keys could be deduced therefrom. At this stage it would suffice just to say that generally speaking, any randomizing algorithm used to create randomized key- integers that complies with the following requirement can be used by the algorithm of the present invention. The first requirement is that the integers comprising the key array must always be able to satisfy tests of randomness. The second requirement is that possession of one or some of the key-integers should not aid an attacker in deriving any of the other key-integers.

The second difference between the regular DES and the present invention is the use of a second XOR in certain rounds in the present invention. This means that in said certain rounds, the expanded plain text is XORed twice, once using a round key and then a second time using a secondary key. It should already be noted that strategic placement of the second XOR in certain rounds allows for a reduction of the amount of rounds the present invention's cipher algorithm must run while maintaining it's integrity. It should be noted that in accordance with the exemplary embodiment described herein, using a second XOR is not mandatory, but optionally.

Hence is a description of an exemplary embodiment of the present invention. The exemplary embodiment assumes at least 6 rounds of encryption, though at least 10 rounds is preferred and in such a case 10 round keys are generated. The exemplary embodiment also demonstrates the use of a second XOR, which requires the further generation of an additional 295 secondary keys integers, out of which the secondary keys is derived.

With reference to Fig. 1 , when encrypting data by means of the present invention, a 64 integers block of plain text will undergo an initial permutation, and then be divided into two halves, the left half consisting of the first 32 integers of said block, and the second half, consisting of the last 32 integers of said block. These operations constitute as prior art, and therefore should be known to someone of ordinary skill in the art. These halves are then put into the round function along with the round keys and the secondary keys (if a second XOR is used) comprising the key array. Hence is a description of the creation of the key array, i.e. the generation of the integers consisting the round keys and the secondary keys.

The key array is generated based on the input into the key array generation algorithm B of a private key having from 4 to 96 integers and of a randomizing table consisting of 256 integers.

As above mentioned, the private key is a predetermined, fixed, array of from 4 to

96 integers, known only to the user encrypting the plain text and to the recipient of the cipher text which needs to decipher it, whereas the randomizing table is re-created every time an encryption process is initiated. The method in which the randomizing table is generated depends on whether a second XOR is used or not.

If there is a second XOR, the values of the randomizing table (hereinafter "RAND") are initialized as the integer representation of the sin(x) function for x = 1 to 256 respectively. Thus, RAND is an array consisting of 256 integers.

If the Second XOR is not being used, RAND must be created using the algorithm described in Fig. 2, also resulting in an array of 256 integers, so that each encryption uses a different set of round keys.

With reference to Fig. 2, hence is a description of the randomizing table generation algorithm A in accordance with an exemplary embodiment of the present invention.

We initiate the [0] slot and the [1] slot of the randomizing array to equal to two randomly selected integers, respectively, and therefore we know RAND[0] and RAND[1].

n is a generic counter, indicating the slot in RAND that needs to be determined next. Since we already know RAND[0] and RAND[1], n is initialized to equal to 2.

Once RAND[0] and RAND[1] are initiated, the following loop is performed: For n = 2 to 255 {

RAND [n] = RAND [n-1] + RAND [n-2] If RAND [n] < RAND [n-1] Then RAND [n] = RAND [n] + 1

}

The result of the randomizing table generation algorithm A is an array of 256 integers representing the randomizing table, in which every integer equals the sum of the two previous integers, except in certain cases in which the integer is the sum of the two previous integers plus one. Hence is an explanation of the reason for this divergence from the general rule.

If both integers are even, then all the subsequent numbers will also be even, therefore at least one of the lowest end bits will always be zero, causing the resulting ciphertext to be more susceptible to attacks. Therefore, pursuant to the "if statement, the algorithm A adds one to certain integers in the table to ensure that not all the subsequent numbers will be even, regardless of whether the first two numbers or any two adjacent numbers are even. The condition of the "if statement that "an integer is incremented by one only if it is smaller than the preceding integer" is fulfilled at a probability of approximately ^ΛA. The sum of two numbers can be lower than one of the numbers in the case of an overflow. The probability of receiving a carry is (2ⁿ - 1) / 2^{(π +}

¹⁾, where n = 0 to 31. For n = 1, the probability is %. For higher n, the probability converges to ^ΛA. With the inclusion of the condition, the probability of receiving a carry is for all n. The inclusion of the "if" statement thereby achieves the objective of assuring that not all the numbers are even, while doing so at a non-predefined rate.

The next stage after generating RAND is generating the key array. This is achieved by the insertion as input of the private key and of RAND into the key array generation algorithm B described in Fig. 3. The key array is actually an array of key integers forming the private key, the round keys, and if a second XOR is used, also the key integers forming the secondary keys. The general structure of a key array would be as follows - the first X slots will be filled with the X key integers consisting the private key. If a second XOR is used, then the following 295 slots will be filled with 295 key integers consisting the secondary keys, and finally, the following R^*48 slots will be filled with R*48 key integers consisting the round keys.

With reference to Fig. 3 and 4, the first stage of the key array generation algorithm

B is performing initial calculations B1 , which will give us the values of A, F and T.

With reference to Fig. 4, hence is the algorithm which determines the value of A and F.

For i=0 to X-1

F = F + (Key[i] modulo 255.)

Once the above loop is terminated we perform - F = 1 + (F mod 255)

Finally, we initiate A to equal to F, and therefore we know A and F.

With further reference to Fig. 4, hence is the algorithm which determines the value of T.

Set T as the length of the key array.

Set R as the number of times the round function C is called for.

As shown in Fig. 4, if there is no second XOR, then T will equal the number of key integers consisting the private key plus 48*R, representing the round keys. If a second XOR is invoked, the number 295 is added to the above sum, an addition which represents the slots holding the key integers of the secondary keys.

Once the abovementioned initial calculations are over, we know A, F and T, and of course the integers consisting the private key, hence referred to in Fig. 2 as key[X]. The next step is taking the abovementioned values and the randomizing table and inserting them as input into the key integer calculation algorithm B2, the outcome of which is the key array.

With reference to Fig. 5, as above mentioned, the values in the first slots of the key array actually equal the key integers consisiting the private key. Therefore, the first X slots' values equal the X integers forming the private key respectively. Therefore we start filling the key array slots with integers only from the X^th slot (slots 0....X-1 of the key array are filled with the key integers of the private key).

Hence is the calculation of the rest of the Vlues of the key array, as shown in Fig.

n = X For n to T-1

KeyArray [n] = KeyArray [n-X] XOR RANDfA]

B = (A + 1 + (KeyArray [n] modulo 255)) modulo 256

RANDfA] = RANDfA] XOR RANDfB]

KeyArrayfn] = KeyArrayfn] XOR RAND [B] A = (B+F) modulo 256

RANDfB] = RANDfB] XOR RANDfA].

It should be noted that each time a key-integer is generated by the key integer calculation algorithm B2, two values in RAND are altered, resulting in an altered randomizing table unique for use in subsequent generation of each successive key integer, i.e. each key-integer is formed using a different randomizing table than the one used for any of the other key-integers. This makes it impossible to derive a key integer, even where all the other key integers (except private key) are known, because the values of RAND are unknown since they are constantly changing and therefore unique for each key integer generated.

Once the abovementioned loop is finished i.e. once the entire key array has been constructed, the last X calculated values of key array are copied to the first X slots of key array, over-writing the integers consisting the private key. The reason is that in the calculation of the first keys, the randomizing table had not yet been sufficiently scrambled.

In the following stage of the key array generation algorithm B, the algorithm is then re-run 96 times (96 integers is the size of the first two round keys). If a second XOR is also used, then, as above mentioned, the key array generation algorithm B will generate an extra 295 key integers for use in the key array. The first 295 keys are referred to as secondary keys since they are designated for use in the second XOR operation. In such a case, the algorithm should be repeated 391 times instead of 96 times.

With reference to Fig. 3, what will happen is that T will be re-initiated to equal n+295+96 if a second XOR is used, and X+96 if a second XOR is not used, n will be reinitiated to equal to X, and the key integer calculation algorithm B2 will be repeated from n to T-1.

With reference to Fig. 6, as mentioned hereinabove, although not mandatory, the present invention can employ a second XOR in the cipher algorithm.

In an exemplary embodiment of the present invention, the cipher algorithm will run for ten rounds, using a second XOR in rounds two, three, eight and nine. As mentioned above, when using a version of the present invention that involves a second XOR, an extra two hundred and ninety five integers should be added to the key array, in the slots preceding the slots of the key integers consisting the round keys. These integers consist the secondary keys with which the result of the performance of the preceding steps of the encryption process upon the plaintext (hereinafter the "Result") is to be XORed in the second XOR stage. With reference to Fig. 8, to choose a key for the second XOR, a subscript into the key table is calculated as the Result modulo two hundred and ninety five. Other numbers may be used with which to modulo the Result to calculate a subscript into the secondary key table. These alternatives will be elaborated upon below. The Result is then XORed with the key chosen by the subscript. It is suggested that embodiments of the present invention which incorporate a second XOR in the encryption process include a second round function with which to XOR all forty-eight integers of the Result, as the size of each text block is forty-eight integers. Since the inclusion of a second XOR causes a round to be slower, it is further suggested that the second XOR be used in as few rounds as possible, while maintaining its effect. The purpose of including a second XOR in certain rounds is to foil differential attacks. Decisions regarding strategic placement of the Second XOR should take this objective into consideration. As a rule, it is suggested that the second XOR be placed in rounds two, three, the next-to-last round and the round before the next-to-last round. Obviously, as the number of rounds rises, the complexity of the algorithm rises as well, and the encryption process gets slower.

In an alternative embodiment of the present invention, it is shown that if the compiler of the computer running the present invention's algorithm can handle unsigned sixty-four bit integers, the present invention may use sixty-four bit integers pursuant to the following changes. It should be noted that larger bit-size integers may also be used, in accordance with the computer's capabilities. In case of a larger integer representation in terms of bit-size, the following description should be adapted proportionately. First, all sizes related to the encryption process must likewise be doubled. In this embodiment, blocks of text should be composed of five hundred and twelve bytes. Similarly, the keys and the randomizing agent should contain eight byte integers.

Additionally, difficulties may arise in computing a randomizing table based on a sin(x) table to a precision of sixty-four bits. Therefore, a dynamically created randomizing table, such as the table suggested above and illustrated in Fig. 2, is better suited to be used in conjunction with the sixty-four bit integer implementation of the present invention.

Finally, it was suggested above that 295 integers be used as the keys with which to second XOR the Result. The reason why the number 295 is used will be explained further below. However, when using 64 bit integers, the minimum recommended number of secondary key-integers grows to 1 ,005. The increased storage requirements of 1 ,005 64 bit integers over two hundred ninety five 32 bit integers, make it advisable to use these integers as the round keys as well.

A proposed algorithm for the computation of optimal numbers by which the Result is modulo to calculate a subscript into the secondary key table follows. This algorithm may be used with any embodiment of the present invention, in terms of the bit size of the key-integers.

W = the bit-size of the key-integers. M = the optimal number by which the Result is modulo to calculate a subscript into the secondary key table. A and B are integers. If:

0 < A < B < 2^ΛW And:

A modulo M = B modulo M Necessitate that:

A XOR B = C and C = integer containing at least four 1s. Then: M = an optimal modulo to be used to calculate a subscript into the secondary key table.

The minimum number M that fulfills the requirement of the optimal modulo test is

295 for 32 bit key-integers. Another optimal modulo for embodiments of the present invention using 32 bit key-integers is 319. As the modulo number grows, so does the number of secondary key-integers, and a larger space is required to store them.

Therefore, it is suggested that the minimum optimal modulo number be used.

The above is considered optimal, because it forces a differential attack to get 4 rows correct simultaneously. Thus , if P was the number of plain-text required to attack 10-round Super-DES w/o the Second XOR, then P⁴ will be the amount of plain-text required to attack 10-round Super-DES with the Second XOR. It is also possible to use the number 255 as the modulo number for calculating a subscript into the secondary key table of the embodiment of the present invention using thirty-two bit key-integers. Although this number is not one of the optimal modulo numbers, it is mentioned as a suggested number because computers perform modulo 255 very efficiently. However, the amount of plain-text required to attack 10-round Super-DES with the Second XOR drops to P².

In Super-DES without the Second XOR embodiment, the two integers RANDfO] and RANDfl] are placed in the beginning of the cipher-text, for each file of data encrypted by means of the present invention. RANDfO] and RANDfl] together with the private key were used in order to generate the randomizing table. The recipient also knows the private key, and once he receives the encrypted message he uses the two attached unencrypted integers together with his private key, and generates the randomizing table. From this stage he repeats the abovementioned steps in order to generate the round key, and the secondary keys, where applicable, and once in possession of all round keys he uses them in a reverse order and therefore deciphers the encrypted message.

In conclusion, with respect to possible attacks on the present invention, there are at least four known attack methods for breaking DES. Of these four attacks, namely brute force, linear analysis, correlation and differential, only the latter attack will work against text encrypted using the present invention. However, even using the differential attack, it is harder and impractical, given time constraints, to break ciphertext encrypted by the present invention, as opposed to ciphertext encrypted by the known DES algorithms.

The first known method for attacking DES encrypted text is the brute force attack.

This attack inserts every possible key into the algorithm to break the cipher-text. The regular DES algorithm uses 56 of the 64 bits in the key to generate round keys. The complexity of trying every possible combination of 56 bits is 2⁵⁶. This is within the range of the possible for today's strongest computers. This attack method cannot practicably be used against the present invention. There are at least 10 unique round keys of 48 integers each, each integer consists of 32 independent bits. There are 480 bits of key per bit position in the 10 rounds. The amount of time it would take for the fastest computers to try all possible combinations of 480 bits (a complexity of 2⁴⁸⁰), renders the brute force attack impractical, and therefore useless, against ciphertext encrypted by the present invention. If the Second XOR embodiment is used, then even that method does not work, because the Second XOR makes all the bit-positions interdependent.

A second known method for attacking DES is the linear analysis attack. It uncovers 6 bits in the first rounds, 6 bits in the last rounds, plus 2 implied bits. The remaining bits are uncovered by brute force. It is not effective against text encrypted by the present invention's cipher algorithm.

A third known method for attacking DES is the Improved Davies Attack. When used against the present invention, this attack will have to find all the bits of the last two round-keys, rendering it slower than the fourth attack, the differential attack.

Furthermore, this attack is completely useless against ciphertext encrypted using the present invention in its second XOR embodiment.

This leads us to a fourth known method for attacking DES, the differential attack.

This attack requires 2⁶¹ steps and 2⁵⁹ pairs of data to break sixteen-round DES with randomized round-keys, according to Section 8.2 of Differential Cryptanalysis of DES- like Crvpto-svstems by Eli Biham and Adi Shamir. There is a more efficient method of this attack that does not work against data encrypted by an algorithm using randomized sub-keys. It can be deduced from the teachings of Biham that the 10 round version of Super-DES without the Second XOR, would require 2³⁴ pairs of data for an attack. A pair consists of two plain texts. In DES, each text contains eight bytes. In the 32 bit version of the present invention each text contains 256 bytes. A pair therefore consists of 512 bytes. Thus, the data requirements to break the 10 round version of the present invention is 2⁴³ bytes (8 terabytes). The is per encryption, because each encryption uses a different set of round keys. Therefore, if every encryption involves less than 2⁴³ bytes of data, the differential attack will be ineffective against cipher-text encrypted by the present invention without the Second XOR.

As mentioned above, Super DES with the Second XOR embodiment requires about P⁴ plain-text, which is about 2¹³⁰ blocks. Therefore, it is not necessary to use random RANDfO] and RANDfl]. Therefore, Super DES with the Second XOR uses a fixed RAND table created from the sin(x) values.

It should be understood that the embodiments described herein are merely for illustrative purposes only and it is anticipated that many modifications and adaptations to the embodiments described herein may be made without departing from the scope of the present invention as determined by the claims appended hereto.

Claims

1. A method for data encryption comprising using a generated set of integers in conjunction with a private key to generate randomized integers at least one of which is used for an encryption key.

2. A method for data encryption in accordance with claim 1 , wherein said generated set of integers is generated by a seed of at least two integers.

3. A method for data encryption in accordance with claim 2, wherein said seed integers are changed for each encryption process.

4. A method for data encryption in accordance with claim 1 , further comprising performing at least two exclusive-or operations in at least four rounds.

5. A method for data encryption in accordance with claim 4, wherein said data encryption has R rounds, and further comprising performing said at least two exclusive-or operations in round 2, round 3, round R-2 and round R-1.

6. A method for data encryption in accordance with claim 1 , wherein said encryption key is a round key.

7. A method for data encryption in accordance with claim 1 , wherein said generated set of integers is changed each time a randomized integer is generated.