_A _P_r_o_p_o_s_e_d _D_e_s_i_g_n _F_o_r _A_n _E_x_t_e_n_d_e_d _D_E_S by Lawrence Brown, Dept. of Computer Science, University College, UNSW, Australian Defence Force Academy, Canberra. ACT. 2600. 6 November 1999 AAbbssttrraacctt The Data Encryption standard (DES) has achieved wide utilization, especially in the finan- cial industry. Whilst DES is a standard, the design criteria used in its development have been classi- fied by the US government. This paper reviews what is known about the design criteria for the S-boxes, P-boxes, and key scheduling in the current DES. It then indicates how this information could be used to design an extended scheme with a double length key. There are two main objectives in doing this. One is because of increasing doubts about the abil- ity of DES to withstand an attack based on exhaus- tive key-space searches, using specialized hard- ware. The other is to develop an encryption scheme for which the design rules used are known, and hence open to analysis and criticism. AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS 11.. IInnttrroodduuccttiioonn +o Doubts about the ability of DES to withstand an With the advent of comput- attack based on exhaustive ers, data encryption schemes key-space searches on spe- underwent a revolutionary cialized hardware (cf. the change. The use of computers decision of the US NBS to enabled the cracking of hith- withdraw certification of erto secure schemes, but also DES for all but banking enabled the implementation of applications). This may schemes which until then were be overcome by increasing too complex for use by a manual the key length. cipherclerk. Based on the work of Shannon [Sha49], a new fam- +o The difficulty in obtain- ily of cryptosystems, known as ing DES systems outside SSuubbssttiittuuttiioonn--PPeerrmmuuttaattiioonn nneett-- the US, due to export wwoorrkkss were developed. These restrictions. led to the development of a system known as Lucifer at the +o The desire to develop a IBM Research Laboratories scheme for which all the [Fei73], and subsequently to design criteria used are the Data Encryption Standard known, and hence open to (DES) [NBS77]. It has since criticism. achieved wide utilization, par- ticularly in the banking and This paper will discuss the electronic funds transfer design criteria used in the areas, where it is now an Aus- DES, both those reported in the tralian standard [ASA85]. literature, and those noted by the author, and will illustrate However, there was a con- how they will be applied in siderable amount of controversy building an extended scheme. at the time of its introduc- tion, primarily with the choice of a 56-bit key [DiH77], 22.. DDeessccrriippttiioonn ooff tthhee DDEESS [Hel79]. This was on the grounds that such a key length 22..11.. FFuunnddaammeennttaall CCoonncceeppttss was small enough to be exhaus- tively searched on machines There are two basic cryp- which could be constructed in tographic primitives: ssuubbssttiittuu-- the foreseeable future. With ttiioonn and ttrraannssppoossiittiioonn (or per- the march of computer technol- mutation). In a substitution ogy, this risk appears to be function, each character is rising. However, on all other replaced by some other charac- accounts DES appears to be an ter (see Fig 1). The particu- excellent cryptosystem. No lar substitution used is short-cuts have been found to selected by some kkeeyy. If char- aid in the cryptanalysis of DES acters are represented by a other than by exhaustive key- small number of bits, then such space search. With the current a scheme may be defeated by significant use of DES (espe- enumerating all possible cases cially in banking), there is to find the substitution used. interest in designing and If made sufficiently large and building a DES-type cryptosys- a suitably complex function is tem with an extended key used, such a scheme is in prac- length, for several reasons. tice unbreakable, since it These include: would require the enumeration of all _n! cases (where _n is the -- 11 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS it is easy to build such a function for large numbers of bits. Because of this, the concept of pprroodduucctt cciipphheerrss arose, whereby a series of sub- stitution and transposition functions are combined to form a function which is much more secure than any of its compo- nents. Prior to the introduc- tion of rotor machines, only Fig 1 - Sample S-box simple product ciphers were possible. The development of rotor machines, and subse- number of possible characters). quently computers, changed this Unfortunately it is also significantly. unworkable, since the number of permutations, and hence keys, Shannon [Sha49], in a key would be equally large. paper, described a particular class of product ciphers which In a transposition func- used a number of small (and tion, traditionally, a set of hence implementable) substitu- characters were permuted (rear- tion boxes, termed S-boxes, ranged) into a new order, again connected by large permutation with the particular rearrange- boxes, termed P-boxes (see Fig ment selected by some key. In 3). He termed these mmiixxiinngg modern implementations, this ttrraannssffoorrmmaattiioonnss, whereby the S- becomes a permutation of bits boxes provided ccoonnffuussiioonn of the or a wire-crossing (see Fig 2). input, and the P-boxes provide Since the complexity of such an ddiiffffuussiioonn of the S-box outputs operation is only linear in the across the inputs to the next number of bits used, it may be stage. Such schemes are now easily broken by testing each termed SSuubbssttiittuuttiioonn--PPeerrmmuuttaattiioonn bit in turn to find its new ((SS--PP)) nneettwwoorrkkss. Two key prop- location. It also implies that erties of such S-P networks are the aavvaallaanncchhee property, identi- fied by Feistel [Fei73]; and the ccoommpplleetteenneessss property, identified by Kam and Davida [KaD79]. The avalanche prop- erty states that changing one input bit should result in approximately half of the out- put bits changing. The com- pleteness property states that each output bit must be a com- plex function of every input bit. These properties appear to be important criteria for pro- viding cryptographic strength in the resultant system. More Fig 2 - Sample P-box formally, these may be defined (see [WeT86]) as follows. A function _f is said to have a good avalanche effect if: -- 22 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS Fig 3 - Sample S-P Network, with Avalanche Characteristic for each bit _i, 0<=_i<_m, one stage incorporating the can divide the 2_m plaintext inverses of the substitutions vectors into 2_m-1 pairs _X and permutations used. This is and _X_i such that each pair expensive in terms of both differs only in bit _i; and hardware and software. It is when forming the 2_m-1 preferable to be able to use exclusive-or sums, termed the same hardware for both avalanche vectors encryption and decryption. This may be done by an elegant _V_i=_f(_X)+_f(_X_i) scheme which partitions the input and output blocks into find that about half of two halves, _L(_i-1) and _R(_i-1), these sums are 1. and uses only _R(_i-1) at each round _i (see Fig 4). This half A function _f is complete if: _R(_i-1), along with a key _K(_i), is used as input to the encryp- for each bit _j, 0<=_j<_m in tion function _g (which incorpo- the ciphertext output vec- rates one stage of the S-P net- tor, there is at least one work), and is also copied to pair of plaintext vectors _X _L(_i) for the next round. The and _X_i, which differ only output from _g is exclusive or'd in bit _i, for which _f(_X) (XOR'd) with _L(_i-1) to form and _f(_X_i) differ in bit j _R(_i) for the next round. Thus when decrypting, _L(_i) is copied For a practical scheme back into _R(_i-1) where it is however, it is obviously neces- used as input to _g in order to sary for the recipient to be recover _L(_i-1). Thus it can be able to decipher the message. used to recover the other half This implies that one must be of the input upon decryption. able to compute the inverse of the enciphering function. For the simple S-P network shown above, it would be necessary to provide a separate decryption -- 33 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS Fig 4 - Invertible DES transform 22..22.. DDeessccrriippttiioonn ooff DDEESS The basic DES enciphering chain is shown in Fig 5. In brief, the input block is per- muted by an initial permutation _I_P, is then subjected to a com- plex key-dependent computation, and is finally permuted by _I_P-1, the inverse of the ini- tial permutation. On decipher- ing, the same process is used, except that the complex compo- nent is run backwards, using keys in reverse order, via the method shown above. In more detail, the input block _X of 64 bits is first permuted by the initial permutation1 _I_P, and then divided into two halves _L(0) and _R(0). The complex key-dependent function consists of sixteen rounds in which the left component _L(_i-1) is exclu- sive-or'd (XOR'd) with the out- put of a non-linear function _g whose input is both the right component _R(_i-1) and part of the key _K(_i). The halves are then interchanged to form the input for the next round (with the exception of the final round). Finally the output is permuted by _I_P-1 (the inverse of the input permutation _I_P) to yield the output ciphertext _Y. Fig 5 - DES Enciphering ____________________ 1 for details of the actual permutation used in _I_P (and all The cryptographic security the other functions in the DES) of DES rests, in the main, on see [ASA85], or any of the mod- the complex function _g. It is ern textbooks on cryptography. shown in more detail in Fig 6. Its purpose is to ensure that the final DES output vector _Y -- 44 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS input bits to give a 4-bit out- put. This output is then per- muted by _P. Together these form one stage of an S-P network. The repetition of this proce- dure sixteen times forms the full S-P network. The other critical compo- nent in the DES algorithm is the kkeeyy sscchheedduulliinngg stage. It is responsible for forming the sixteen 48-bit sub-keys used in the rounds of the encryption procedure. It is shown in Fig 7. This function is important since if the same key is used on successive rounds, it can weaken the resulting algorithm. This trap is mostly avoided with the specified key schedul- Fig 6 - DES Function g ing algorithm, except for a small number of keys known as wweeaakk or sseemmii--wweeaakk keys (see (see Fig 5.) is a complex non- [GrT78], [MeM82], [MoS87], linear function of the input, [MoS86], and [ASA85]). In such that there is no easy way detail, the 64-bit key is per- of deriving the input knowing muted by _P_C1. This permutation only the output, short of enu- performs two functions, first merating all possible keys. In it strips the eight parity bits detail, in round _i, 1<=_i<=16, the right component of the mes- sage input _R(_i-1) is first expanded from 32 to 48 bits via an expansion function _E(_R(_i-1)). These are then XOR'd with a 48-bit component extracted from the key _K(_i) to form vector _A. This vector is partitioned into eight 6-bit blocks which are used as input to eight substitution boxes (S- boxes). Each S-box produces a 4-bit output, all of which are concatenated to form the vector _B. This vector is permuted by _P and then XOR'd with the left component _L(_i-1) of the mes- sage. In more detail, each S- box may be regarded as being composed of four substitution functions (row functions or Fig 7 - DES Key Scheduling rows). The (outer) two bits of the 6-bit input selects one of these four functions, which then operates on the (inner) 4 -- 55 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS out, and then distributes the second in designing new and remaining 56 bits over two extended DES style schemes. The 28-bit halves _C(0) and _D(0). S-boxes and P-boxes will be Subsequently these form two examined independently. distinct paths. At each round, each 28-bit register is rotated 33..11.. SS--bbooxx DDeessiiggnn CCrriitteerriiaa left either one or two places according to the following The S-boxes in DES are the schedule: prime source of complexity in the algorithm, and are largely +------+----------------------------r-e-s-p-o-n-s-i-b-l-e--f+or the security of |Round | 1 2 3 4 5 6 7 8 9 10 11 12t1h3e 1s4ch1e5me1.6 |Consequently, con- +------+----------------------------s-i-d-e-r-a-b-l-e---t-i+me has been spent |Shift | 1 1 2 2 2 2 2 2 1 2 2 2 o2n a2nal2ysi1ng |them, and hence +------+----------------------------m-o-r-e---i-s---k-n-o+wn about them than After the shift, the resultant the P-boxes. The actual crite- 28-bit vectors are permuted by ria used are classified secret. _P_C2 (which in fact consists of It has been stated2 that there two 28-bit permutations, not were 12 (possibly 13) criteria one 56-bit permutation), and used, which resulted in about are concatenated together to 1000 suitable S-boxes, of which form the sub-key for that the implementors chose 8. Some round. Note that the total num- of the criteria used were ber of shifts is 28; hence reported to an NBS workshop on _C(16)=_C(0), and _D(16)=_D(0). cryptography [BGK77], and are: When decrypting, it is neces- sary to generate the keys in +o 1 Each row function in an S- reverse order. Because the box is a permutation of final vector is the same as the the integers 0 to 15 initial vector, this can be done by rotating right, reading +o 2 No S-box is a linear or the table in reverse order (and affine function of the with no shift before generating input. the first key). Thus, with minor changes, the same hard- +o 3 Changing 1 input bit to an ware is used for both encryp- S-box results in changing tion and decryption. at least 2 output bits +o 4 _S(_x) and _S(_x+0011002) must 33.. KKnnoowwnn DDEESS DDeessiiggnn CCrriitteerriiaa differ in at least 2 bits (where _S(_x) is the output All the functions used in of an S-box given input the DES are specified in tabu- vector _x). lar form. No description is provided on why they are cho- The following rules were sen. In fact it is stated that labelled (see [BGK77]) as the design criteria are classi- resulting from design criteria: fied. Nonetheless, some of the criteria have been released, +o 5 _S(_x) != _S(_x+11_e_f002) for and others may be deduced by any choice of _e or _f. examining the tables as given. ____________________ The search for the design cri- 2 by Alan G. Konheim at a teria is motivated by two rea- Seminar series on Cryptography sons, first to aid in the in Amsterdam, 1986 [Kon86] cryptanalysis of the DES, and -- 66 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS +o 6 The S-boxes were chosen to choice would require. minimize the difference between the number of 1's A random choice of S-box and 0's in any S-box out- would lead to a distribution put when any single input with a mean around 32. However bit is held constant. Meyer and Matyas stated that as they added more design rules, These criteria and rules the average number of minterms were analysed by Brickell et rose from around 46 in the al. [BMP87]. Criterion 1 early stages, to around 56 in states, in effect, that each the final design (with the dis- row of each S-box is a 1-1 tribution mostly ranging from function. If this were not 52 to 59). The final choice of true, then information would be 8 boxes was taken from the low lost, and recovery of the input end of this range (52 and 53) would be impossible. Criterion in order to make hardware 2 ensures that the DES algo- implementation easier. This rithm as a whole is not linear rule would indicate that the S- or affine. If it were, it would boxes are considerably more substantially reduce the secu- complex than a random choice rity of the scheme, and enable would provide. reasonably easy recovery of a key with a set of plain- text/ciphertext pairs. The next 33..22.. PP--bbooxx DDeessiiggnn CCrriitteerriiaa two criteria 3 and 4, seem to incorporate the concept of the There are a number of per- avalanche effect, in that it mutation networks in the DES ensures that small changes in design, _I_P, _I_P-1, _E, _P, _P_C1, the input result in large and _P_C2. They appear to be per- changes in the output. Rule 5, forming various functions. No reduces the probability that design criteria for them have two different inputs would be been released. However by exam- mapped onto the same output ination of the various net- (nb: function _g is neither 1-1 works, certain features can be nor _o_n_t_o, it must only generate deduced. In general these all the same output from the same appear to be motivated by the input and key); and that the avalanche and completeness cri- image space (ie: the range of teria, in that there is a wide possible values generated by _g) ____________________ is as large as possible. Cri- 3 a minterm is a logical AND teria 1, 3, and 4 seem to imply (boolean product) of input bits rule 6 (which accords with the (and their negations), which original statement that it is a form a necessary (but not suf- consequence of the design cri- ficient) condition for a par- teria). ticular output bit to be as- serted. An output bit may have Another consequence of design its value completely described criteria was noted by Meyer and by the logical OR (boolean sum) Matyas in their book [MeM82], of all its minterms. The num- namely that: ber of minterms in such an ex- pression (after simplification) +o 7 the S-boxes chosen is a measure of its complexity. required significantly In the worst case, for _n input more logical minterms3 to bits, 2_n minterms may be needed implement than a random to describe each output bit. -- 77 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS dispersion of outputs across As with _I_P, it may be imple- the inputs to the next stage. mented with eight iterations of We will examine these networks a 7-bit permutation in turn. {0,1,2,3,4,5,6,7} (the parity bit 8 is discarded). However 33..22..11.. _I_P aanndd _I_P-1 now the permuted value is read out by shifting two 28-bit These two permutations halves toward the centre, form the initial and final rather than to one end, as in steps respectively in the enci- _I_P (see [HGD84]). phering chain for DES. It has been argued [DDF83] that these 33..22..33.. _P aanndd _E permutations have no crypto- graphic significance, since It has been noted by exhaustive plaintext searches Davies [Dav82] and Davio et al can be conducted on messages [DDF83], that _P and _E need to after these transformations be analysed together as the have been applied. This argu- functional composition _P._E (in ment probably does not hold fact _S._P._E should be analysed when DES is used in one of its thus, being one round in an S-P chaining modes. Other reasons network). put forward for their inclusion are that hardware implementa- The expansion function _E tions would benefit, and that is very regular. If the 32-bit it might help thwart other input block is broken into forms of attack. It was also eight 4-bit blocks, then the noted that _I_P is extremely reg- 6-bit output block is formed by ular. As is shown in [HGD84], concatenating the adjacent bit if the input block is broken from the neighboring blocks. If into 8-bit bytes, then it may the 6 bits are labelled _a_b_c_d_e_f be implemented as eight itera- then bits _a_b and _e_f are tions of an 8-bit permutation repeated in the neighboring {2,4,6,8,1,3,5,7} into eight blocks (and include the S-box shift registers: a much more selector bits), whilst the _c_d compact hardware realization, bits are message bits only. than a true 64-bit permutation would imply. Its functionality Now consider the composi- seems to be to distribute bits tion _P._E. The input of _P is from each input byte over all divided into the eight 4-bit eight bytes in the input block. outputs from the S-boxes, and Also it sends all even numbered the output from _E is divided bits to the left hand vector, into the eight 6-bit inputs to and odd numbered bits to the the S-boxes at the next stage. right hand vector. Examination of this network by the author revealed the follow- 33..22..22.. _P_C1 ing: This transformation per- +o 1 each bit in a given 6-bit forms a very similar function output comes from a dif- to _I_P, and additionally strips ferent 4-bit input off the parity bits to reduce the 64-bit key value entered +o 2 no bit in a given 6-bit down to the 56-bit key actually output comes from the cor- used. It is nearly as regular responding 4-bit input as _I_P, except for an asymmetry around the two 28-bit halves. -- 88 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS +o 3 in each 4-bit input block, which become S-box inputs after two bits go to _a_b or _e_f being XOR'd with the expanded bits (ie bits shared by message block. As with the two output blocks), the other components in the key other two go to _c_d bits scheduling stage, it can be regarded as two distinct 28 to These rules all appear 24-bit selections and permuta- consistent with the implementa- tions. There is no interaction tion of the avalanche and com- across the two halves. The pleteness effects. They ensure author has noted that in each that every output bit becomes a 6-bit output block, if the bits function of each input bit in are sorted into ascending order as few rounds as possible. of their input bits, then: Meyer [Mey78] (also in [MeM82]) has shown that with the net- +o 1 no two bits may be spaced works specified in DES, and closer than 3 bits apart assuming S-box output bits are functions of all their input +o 2 the span from lowest to bits, then after 5 rounds, highest input bit number every output bit is a function must be at least 22 of all input bits. This would (alternatively, the aver- appear to be an important con- age spacing must be at sequence of the design crite- least 3 2/3) ria. The first rule implies It is worth noting that that the same bit of the key both Davies [Dav82] and Davio will not be used as input to et al [DDF83] have commented the same S-box on successive that the actual order of output rounds (since in the key sched- bits from each S-box is irrele- ule, bits are shifted only 1 or vant. This is because a func- 2 places). The second results tionly equivalent _S._P._E combi- from application of the nation can be formed by rear- avalanche and completeness ranging the order of bits in effects to ensure that the out- each S-box (by rearranging put depends on all key bits in columns), and then altering as few rounds as possible. permutation _P to compensate. As Meyer [Mey78] (also in [MeM82]) Hoornaert et al [HGD84] show, has shown that with the current this is desirable in order to DES each output bit will be a design an efficient hardware function of all key bits after implementation which minimizes 5 rounds. the number of wire crossings (and hence area) in _P. It cer- 33..33.. KKeeyy SScchheedduulliinngg tainly illustrates that any analysis of these components Aside from the S-boxes and needs to be performed on them P-boxes, the other component as a whole. critical to the security of DES is the kkeeyy sscchheedduulliinngg algo- 33..22..44.. _P_C2 rithm. Several authors [Ber82], [Dav82], [QDD86] have noted The permutation _P_C2 is that DES in fact uses a 768-bit responsible for selecting 48 of key (formed from a 48-bit key the 56 key bits available on to each of 16 stages), which is each round. The output of this generated from the 56-bit key permutation can be analysed in supplied. If either the key terms of the eight 6-bit blocks scheduling is poor [GrT78], or -- 99 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS a bad choice of key is made the foreseeable future. It [Dav82], then the same subkey will also result in a scheme might be repeated for more than for which all the design crite- one round, leading to insecuri- ria used are known, and hence ties in the scheme. No design open to criticism; and which is rules are known for the scheme not bound by foreign government currently in use. However the restrictions. author notes that: 44..11.. SS--bbooxx RReeddeessiiggnn +o 1 each bit is used as input to each S-box Since sixteen S-boxes will be required in the extended +o 2 no bit is used as input to scheme, an additional eight the same S-box on succes- boxes will be required. One sive rounds possibility is simply to reuse the existing eight boxes. This +o 3 the total number of bits option was rejected both for rotated is 56 (which copyright reasons, and because implies that _K(0) = _K(16), of doubts about the cryptologi- enabling the decryption cal security of the current S- operation to use right box 4 [BMP87], [Sha86]. Hence shifts in reverse order). it was decided that sixteen new S-boxes will be generated. Suggestions for alternate Ideally all possible 6*4 bit forms of key scheduling have functions would be generated been made in [Ber82] and and evaluated against the known [QDD86]. design rules, and a subset then selected from those which sat- isfy them. Because of the time 44.. AAnn EExxtteennddeedd DDEESS this would take, it is envi- sioned that a random selection Having analysed the exist- of boxes based on the non-lin- ing DES, and determined as many earity requirement will be gen- of the design rules as possi- erated and tested against the ble, a proposed design of an remaining criteria. This will extended DES style scheme may be done both to generate suit- be outlined. In doing this it able boxes for the proposed is proposed to extend the work design, and to extend work (see of Morris-Yates [Mor86], who [BMP87]) on the analysis of the used a subset of the criteria design rules, identifying both detailed previously. It redundant rules and possibly involves widening all the data new rules. paths to twice the current width, and extending or 44..22.. PP--bbooxx RReeddeessiiggnn redesigning all the S-boxes, P- boxes, and key scheduling. The The use of double width initial motivation for doing data paths implies a complete this was to overcome the doubts redesign of all the permuta- about the ability of DES to tions. _I_P, _I_P-1, and _P_C1 may be withstand an attack based on easily extended because of exhaustive key-space searches ____________________ by doubling the key length. 4 there is a saving of half This raises the effort needed resulting from the well known from 255 trials to 2111 symmetry in DES, namely that trials4, an impossibility in _D_E_S(___X) = ___D___E___S__(___X__) -- 1100 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS their regular design, if they rounds. This impacts on the are included at all. Morris- minimum spacing requirement Yates [Mor86] has argued that between bits selected in _P_C2. because of doubts about their cryptological usefulness, they need not be provided at all 55.. CCoonncclluussiioonn (with the exception of the par- ity stripping component of In this paper, all the _P_C1), saving a significant por- known design criteria for the tion of silicon real-estate. If S-boxes, P-boxes, and key they are provided then the scheduling in the Data Encryp- efficient implementation sug- tion Standard have been identi- gested by Hoornaert et al fied. These all appear to be [HGD84] should be used. related to the avalanche and completeness effects. The The expansion function _E paper concludes with a discus- may also be easily extended sion on how these criteria will because of its regular design. be used to design an extended This leaves the important per- DES, as well as aiding in iden- mutations _P and _P_C2. Because tifying further design crite- these are central components of ria. the S-P network, and key scheduling respectively, they are critical to the security of RReeffeerreenncceess the new scheme. As with the S- boxes, a sample will be ran- domly generated and tested [ASA85] ASA, "_E_l_e_c_t_r_o_n_i_c_s against the known rules, in an _F_u_n_d_s _T_r_a_n_s_f_e_r _- effort to isolate any further _R_e_q_u_i_r_e_m_e_n_t_s _f_o_r design criteria, and to iden- _I_n_t_e_r_f_a_c_e_s_, _P_a_r_t _5_, tify _S._P combinations which are _D_a_t_a _E_n_c_r_y_p_t_i_o_n functionally identical. It is _A_l_g_o_r_i_t_h_m," here that this work differs AS2805.5-1985, most from Morris-Yates, who Standards Association chose purely random permuta- of Australia, Sydney, tions. Australia, 1985. 44..33.. KKeeyy SScchheedduulliinngg [Ber82] T. A. Berson, "Long EExxtteennssiioonn Key Variants of DES," in _A_d_v_a_n_c_e_s _i_n In the extended algorithm, _C_r_y_p_t_o_l_o_g_y _- _|_P_r_o_c_._| the same style of shift and _o_f _C_r_y_p_t_o _8_2, D. select key scheduling will be Chaum, R. L. Rivest used. A new shift schedule will and A. T. Sherman be designed to satisfy the (editors), pp. known design criteria, which 311-313, Plenum will involve some interaction Press, New York, with the design of _P_C2. Since |August.| 23-25, sixteen rounds are planned in 1982. the extended design (provided analyses of the dependence of [BGK77] D. K. Branstead, J. output bits on input and key Gait and S. Katzke, prove satisfactory), this "_R_e_p_o_r_t _o_f _t_h_e implies rotations greater than _W_o_r_k_s_h_o_p _o_n 2 bits in order to have a total _C_r_y_p_t_o_g_r_a_p_h_y _i_n rotation of 112 bits in sixteen _S_u_p_p_o_r_t _o_f _C_o_m_p_u_t_e_r -- 1111 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS _S_e_c_u_r_i_t_y," NBSIR vol. 10, no. 6, pp. 77-1291, National 74-84, |June| 1977. Bureau of Standards, |September.| 1977. [Fei73] H. Feistel, "Cryptography and [BMP87] E. F. Brickell, J. H. Computer Privacy," Moore and M. R. _S_c_i_e_n_t_i_f_i_c _A_m_e_r_i_c_a_n, Purtill, _A_d_v_a_n_c_e_s _i_n vol. 228, no. 5, pp. _C_r_y_p_t_o_l_o_g_y _- _|_P_r_o_c_._| 15-23, |May| 1973. _o_f _C_R_Y_P_T_O_'_8_6, Lecture Notes in Computer [GrT78] E. K. Grossman and B. Science, no. 263, pp. Tuckerman, "Analysis 3-8, |Springer of a Weakened Verlag|, Berlin, Feistel-Like Cipher," 1987. in _|_P_r_o_c_._| _1_9_7_8 _I_E_E_E _|_C_o_n_f_._| _O_n [Dav82] D. W. Davies, "Some _C_o_m_m_u_n_i_c_a_t_i_o_n_s, pp. Regular Properties of 46.3.1-5, IEEE, 1978. the Data Encryption Standard," in [Hel79] M. E. Hellman, "DES _A_d_v_a_n_c_e_s _i_n will be totally _C_r_y_p_t_o_l_o_g_y _- _|_P_r_o_c_._| insecure within ten _o_f _C_r_y_p_t_o _8_2, D. years," _S_P_E_C_T_R_U_M, Chaum, R. L. Rivest vol. 16, no. 7, pp. and A. T. Sherman 31-41, |July| 1979. (editors), pp. 89-96, With rebuttals from Plenum Press, New George I. Davida, York, |August.| Walter Tuchman, and 23-25, 1982. Dennis Branstad. [DDF83] M. Davio, Y. Desmedt, [HGD84] F. Hoornaert, J. M. Fosseprez, R. Goubert and Y. Govaerts, J. Desmedt, "Efficient Hulsbosch, P. Hardware Neutjens, P. Piret, Implementation of the J. Quisquater, J. DES," in _A_d_v_a_n_c_e_s _i_n Vanderwalle and P. _C_r_y_p_t_o_l_o_g_y_: _|_P_r_o_c_._| Wouters, "Analytical _o_f _C_r_y_p_t_o _8_4, Lecture Characteristics of Notes in Computer the DES," in Science, no. 196, G. _A_d_v_a_n_c_e_s _i_n R. Blakley and D. _C_r_y_p_t_o_l_o_g_y _- _|_P_r_o_c_._| Chaum (editors), pp. _o_f _C_r_y_p_t_o _8_3, D. 147-173, |Springer Chaum, R. L. Rivest Verlag|, Berlin, and A. T. Sherman |August.| 1984. (editors), pp. 171-202, Plenum [KaD79] J. B. Kam and G. I. Press, New York, Davida, "Structured |August.| 22-24, Design of 1983. Substitution- Permutation [DiH77] W. Diffie and M. E. Encryption Networks," Hellman, "Exhaustive _|_I_E_E_E _T_r_a_n_s_. _o_n Cryptanalysis of the _C_o_m_p_u_t_e_r_s_|, vol. NBS Data Encryption C-28, no. 10, pp. Standard," _C_o_m_p_u_t_e_r, 747-753, |October.| -- 1122 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS 1979. School of Electrical Engineering, Uni. [Kon86] A. G. Konheim, Sydney, |November.| _C_r_y_p_t_o_g_r_a_p_h_y, 1986. Seminars of Excellence, ORSYS [NBS77] NBS, "_D_a_t_a _E_n_c_r_y_p_t_i_o_n Institute, Amsterdam, _S_t_a_n_d_a_r_d _(_D_E_S_)," |June| 9-11, 1986. FIPS PUB 46, US notes from a seminar National Bureau of series. Standards, Washington, DC, [Mey78] C. H. Meyer, |January.| 1977. "Ciphertext/plaintext and ciphertext/key [QDD86] J. Quisquater, Y. dependence vs number Desmedt and M. Davio, of rounds for the "The Importance of data encryption Good Key Scheduling standard," in _A_F_I_P_S Schemes (How to make _|_C_o_n_f_._| _|_P_r_o_c_._| _4_7, a Secure DES scheme pp. 1119-1126, AFIPS with <= 48 bit Press, Montvale NJ, keys)," in _A_d_v_a_n_c_e_s USA, |June| 1978. _i_n _C_r_y_p_t_o_l_o_g_y _- _C_r_y_p_t_o _8_5, Lecture [MeM82] C. H. Meyer and S. M. Notes in Computer Matyas, _C_r_y_p_t_o_g_r_a_p_h_y_: Science, no. 218, H. _A _N_e_w _D_i_m_e_n_s_i_o_n _i_n C. Williams (editor), _D_a_t_a _S_e_c_u_r_i_t_y, |John pp. 537-542, Wiley & Sons, New |Springer Verlag|, York, 1982. Berlin, 1986. [MoS86] J. H. Moore and G. J. [Sha86] A. Shamir, "On the Simmons, "Cycle Security of DES," in Structure of the Weak _A_d_v_a_n_c_e_s _i_n and Semi-Weak DES _C_r_y_p_t_o_l_o_g_y _- _C_r_y_p_t_o Keys," _E_u_r_o_c_r_y_p_t _8_6 _8_5, Lecture Notes in _- _A_b_s_t_r_a_c_t_s _o_f _P_a_p_e_r_s Computer Science, no. , p. 2.1, Linkoping, 218, H. C. Williams Sweden, 20-22 |May| (editor), pp. 1986. 280-281, |Springer Verlag|, Berlin, [MoS87] J. H. Moore and G. J. 1986. Simmons, _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _|_P_r_o_c_._| [Sha49] C. E. Shannon, _o_f _C_R_Y_P_T_O_'_8_6, Lecture "Communication Theory Notes in Computer of Secrecy Systems," Science, no. 263, pp. _B_e_l_l _S_y_s_t_e_m _T_e_c_h_n_i_c_a_l 9-32, |Springer _J_o_u_r_n_a_l, vol. 28, no. Verlag|, Berlin, 10, pp. 656-715, 1987. |October.| 1949. [Mor86] T. M. Morris-Yates, [WeT86] A. F. Webster and S. "_A_n _n_M_O_S _V_L_S_I E. Tavares, "On the _I_m_p_l_e_m_e_n_t_a_t_i_o_n _o_f _a design of S-Boxes," _D_a_t_a _E_n_c_r_y_p_t_i_o_n in _A_d_v_a_n_c_e_s _i_n _A_l_g_o_r_i_t_h_m," BEng _C_r_y_p_t_o_l_o_g_y _- _C_r_y_p_t_o Honours Thesis, _8_5, Lecture Notes in -- 1133 -- AA PPrrooppoosseedd DDeessiiggnn FFoorr AAnn EExxtteennddeedd DDEESS Computer Science, no. 218, H. C. Williams (editor), pp. 523-534, |Springer Verlag|, Berlin, 1986. -- 1144 --