DEAL – 128 bit block code number

 

Lars R. Knudsen

On February, 21st 1998

 

Translation from English: Kochetkov N.N.

October 1998

 

The summary

 

We offer the new block code number, DEAL, based on DES (DEA). The size of block DEAL – 128 bits, the size of a key can be 128, 192 or 256 bits. The code number offered by us has some advantages before other schemes: thanking большему to the size of blocks, the problem �attacks under the picked up code number-text� becomes less essential, and speed of enciphering corresponds to speed threefold DES. We assume that the most realistic (or the least unrealistic) attack to any version DEAL’а is an exhaustive search of keys. We have suggested ANSI (institute) to include DEAL in standard ANSI X9.52. Besides we offer DEAL, as the candidate on standard NIST AES.

 

1 Introduction

DES (or DEA) [15] – the block code number with the size of the block 64 bits and 64 bit key in which 56 bits are effective. It is the iterative 16 cyclic code number, in it the code number-text is calculated by the iterative appendix of cyclic function to a clear text. DES has so-called Fejstelevu structure: in each cycle half of block is passed through nonlinear function, its exit XOR’ится with other half then both half are interchanged the position.

For modern appendices the size of key DES became too small. Wiener [20] has shown what to design the specialised device, capable to make exhaustive search of key DES on the average all for 3.5 hours, will cost about 1 million US $. Besides, recently it has been shown, as from program attacks the key in the size of 56 bits does not give considerable protection – key DES has been found by exhaustive search by means extended on Internet’у.

However, in a problem of the insufficient size of a key specified already almost right after publications DES [6]. Therefore, it is frequent DES it is used under the threefold scheme of enciphering named threefold DES’ом (Triple-DES) where the clear text is three times ciphered on three independent keys. In other variant named two-key threefold DES’ом, the clear text is at first ciphered by key К1, then deciphered by key К2 and, at last, is again ciphered by key К1 [18]. However, the size of the block in 64 bits does these schemes vulnerable to attack under the picked up code number-text which is based on that fact that for большего with DES [16] after зашифрования 2³³ blocks it is possible to expect number of operating modes identical blocks of the code number-text, it escapes information on a clear text [5, 9, 13]. Besides, threefold DES with three independent keys it is vulnerable to attack on the dependent (?) key [7], which time of performance about same, as time of exhaustive search of a key in simple DES.

Commission X9.F.1 of National American Institute of Standards (ANSI) works over acceptance of a set of modes of threefold enciphering DES [21]. One of these modes – with a feedback under the code number-text (Triple DES Cipher Block Chaining – TCBC) where the block for a feedback is the block of the code number-text after 3 зашифрований, – also is called as external (outer-) CBC a mode. However, this mode is vulnerable to attack under the picked up code number-text. Therefore, it is offered to use threefold DES in a mode with a feedback under the code number-text with an internal feedback, also is called as internal (inner-) CBC a mode where the feedback is carried out after everyone зашифрования unary DES’ом. Though this mode is less vulnerable to attack under the picked up code number-text, effective attack on key opening can be spent in time much smaller, than it would be possible to expect for the scheme with threefold enciphering [1].

Coupersmith, Jonson and Matyas [5, 4] offer for threefold DES’а mode CBC with OFB Masking (CBCM). Wagner [5] has spent криптоанализ the offer preceding given working out where each of two initial sizes can accept only 2²⁰ values. Mode CBCM is not vulnerable to attack under the picked up code number-text, and security level is supposed 2⁸⁰. Inconvenience of the offered scheme that for зашифрования the block of a clear text in the size of 64 bits is used 4 зашифрования DES on three various keys. Earlier Biham and Knudsen have shown that DES in mode CBCM it is vulnerable to attack under the chosen code number-text in which 2⁶⁵ blocks of the chosen code number-text and which complexity on time – 2⁵⁸ [2] are used.

We offer r-cyclic Fejstelev the code number using DES as cyclic function. The code number with the size of the block of 128 bits and r � in 64 bits of the cyclic keys received on algorithm of the schedule of keys as a result turns out. The schedule of keys is developed so that the size of a key can accept one of three various values: 128, 192 or 256 bits. We recommend to put at first two sizes of a key r = 6, and at the size of a key of 256 bits r = 8. More low we will explain, why we recommend r ≥ 6. If bits of check of parity of each byte of a key are not used at enciphering as it occurs in DES, the operating sizes of keys decrease to 112, 168 and 224 bits accordingly. Exhaustive search of a key still is absolutely impossible (discussion of the sizes of keys in [3]) see, for example. Besides, for successful attack under the picked up code number-text it is necessary to enter an order of 2⁶⁴ blocks of the code number-text. Speed of the code number offered by us same as at threefold DES’а, if to use 6 зашифрований for closing of two blocks of a clear text on 64 bits, moreover, can be applied it with use of existing means DES.

The national Institute of Standards and Technology (NIST) declared recently intention to standardise new algorithm of enciphering, Advanced Encryption Standart, as replacement DES [14]. Statement NIST that before AES will be ready, will pass some years, and that they intend to recognise �Threefold DES-algorithm, time it is accepted by standard ANSI� [14], does initiative ANSI even by more important.

 

2 DEAL

DEAL (Data Encryption Algorithm with Larger blocks – the Algorithm of Enciphering of the Data with the Integrated blocks) is 128 bit block code number with the sizes of a key 128, 192 and 256 bits that further will be designated here DEAL-128, DEAL-192 and DEAL-256 accordingly. All versions can be used in any of four standard modes DES’a [16]. We will begin with the description of work DEAL in mode ECB. Let with = EVES () means ciphered DES value 64 bit And on a key In, and let Y = ЕA_Z (X) means зашифрование DEAL 128 bit X on key Z. Clear text Р is divided into blocks P_i on 128 bits everyone, P = P₁, P₂, …, P_n. The schedule of keys accepts a key To and returns r keys DES RK_i, where i = 1, …, r as it is described more low. We will designate X^L and X^{R the} left and right parts Х accordingly. The Code number-text is calculated as follows. We will put, and we will calculate for j = 1, …, r

	(1)
.	(2)

Let's put. On fig. 1 one cycle DEAL is shown. For DEAL-128 and DEAL-192 we suggest to use 6 cycles, i.e. r = 6. However, as we will see more low, it can be insufficiently for DEAL-256, here it is offered to use 8 cycles, r = 8. It is represented that the version with the size of a key of 256 bits is used only when it is required especially strong зашифрование.

Let's notice that last cycle DEAL of half of block in places vary. The reason in the following: the right part of code number-text С_i is not ciphered in last cycle of i th зашифрования, and only the left part of an input i + 1st зашифрования (which it is equal) is ciphered on last cycle. Т an island the right part C_i would remain not reciphered two cycles. The sphere of action can give it to malefactors as the code number consists all from 6 or 8 cycles. We will notice that similar property is and at DES in mode CBC. However, similar it would be more difficult for using, after all at DES 16 cycles. We will dare to notice that the exchange of places of the right and left parts for last cycle does not influence firmness of the block code number in mode ECB.

Work of mode CBC is in more details described in [16]. So, we will designate clear text blocks on 128 bits P₁, P₂, …, P_n and С₁, С₂, …, С_n – blocks of the code number-text corresponding to them. Then:

,

Where С₀ – initial value.

In DES initial shift IP of the first is applied to a clear text, and is similar before an exit the code number-text is passed through return to it IP^-1. Probably to increase speed DEAL, if to clean from used DES these initial and final shifts. It is easy to show that for reception of correct realisation DEAL’а IP should be enclosed to both parts of a clear text before зашифрованием, and IP^-1 – to both parts of the code number-text.

On an input of the schedule of keys moves s keys DES, К₁, …, K_s, for s = 2, 3, 4, everyone on 64 bit (including 8 verifying bits, the senior bats of each byte), on an exit turns out r keys DES, RК_i. We use the general method, applicable to all three sizes of a key. First we expand s keys to r keys, by repetition and XOR’ения with a new constant for each new repetition. We cipher the expanded list of keys DES’ом in mode CBC with the fixed key and zero initial value. Of the received blocks of the code number-text also are formed connect RK_i. Further we result exact definitions of each of schedules of keys, here To = 0х1234 5678 90ab cdef_x (hexadecimal number) – fixed key DES.

In DEAL-128 connect are generated as follows:

,

,

,

,

,

,

Where – 64 bit integer in which i – 1st bit (indexation goes with 0) is established, and the others are cleared. For example, can be presented as hexadecimal “0х8000 0000 0000 0000_х”.

 

In DEAL-192 connect are generated as follows:

,

,

,

,

,

.

These versions of the schedule of keys demand 6 schedules of keys DES and 6 зашифрований DES on the fixed key. Connect it is necessary to generate only once if them subsequently to keep.

 

In DEAL-256 connect are generated as follows:

,

,

,

,

,

,

,

.

This version of the schedule of keys demands 8 schedules of keys DES and 8 зашифрований DES on the fixed key. Connect it is necessary to generate only once if them subsequently to keep.

 

Let's notice that for all versions of the schedule of keys of 64 bit sizes RK_i are used as keys DES, therefore bits of check of parity RK_i are not used in i th cycle. However, all of 64 bits RK_i as an enciphering exit on a key To, are used at following generation подключа.

Principles of working out of the schedule of keys, first, consist in that connect depended on the greatest number of bits of the basic key, but a lot of work did not demand thus, secondly, at input s the basic keys in the size on 64 bits, any s consecutive подключей should have entropy s ∙ 56 bits, and, at last, there should not be obviously dependent and weak keys and there should not be a property дополнительности (?). We will notice that last two problems are present and in DES, and – all three – in threefold DES. We have noticed that if the basic keys in the size on 64 bits everyone, can be pair of the keys generating identical sets подключей. However, the number of such keys is, seemingly, so insignificant that does not represent threat DEAL’у, applied to enciphering.

Displacement are entered for prevention of occurrence of weak keys. If they were not, there would be keys for which all connect were equal. For example, for DEAL-128 keys K₁ = K₂ = D_K (0) would generate 6 подключей with value 0. Displacement and enciphering on the fixed key prevent occurrence of weak and dependent keys and property дополнительности.

Let's notice that if the bit of check of parity is used in each byte of the basic key, the operating sizes of the offered keys make 112, 168 and 224 bits accordingly.

The above described structure DEAL could be and another – is some possible variants. Instead of Fejstelevoj of structure it is possible to use structure MISTY for the first time described in [12], it allows in a greater degree распараллелить calculations (in hardware execution). However, this structure is developed much later and yet so is deeply analysed. Other variant – to use DEAL in a mode �DES-X� [8], in which additional key XOR’ится with clear text and with the code number-text. Or, instead of use DES as cyclic function, it is possible to use DES-X. The lack of last two offers that it is required to generate большее number подключей, and, hence, the schedule of keys DEAL becomes more difficult.

 

2.1 Firmness DEAL’а

What it is possible to tell about firmness DEAL’а as a whole? First of all, we will notice that for DEAL simple attack meet-in-the-middle (to meet on the middle), similar to such attack on double DES [6, 19], will find keys during an order 2¹⁶⁸ зашифрований for six and 2²²⁴ зашифрований for eight cycles DEAL accordingly, irrespective of the schedule of keys. For this reason, it is offered in DEAL-256 to make at least 8 cycles зашифрования. For DEAL-128 exhaustive search of a key will occupy time of an order 2¹¹² зашифрований.

Patarin in [17] has shown that to distinguish 5 or 6 cyclic n-bit Fejstelev the code number with casual cyclic function from truly casual 2n-bit shift, it is required to know at least 2^2n / 3 clear texts and code numbers-texts corresponding to them. Further he assumes that is required 2ⁿ steam. If to consider that DES models casual shift [1], that, under assumption Patarin’а, it is required an order 2⁶⁴ зашифрований to distinguish DEAL from casual shift; complexity of attack under the picked up code number-text is same also. Fastest of known attacks on a key finding on DEAL (with six cycles) which we understand, – the general attack to 6 cyclic Fejstelevy code numbers [10], in the appendix to DEAL, it demands an order 2¹²¹ зашифрований DES, using an order of 2⁷⁰ chosen clear texts, for any schedule of keys. Further we will define a difference between two sequences of bats, as bit-by-bit XOR.

The statement 1: There is an attack on шестицикловый DEAL with independent cyclic keys which demands an order 2¹²¹ зашифрований DES, using an order of 2⁷⁰ chosen clear texts.

The proof: we Will consider 5 cyclic version and pair of clear texts with a difference α ≠ 0 in the right parts and equal left parts. We will assume that code numbers-texts after 5 cycles have a difference α in the left parts and equal right parts. It means that in both зашифрованиях on inputs DES (in cyclic function DEAL) there were identical values on the first and on the fifth cycles. Further, the difference on inputs DES both on the second and on the fourth cycles was α. But from this it follows that exits DES are equal in the third cycle, so, and inputs DES on the third cycle too are equal. It conducts to the contradiction, since. It means that exits DES on the second and on the fourth cycles are equal that is impossible, since. We have assumed that they are not equal. Thus the assumption that the difference between code numbers-texts after 5 cycles is equal α in left and 0 in the right parts, not truly. In other words, we have defined 5 cyclic differential with zero probability. It can be used for attack on DEAL.

Attack occurs as follows. We will choose 2⁶⁴ clear texts with the fixed left and various right parts, we will designate them at i = 1, …, 2⁶⁴. We will designate code numbers-texts corresponding to them. We will calculate and will find coincidence at i  ≠ j. It is possible to expect an order such 2⁶³ coincidence:. We will put. For all such conterminous pairs and for all values of a key in the sixth cycle we will decipher one cycle of code numbers-texts. If differences after 5 cycles are equal α and 0, prospective value of a key not truly. We will notice that at correct value of a key such differences after 5 cycles cannot appear, but at wrong they will appear with probability 2^-64 for each analyzed pair. Thus with 2⁶³ steams of an order of half of keys will be rejected. At repetition of attack of 56 times there are possible only few values of a key in the sixth cycle. In general, attack demands 56 ∙ 2⁶⁴ ≈ 2⁷⁰ chosen clear texts, (2⁵⁶ + 2⁵⁵ + 2⁵⁴ + … + 2 + 1) ∙ 2⁶⁴ ≈ 2⁵⁷ ∙ 2⁶⁴ = 2¹²¹ зашифрований DES and 2⁶⁴ words ярь�=ш.аааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааа □

The above described attack enclosed to DEAL-192 faster, than exhaustive search of a key, though preconditions rather unrealistic. If attacking it will be possible to find 2⁶⁴ or more steams opened and code numbers-texts, attack under the picked up code number-text can enter into game, and in any case the code number with the big size of the block is required. The most studied attack on DEAL-128 – exhaustive search of a key – demands time of an order 2¹¹² зашифрований. We have not found attack on DEAL with восемью cycles of the best, than the above described exhaustive search of a key �meet-in-the-middle�. Perhaps, there are also faster attacks, for example, successful generalisation of the above-stated attack to 6 cycles, but such plan of attack will be demanded by unreal quantity of the chosen clear texts and an unreal memory size.

Attack to 6 cycles explains our recommendations – to use for DEAL r ≥ 6. At r ≤ 5 probably to specify differentials with zero probability. It means that for some differences in clear text steams, some other differences are impossible in corresponding steams of the code number-text. First of all, such property is not present at some modern block code numbers, then, such differentials can be used in attacks on opening of a key with complexity of an order 2⁸⁸ for DEAL only with 5th cycles [10]. (We Will notice that such attack – only the top limit of level of security).

In the end of this section we will sum up to features DEAL.

�         DEAL has the size of the block of 128 bits and the size of a key 128, 192 or 256 bits (the operating size, accordingly, – 112, 168 or 224 bits).

�         Attack under the picked up code number-text demands an order of 2⁶⁴ blocks of the code number-text.

�         There are no known, probable attacks.

�         DEAL with six cycles has the speed similar to speed threefold DES.

�         DEAL it can be used in standard operating modes.

�         DEAL maintenance DES can be realised on available hardware and program.

�         There are no obviously weak keys and property дополнительности is eliminated.

At last, we will dare to notice that in view of enough difficult schedule of keys, DEAL is not practical to use in stochastic functions.

 

3 Conclusion

We have described the block code number, DEAL, with the size of the block of 128 bits and the size of a key 128, 192 or 256 bits, as alternative to existing threefold modes of enciphering. DEAL it can be used in all four, developed for DES, standard modes of enciphering. For first two sizes of a key the scheme ciphers two blocks on 64 bits, using six зашифрований DES, thus its productivity is equal to productivity threefold DES. Productivity DEAL with восемью cycles (and the size of a key of 256 bits) is equal DES in mode CBCM. Thanks to the big sizes of the block and a key, exhaustive search of a key and attack under the picked up code number-text are impracticable. Besides, weak places DES and threefold DES are avoided. There are no obviously weak keys, does not remain properties дополнительности, and the success of attacks on a dependent key is rather improbable. We recommended ANSI to accept DEAL, as a part [21]. Besides, we offer DEAL, as the possible candidate on Advanced Encryption Standard [14].

 

4 Thanks

The author is grateful Don Coupersmith’y, Bart Preneel’y, Vincent Rijmen’y and Matthew Robshaw’y for set of considerable comments.

 

References

Article original see English, section References.