AAnnaallyyssiiss ooff tthhee DDEESS aanndd IIttss IImmpplliiccaattiioonnss ffoorr tthhee DDeessiiggnn ooff aann EExxtteennddeedd DDEESS1 Technical Report CS88/32 by _L_a_w_r_e_n_c_e _B_r_o_w_n_, Department of Computer Science, University College, UNSW, Australian Defence Force Academy, Canberra ACT 2600. Australia. 6/5/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 ____________________ 1 this technical report is expanded version of, and supersedes an earlier report, TR CS87/8 which also appears in the Proceedings of IFIP Sec'88 [Bro89]. It reflects the material presented at that conference. TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn for which the design rules used are known, and hence open to analysis and criticism. -- 11 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn 11.. IInnttrroodduuccttiioonn With the advent of computers, data encryption schemes under- went a revolutionary change. The use of computers enabled the cracking of hitherto secure schemes, but also enabled the implemen- tation of schemes which until then were too complex for use by a manual cipherclerk. Based on the work of Shannon [Sha49], a new family of cryptosystems, known as SSuubbssttiittuuttiioonn--PPeerrmmuuttaattiioonn nneettwwoorrkkss were developed. These led to the development of a system known as Lucifer at the IBM Research Laboratories [Fei73], and subsequently to the Data Encryption Standard (DES) [NBS77]. It has since achieved wide utilization, particularly in the banking and elec- tronic funds transfer areas, where it is now an Australian standard [ASA85]. However, there was a considerable amount of controversy at the time of its introduction, primarily with the choice of a 56-bit key [DiH77], [Hel79]. This was on the grounds that such a key length was small enough to be exhaustively searched on machines which could be constructed in the foreseeable future. With the march of computer technology, this risk appears to be rising. However, on all other accounts DES appears to be an excellent cryptosystem. No short-cuts have been found to aid in the cryptanalysis of DES other than by exhaustive key-space search. With the current significant use of DES (especially in banking), there is interest in designing and building a DES-type cryptosystem with an extended key length, for several reasons. These include: +o Doubts about the ability of DES to withstand an attack based on exhaustive key-space searches on specialized hardware (cf. the decision of the US NBS to withdraw certification of DES for all but banking applications). This may be overcome by increasing the key length. +o The difficulty in obtaining DES systems outside the US, due to export restrictions. +o The desire to develop a scheme for which all the design crite- ria used are known, and hence open to criticism. This paper will discuss the design criteria used in the DES, both those reported in the literature, and those noted by the author, and will illustrate how they will be applied in building an extended scheme. 22.. DDeessccrriippttiioonn ooff tthhee DDEESS 22..11.. FFuunnddaammeennttaall CCoonncceeppttss There are two basic cryptographic primitives: ssuubbssttiittuuttiioonn and ttrraannssppoossiittiioonn (or permutation). In a substitution function, each character is replaced by some other character (see Fig 1). The particular substitution used is selected by some kkeeyy. If charac- ters are represented by a small number of bits, then such a scheme may be defeated by enumerating all possible cases to find the sub- stitution used. If made sufficiently large and a suitably complex -- 22 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn Fig 1 - Sample S-box function is used, such a scheme is in practice unbreakable, since it would require the enumeration of all _n! cases (where _n is the number of possible characters). Unfortunately it is also unwork- able, since the number of permutations, and hence keys, would be equally large. In a transposition function, traditionally, a set of charac- ters were permuted (rearranged) into a new order, again with the particular rearrangement selected by some key. In modern implemen- tations, this becomes a permutation of bits or a wire-crossing (see Fig 2). Since the complexity of such an operation is only linear in the number of bits used, it may be easily broken by testing each bit in turn to find its new location. It also implies that 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 substitution and transposition functions are combined to form a function which is much more secure than any of its components. Prior to the introduction of rotor machines, only simple product ciphers were possible. The development of rotor machines, and sub- sequently computers, changed this significantly. Fig 2 - Sample P-box -- 33 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn Fig 3 - Sample S-P Network, with Avalanche Characteristic Shannon [Sha49], in a key paper, described a particular class of product ciphers which used a number of small (and hence imple- mentable) substitution boxes, termed S-boxes, connected by large permutation boxes, termed P-boxes (see Fig 3). He termed these mmiixxiinngg ttrraannssffoorrmmaattiioonnss, whereby the S-boxes provided ccoonnffuussiioonn of the input, and the P-boxes provide ddiiffffuussiioonn of the S-box outputs across the inputs to the next stage. Such schemes are now termed SSuubbssttiittuuttiioonn--PPeerrmmuuttaattiioonn ((SS--PP)) nneettwwoorrkkss. Two key properties of such S-P networks are the aavvaallaanncchhee property, identified by Feistel [Fei73]; and the ccoommpplleetteenneessss property, identified by Kam and Davida [KaD79]. The avalanche property states that changing one input bit should result in approximately half of the output bits changing. The completeness property states that each output bit must be a complex function of every input bit. These properties appear to be important criteria for providing cryptographic strength in the resultant system. More formally, these may be defined (see [WeT86]) as follows. A function _f is said to have a good aavvaallaanncchhee effect if: for each bit _i, 0<=_i<_m, one can divide the 2_m plaintext vectors into 2_m-1 pairs _X and _X_i such that each pair differs only in bit _i; and when forming the 2_m-1 exclusive-or sums, termed avalanche vectors _V_i=_f(_X)_X_O_R_f(_X_i) find that about half of these sums are 1. A function _f is ccoommpplleettee if: for each bit _j, 0<=_j<_m in the ciphertext output vector, there is at least one pair of plaintext vectors _X and _X_i, which dif- fer only in bit _i, for which _f(_X) and _f(_X_i) differ in bit j -- 44 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn For a practical scheme however, it is obviously necessary for the recipient to be able to decipher the message. This implies that one must be able to compute the inverse of the enciphering function. For the simple S-P network shown above, it would be nec- essary to provide a separate decryption stage incorporating the inverses of the substitutions and permutations used. This is expensive in terms of both hardware and software. It is preferable to be able to use the same hardware for both encryption and decryp- tion. This may be done by an elegant scheme which partitions the input and output blocks into two halves, _L(_i-1) and _R(_i-1), and uses only _R(_i-1) at each round _i (see Fig 4). This half _R(_i-1), along with a key _K(_i), is used as input to the encryption function _g (which incorporates one stage of the S-P network), and _R(_i-1) is also copied to _L(_i) for the next round. The output from _g is exclusive or'd (XOR'd) with _L(_i-1) to form _R(_i) for the next round. Thus when decrypting, _L(_i) is copied back into _R(_i-1) where it is used as input to _g in order to recover _L(_i-1). Thus it can be used to recover the other half of the input upon decryption. 22..22.. DDeessccrriippttiioonn ooff DDEESS The basic DES enciphering chain is shown in Fig 5. In brief, the input block is permuted by an initial permutation _I_P, is then subjected to a complex key-dependent computation, and is finally permuted by _I_P-1, the inverse of the initial permutation. On deci- phering, 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 permutation2 _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 exclusive- or'd (XOR'd) with the output 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 4 - Invertible DES transform ____________________ 2 for details of the actual permutation used in _I_P (and all the other functions in the DES) see [ASA85], or any of the modern text- books on cryptography (eg [SeP89], [Den82]). -- 55 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn Fig 5 - DES Enciphering The cryptographic security of DES rests, in the main, on the complex function _g. It is shown in more detail in Fig 6. Its pur- pose is to ensure that the final DES output vector _Y (see Fig 5.) is a complex nonlinear function of the input, such that there is no easy way of deriving the input knowing only the output, short of enumerating all possible keys. In detail, in round _i, 1<=_i<=16, the right component of the message 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 message. In more detail, each S-box may be regarded as being composed of four substitution func- tions (row functions or rows). The two (outer or selector) bits of the 6-bit input selects one of these four functions, which then operate on the four (inner or substitution) bits to give a 4-bit -- 66 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn Fig 6 - DES Function g output. This output is then permuted by _P. Together these form one stage of an S-P network. The repetition of this procedure sixteen times forms the full S-P network. The other critical component 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 algo- rithm. This trap is mostly avoided with the specified key schedul- ing algorithm, except for a small number of keys known as wweeaakk or sseemmii--wweeaakk keys (see [GrT78], [MeM82], [MoS86], [MoS86], and [ASA85]). In detail, the 64-bit key is permuted by _P_C1. This per- mutation performs two functions, first it strips the eight parity bits out, and then distributes the remaining 56 bits over two 28-bit halves _C(0) and _D(0). Subsequently these form two distinct paths. At each round, each 28-bit register is rotated left either one or two places according to the following schedule: +---------------------------------------------------+ | TTaabbllee 11 -- KKeeyy SScchheedduullee ffoorr DDEESS | +------+--------------------------------------------+ |Round | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | +------+--------------------------------------------+ |Shift | 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 | +------+--------------------------------------------+ |Total | 1 2 4 6 8 10 12 14 15 17 19 21 23 25 27 28 | +------+--------------------------------------------+ After the shift, the resultant 28-bit vectors are permuted by _P_C2 (which in fact consists of two 28-bit permutations, not one 56-bit permutation), and are concatenated together to form the sub-key for -- 77 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn Fig 7 - DES Key Scheduling that round. Note that the total number of shifts is 28; hence _C(16)=_C(0), and _D(16)=_D(0). When decrypting, it is necessary to generate the keys in reverse order. Because the final vector is the same as the initial vector, this can be done by rotating right, reading the table in reverse order (and with no shift before gener- ating the first key). Thus, with minor changes, the same hardware is used for both encryption and decryption. 33.. KKnnoowwnn DDEESS DDeessiiggnn CCrriitteerriiaa All the functions used in the DES are specified in tabular form. No description is provided on why they are chosen. In fact it is stated that the design criteria are classified. Nonetheless, some of the criteria have been released, and others may be deduced by examining the tables as given. The search for the design crite- ria is motivated by two reasons, first to aid in the cryptanalysis of the DES, and second in designing new and extended DES style schemes. The S-boxes and P-boxes, being the major components of the function _g, will be examined independently. 33..11.. SS--bbooxx DDeessiiggnn CCrriitteerriiaa The S-boxes in DES are the prime source of complexity in the algorithm, and are largely responsible for the security of the scheme. Consequently, considerable time has been spent on analysing them, and hence more is known about them than the P- boxes. The actual criteria used are classified secret. It has been -- 88 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn stated3 that there were 12 (possibly 13) criteria used, which resulted in about 1000 suitable S-boxes, of which the implementors chose 8. Some of the criteria used were reported to an NBS work- shop on cryptography [BGK77], and are: +o 1 Each row function in an S-box is a permutation of the integers 0 to 15 +o 2 No S-box is a linear or affine function of the input. +o 3 Changing 1 input bit to an S-box results in changing at least 2 output bits +o 4 _S(_x) and _S(_x_X_O_R0011002) must differ in at least 2 bits (where _S(_x) is the output of an S-box given input vector _x). The following rules were labelled (see [BGK77]) as resulting from design criteria: +o 5 _S(_x) != _S(_x_X_O_R11_e_f002) for any choice of _e or _f. +o 6 The S-boxes were chosen to minimize the difference between the number of 1's and 0's in any S-box output when any single input bit is held constant. These criteria and rules were analysed by Brickell et al. [BMP87]. Criterion 1 states, in effect, that each row of each S- box is a 1-1 function. If this were not true, then information would be lost, and recovery of the input would be impossible. Cri- terion 2 ensures that the DES algorithm as a whole is not linear or affine. If it were, it would substantially reduce the security of the scheme, and enable reasonably easy recovery of a key with a set of plaintext/ciphertext pairs. The next two criteria 3 and 4, seem to incorporate the concept of the avalanche effect, in that it ensures that small changes to one or two bits of input result in large changes in the output. Rule 5, reduces the probability that two different inputs would be mapped onto the same output (nb: function _g is neither 1-1 nor _o_n_t_o, it must only generate the same output from the same input and key); and that the image space (ie: the range of possible values generated by _g) is as large as possi- ble. Criteria 1, 3, and 4 seem to imply rule 6 (which accords with the original statement that it is a consequence of the design cri- teria), and is related to the S-boxes being permutation functions. Another consequence of design criteria was noted by Meyer and Matyas in their book [MeM82], namely that: +o 7 the S-boxes chosen required significantly more logical minterms4 to implement than a random choice would require. ____________________ 3 by Alan G. Konheim at a Seminar series on Cryptography in Ams- terdam, 1986 [Kon86] 4 a minterm is a logical AND (boolean product) of input bits (and their negations), which form a necessary (but not sufficient) condition for a particular output bit to be asserted. An output bit may have its value completely described by the logical OR (boolean -- 99 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn A random choice of S-box would lead to a distribution with a mean around 32. However Meyer and Matyas stated that as they added more design rules, the average number of minterms rose from around 46 in the early stages, to around 56 in the final design (with the distribution mostly ranging from 52 to 59). The final choice of 8 boxes was taken from the low end of this range (52 and 53) in order to make hardware implementation easier. This rule would indicate that the S-boxes are considerably more complex than a random choice would provide. It also implies that cryptanalysis of DES via formal coding techniques is extremely difficult, as was illustrated by Schaumuller-Bichl [Sch82]. 33..22.. PP--bbooxx DDeessiiggnn CCrriitteerriiaa There are a number of permutation networks in the DES design, _I_P, _I_P-1, _E, _P, _P_C1, and _P_C2. They appear to be performing various functions. No design criteria for them have been released. However by examination of the various networks, certain features can be deduced. In general these all appear to be motivated by the avalanche and completeness criteria, in that there is a wide dis- persion of outputs across the inputs to the next stage. We will examine these networks in turn. 33..22..11.. _I_P aanndd _I_P-1 These two permutations form the initial and final steps respectively in the enciphering chain for DES. It has been argued [DDF83] that these permutations have no cryptographic significance, since exhaustive plaintext searches can be conducted on messages after these transformations have been applied. This argument proba- bly does not hold when DES is used in one of its chaining modes. Other reasons put forward for their inclusion are that hardware implementations would benefit, and that it might help thwart other forms of attack. Further evidence for this may be found in Schau- muller-Bichl [Sch82] who show's that the complexity of DES depends mainly on the S-boxes, key scheduling and number of rounds, rather than the permutations. It was also noted that _I_P is extremely reg- ular. As is shown in [HGD84], if the input block is broken into 8-bit bytes, then it may be implemented as eight iterations of an 8-bit permutation {2,4,6,8,1,3,5,7} into eight shift registers: a much more compact hardware realization, than a true 64-bit permuta- tion would imply. Its functionality seems to be to distribute bits from each input byte over all eight bytes in the input block. Also it sends all even numbered bits to the left hand vector, and odd numbered bits to the right hand vector. ____________________ sum) of all its minterms. The number of minterms in such an ex- pression (after simplification) is a measure of its complexity. In the worst case, for _n input bits, 2_n minterms may be needed to de- scribe each output bit. -- 1100 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn 33..22..22.. _P_C1 This transformation performs a very similar function to _I_P, and additionally strips off the parity bits to reduce the 64-bit key value entered down to the 56-bit key actually used. It is nearly as regular as _I_P, except for an asymmetry around the two 28-bit halves. As with _I_P, it may be implemented with eight itera- tions of a 7-bit permutation {0,1,2,3,4,5,6,7} (the parity bit 8 is discarded). However now the permuted value is read out by shifting two 28-bit halves toward the centre, rather than to one end, as in _I_P (see [HGD84]). 33..22..33.. _P aanndd _E It has been noted by Davies [Dav82] and Davio et al [DDF83], that _P and _E need to be analysed together as the functional compo- sition _P._E. In fact _S._P._E should be analysed thus, being one round in an S-P network, since _R(_i)=_L(_i-1)_X_O_R_P(_S(_E(_R(_i-1))_X_O_R_K(_i))). The expansion function _E is very regular. If the 32-bit input block is broken into eight 4-bit blocks, then the 6-bit output block is formed by concatenating the adjacent bit from the neigh- bouring blocks. If the 6 input bits to an S-box are labelled _a_b_c_d_e_f, then +o bits _a_b and _e_f are replicated in the neighbouring blocks and include the S-box selector bits for both the current (bits _a and _f), previous (bit _b), and next (bit _e) S-boxes, +o bits _c_d are substituted in the current S-box only. Thus _E serves to provide some diffusion by spreading the input bits at each round into adjacent S-boxes. Now consider the composition _P._E. The input of _P is divided into 4-bit outputs from the eight S-boxes, and the output from _E is divided into 6-bit inputs to the eight S-boxes at the next stage. Provided the S-boxes fulfil their design requirements, it may be assumed that all S-box outputs are equivalent, and that the inputs may be considered in the three pairs indicated above. Instead of expressing this permutation in terms of bit positions, it may be written in terms of which S-box output is connected by _P._E to each input bit at the next stage (see Table 2). -- 1111 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn +--------------------------------------------+ | TTaabbllee 22 -- PP..EE PPeerrmmuuttaattiioonn | +------+-----------------------+-------------+ |S-box | Inputs from | missing box | | | a b c d e f | | +------+-----------------------+-------------+ | 1 | 7 4 22 5 6 88 | 3 | | 2 | 6 8 33 7 5 11 | 4 | | 3 | 5 1 44 6 7 22 | 8 | | 4 | 7 2 55 8 33 1 | 6 | | 5 | 3 1 2 66 44 8 | 7 | | 6 | 4 8 77 1 3 55 | 2 | | 7 | 3 5 4 88 2 66 | 1 | | 8 | 2 6 3 11 77 4 | 5 | +------+-----------------------+-------------+ +------+-----------------------+-------------+ From this form, the author notes that: +o 1 each S-box input bit comes from the output of a different S- box +o 2 no input bit to a given S-box comes from the output of the same S-box +o 3 an output from S(i-1) goes to one of the _e_f input bits of S(i), and hence via _E an output from S(i-2) goes to one of the _a_b input bits. +o 4 an output from S(i+1) goes to one of the _c_d input bits of S(i). +o 5 for each S-box output, two bits go to _a_b or _e_f input bits, the other two go to _c_d input bits. This was noted in Davies [Dav82]. These rules all appear consistent with the implementation of the avalanche and completeness effects. They ensure that every output bit becomes a function of each input bit in as few rounds as possible. Meyer [Mey78] (also in [MeM82]) has shown that with the networks specified in DES, then after 5 rounds, every output bit is a function of all input bits. This analysis is repeated an extended in the next section. This result would appear to be an important consequence of the design criteria. Permutations satisfying these criteria were generated. First rules 1 and 2 imply that each S-box takes inputs from 6 S-boxes. Hence one S-box apart from itself must have been missed. There are 264 ways possible to do this, which I termed exclusion sets. Then rules 3, 4 and 5 were used to generate classes of possible permutations5. A total of 178 such classes were found from 96 of the 264 exclusion sets (the others generated no valid permutations, ____________________ 5 the mandatory wirings required by rules 3 and 4 were arbitrar- ily assigned to bits _c and _e/_a respectively. -- 1122 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn due to the missing S-box being one of those required by rules 3 or 4). Each of these classes could generate a number of possible per- mutations by swapping the order of bits in each of the pairs _a_b, _c_d, and _e_f; or by rearranging the order of the four output bits from each S-box. It is worth noting that both Davies [Dav82] and Davio et al [DDF83] have commented that the actual order of output bits from each S-box is irrelevant. This is because a functionly equivalent _S._P._E combination can be formed by rearranging the order of bits in each S-box (by rearranging columns), and then altering permutation _P to compensate. As Hoornaert et al [HGD84] show, this is desirable in order to design an efficient hardware implementation which mini- mizes the number of wire crossings (and hence area) in _P. It cer- tainly illustrates that any analysis of these components needs to be performed on them as a whole. 33..22..44.. _P_C2 The permutation _P_C2 is responsible for selecting 48 of the 56 key bits available on each round. The output of this permutation can be analysed in terms of the eight 6-bit blocks which become S- box inputs after being XOR'd with the expanded message block. As with the other components in the key scheduling stage, it can be regarded as two distinct 28 to 24-bit selections and permutations, with no interaction between the two halves. Again, like the permu- tation _P, _P_C2 needs to be analysed in conjunction with the other components of function _f, and the key scheduling function _K_S. We have _R(_i)=_L(_i-1)_X_O_R_P(_S(_E(_R(_i-1))_X_O_R_P_C2(_K_S(_U,_i)))) _w_h_e_r_e_U=_P_C1(_K) The author has noted that in each 6-bit output block corresponding to an S-box input, if the bits are sorted into ascending order of their input bits, then: +o 1 bits permuted to the same S-box input are no closer than 3 bits apart +o 2 bits permuted to an S-box input must have a span from lowest to highest input bit number of at least 22 of the 28 bits in each key half (alternatively, the average spacing must be at least 3 2/3) +o 3 bits permuted to the selector bits _a,_f on a given S-box must not be adjacent in the sorted list of input bits +o 4 bits not selected by PC2 must be at least 3 places apart Rule 1 implies that the same bit of the key will not be used as input to the same S-box on successive rounds (since in the key schedule, bits are shifted only 1 or 2 places). Rule 2 results from application of the avalanche and completeness effects to ensure -- 1133 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn that the output depends on all key bits in as few rounds as possi- ble, again as confirmed by Meyer [Mey78] (also in [MeM82]). Rule 3 ensures that the same bit is not used as a selector bit on succes- sive permutations to an S-box. Rule 4 ensures that the same bit will not be missed on successive rounds (ie: that all keys bits are used as soon as possible). 33..33.. KKeeyy SScchheedduulliinngg Aside from the S-boxes and P-boxes, the other component criti- cal to the security of DES is the kkeeyy sscchheedduulliinngg algorithm (see Schaumuller-Bichl [Sch82]). Several authors [Ber82], [Dav82], [QDD86] have noted that DES in fact uses a 768-bit key (formed from a 48-bit key to each of 16 stages), which is generated from the 56-bit key supplied. If either the key scheduling is poor [GrT78], or a bad choice of key is made [Dav82], then the same subkey might be repeated for more than one round, leading to insecurities in the scheme. No design rules have been published for the scheme cur- rently in use. The design of the key scheduling function is obvi- ously related to the design of _P_C2 by rules 1 and 4 given above. The author notes that the key scheduling function ensures that: +o 1 each bit is used as input to each S-box +o 2 no bit is used as input to the same S-box on successive rounds +o 3 the total number of bits rotated is 56 (which implies that _K(0) = _K(16), enabling the decryption operation to use right shifts in reverse order). Suggestions for alternate forms of key scheduling have been made in [Ber82] and [QDD86]. 44.. CCiipphheerrtteexxtt DDeeppeennddeennccyy AAnnaallyyssiiss One technique to provide a measure of the ability of a given S-P design to fulfil the completeness effect, is to analysis how rapidly the output bits become dependent on every input and key bit. This analysis was first performed by Meyer [Mey78] (also in [MeM82]). A basic assumption in this analysis is that each S-boxes ensures that every output bit was a complex function of all its input bits. 44..11.. CCiipphheerrtteexxtt DDeeppeennddeennccee ooff PPllaaiinntteexxtt BBiittss To provide a measure of this dependency, a 64*64 array _G_a,_b is formed. Each element _G_a,_b(_i,_j) of which specifies a dependency of output bit _X(_j) on input bit _X(_i), between rounds _a and _b. The number of marked elements in _G0,_r indicates the degree to which complete dependence was achieved by round _r. Details of the derivation of this matrix, and the means by which entries are prop- agated, may be found in [MeM82]. The author repeated this analysis for the current DES, and extended it by analysing each of the 178 candidates for permutation _P, as well as for a worst case _P (see Table 3). -- 1144 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn +---------------------------+ |TTaabbllee 33 -- WWoorrsstt CCaassee DDEESS PP | +---------------------------+ | 1 1 1 1 | | 2 2 2 2 | | 3 3 3 3 | | 4 4 4 4 | | 5 5 5 5 | | 6 6 6 6 | | 7 7 7 7 | | 8 8 8 8 | | | +---------------------------+ The results are summarized in Table 4, and lead to the follow- ing conclusions: +o the current DES P results in complete ciphertext-plaintext dependence after 5 rounds. +o all 178 candidate permutations _P result in complete dependence after 5 rounds. +o the worst case permutation _P results in complete dependence after 7 rounds. Here _E alone is relied upon to provide diffu- sion. +-----------------------------------------+ |TTaabbllee 44 -- DDeeppeennddeennccyy ooff CCiipphheerrtteexxtt bbiittss | | oonn PPllaaiinntteexxtt bbiittss iinn DDEESS | +-------+--------+--------------+---------+ |Round | Std P | Candidate P |Worst P | +-------+--------+--------------+---------+ | 1 | 6.25 | 6.25 | 6.25 | | 2 | 32.06 | 32.03-32.10 | 21.09 | | 3 | 73.49 | 73.44-73.58 | 43.75 | | 4 | 96.90 | 96.87-96.95 | 68.75 | | 5 |100.00 | 100.00 | 89.06 | | 6 |100.00 | 100.00 | 98.44 | | 7 |100.00 | 100.00 | 100.00 | | 8 |100.00 | 100.00 | 100.00 | | | | | | +-------+--------+--------------+---------+ The P-box used in the current DES has a propagation profile that falls fairly close to to the median of the 178 classes I have identified. It thus appears to be a fairly representative example of them. In conjunction with the substantially inferior profile of the worst case P-box, this also provides a strong indication that the design rules identified are comprehensive, at least as far as this aspect of the P-box design is concerned. -- 1155 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn 44..22.. CCiipphheerrtteexxtt DDeeppeennddeennccee oonn KKeeyy BBiittss This analysis is substantially more complex, since it is dependent on the choices of permutations P and PC2 as well as the KS the key schedule. To date, this dependency has been analysed for each of the P permutations used above, with the current key schedule, and with the current, worst case, and a sample regular PC2. To quantify this dependency, a 64*56 array _F_a,_b is formed, each element of which specifies a dependency of output bit _X(_j) on key bit _U(_i). The vector _U is that formed after PC1 is applied, ie _U=_P_C1(_K). The number of marked elements in _G0,_r will be examined to provide a profile of the degree of dependence achieved by round _r. Details of the derivation of this matrix, and the means by which entries are propagated, as before, may be found in [MeM82]. The author repeated this analysis for the current DES, and extended it as indicated before. The results are summarized in Table 5 for the current PC2, Table 6 for a worst case PC2, and Table 7 for a sample PC2. The sample PC2 was designed to satisfy the current rules known, and to use a regular wiring. It is listed in Table 8. These results have led to the following conclusions: +o there are two errors in Meyers analysis. Firstly in his key schedule implementation he appears to have shifted, rather than rotated key bits. This alters the "type" of dependence, but not the number of dependent bits. Secondly, he appears to have miscalculated the dependence percentage. This same error was made in his cipher-plaintext dependence analysis in his original paper, but was corrected in his book. This did not occur in this analysis, and I suspect the same systematic error was at fault. +o the current DES PC2 results in complete ciphertext-key depen- dence after 5 rounds for current candidate permutations P, and in 7 rounds for the worst case permutation P. +o the worst case DES PC2 results in complete ciphertext-key dependence after 7 rounds for current candidate permutations P, and in 9 rounds for the worst case permutation P. Here _E along with the key schedule are relied upon to provide diffu- sion. +o the sample DES PC2 results in complete ciphertext-key depen- dence after 5 rounds for current candidate permutations P, and in 6 rounds for the worst case permutation P. Interestingly, the profile is slightly worse for the current and candidate permutations P, but significantly better for the worst case. -- 1166 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn +----------------------------------------+ |TTaabbllee 55 -- DDeeppeennddeennccyy ooff CCiipphheerrtteexxtt bbiittss | | oonn KKeeyy bbiittss iinn DDEESS wwiitthh CCuurrrreenntt PPCC22 | +-------+--------+-------------+---------+ |Round |Std P |Candidate P | Worst P | +-------+--------+-------------+---------+ | 1 | 5.36 | 5.36 | 5.36 | | 2 |39.17 |38.39-39.29 | 24.67 | | 3 |82.25 |81.25-82.48 | 53.12 | | 4 |98.44 |98.21-98.55 | 79.69 | | 5 |100.00 | 100.00 | 95.65 | | 6 |100.00 | 100.00 | 99.78 | | 7 |100.00 | 100.00 | 100.00 | | 8 |100.00 | 100.00 | 100.00 | | | | | | +-------+--------+-------------+---------+ +-------------------------------------------+ |TTaabbllee 66 -- DDeeppeennddeennccyy ooff CCiipphheerrtteexxtt bbiittss oonn | | KKeeyy bbiittss iinn DDEESS wwiitthh WWoorrsstt CCaassee PPCC22 | +-------+---------+--------------+----------+ |Round | Std P | Candidate P | Worst P | +-------+---------+--------------+----------+ | 1 | 5.36 | 5.36 | 5.36 | | 2 | 42.19 | 42.19 | 21.65 | | 3 | 81.47 | 81.47 | 43.97 | | 4 | 91.29 | 91.29 | 67.41 | | 5 | 96.21 | 96.21 | 86.61 | | 6 | 99.55 | 99.55 | 95.31 | | 7 | 100.00 | 100.00 | 97.99 | | 8 | 100.00 | 100.00 | 99.55 | | | | | | +-------+---------+--------------+----------+ +-------------------------------------------+ |TTaabbllee 77 -- DDeeppeennddeennccyy ooff CCiipphheerrtteexxtt bbiittss oonn | | KKeeyy bbiittss iinn DDEESS wwiitthh SSaammppllee PPCC22 | +-------+---------+--------------+----------+ |Round | Std P | Candidate P | Worst P | +-------+---------+--------------+----------+ | 1 | 5.36 | 5.36 | 5.36 | | 2 | 38.62 | 38.39-38.84 | 22.77 | | 3 | 81.47 | 81.25-81.70 | 48.66 | | 4 | 98.21 | 98.21 | 75.45 | | 5 | 100.00 | 100.00 | 94.20 | | 6 | 100.00 | 100.00 | 100.00 | | 7 | 100.00 | 100.00 | 100.00 | | 8 | 100.00 | 100.00 | 100.00 | | | | | | +-------+---------+--------------+----------+ -- 1177 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn +----------------------------+ | TTaabbllee 88 -- SSaammppllee DDEESS PPCC22 | +----------------------------+ |1 5 10 15 20 25 | |2 6 11 16 21 26 | |3 7 12 17 22 27 | |4 8 13 18 23 28 | |29 33 38 43 48 53 | |30 34 39 44 49 54 | |31 35 40 45 50 55 | |32 36 41 46 51 56 | | | +----------------------------+ 55.. AAnn EExxtteennddeedd DDEESS Having analysed the existing DES, and determined as many of the design rules as possible, a proposed design of an extended DES style scheme may be outlined. In doing this it is proposed to extend the work of Morris-Yates [Mor86], who used a subset of the criteria detailed previously. It involves widening all the data paths to twice the current width, and extending or redesigning all the S-boxes, P-boxes, and key scheduling. The initial motivation for doing this was to overcome the doubts about the ability of DES to withstand an attack based on exhaustive key-space searches by doubling the key length. This raises the effort needed from 255 trials to 2111 trials6, an impossibility in the foreseeable future. It will also result in a scheme for which all the design criteria used are known, and hence open to criticism; and which is not bound by foreign government restrictions. 55..11.. SS--bbooxx RReeddeessiiggnn Since sixteen S-boxes will be required in the extended scheme, an additional eight boxes will be required. One possibility is sim- ply to reuse the existing eight boxes, either by using them twice, or by designing an additional eight only. These options were rejected both for copyright reasons, and because of doubts about the cryptological security of the current S-box 4 [BMP87], [Sha86]. Hence it was decided that sixteen new S-boxes will be generated. Ideally all possible 6*4 bit functions would be generated and eval- uated against Both the known design rules, and additional criteria based on non-linearity criteria suggested by Pieprzyk [PiF89] and Carroll7. A subset will then be selected from those which satisfy these criteria. Because of the time this would take, it is envi- sioned that a random selection of boxes based on the non-linearity requirement will be generated and tested against the remaining cri- teria. This will be done both to generate suitable boxes for the proposed design, and to extend work (see [BMP87]) on the analysis of the design rules, identifying both redundant rules and possibly ____________________ 6 there is a saving of half resulting from the well known symme- try in DES, namely that _D_E_S(___X) = ___D___E___S__(___X__) 7 in personal communications. -- 1188 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn new rules. 55..22.. PP--bbooxx RReeddeessiiggnn The use of double width data paths implies a complete redesign of all the permutations. _I_P, _I_P-1, and _P_C1 may be easily extended because of their regular design, if they are included at all. Mor- ris-Yates [Mor86] has argued that because of doubts about their cryptological usefulness, they need not be provided at all (with the exception of the parity stripping component of _P_C1), saving a significant portion of silicon real-estate. If they are provided then the efficient implementation suggested by Hoornaert et al [HGD84] should be used. Initially, I will not be using these func- tions in the extended scheme. The expansion function _E may also be easily extended because of its regular design. This leaves the important permutations _P and _P_C2. Because these are central components of the S-P network, and key scheduling respectively, they are critical to the security of the new scheme. As with the S-boxes, a sample will be randomly gen- erated and tested against the known rules, in an effort to isolate any further design criteria, and to identify _S._P combinations which are functionally identical. It is here that this work differs most from Morris-Yates, who chose purely random permutations. Initially these will be specified as follows: +o P will use the existing design rules, but will have a regular wiring array. eg one proposal has inputs for _S(_i) from _S(_i-2),_S(_i+1),_S(_i+8),_S(_i+5) (see Table 9). Such a regular array leads to efficient implementation in both hardware and software. +--------------------------------+ |TTaabbllee 99 -- SSaammppllee EExxtteennddeedd DDEESS PP | +--------------------------------+ | 15 2 9 6 | | 16 3 10 7 | | 1 4 11 8 | | 2 5 12 9 | | 3 6 13 10 | | 4 7 14 11 | | 5 8 15 12 | | 6 9 16 13 | | 7 10 1 14 | | 8 11 2 15 | | 9 12 3 16 | | 10 13 4 1 | | 11 14 5 2 | | 12 15 6 3 | | 13 16 7 4 | | 14 1 8 5 | | | +--------------------------------+ -- 1199 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn +o PC2 will use the existing rules modified to suit the larger shifts of 3 or 4 places needed in the Key Schedule. This implies that the constant 3 in rules R1 and R4 will become 5 in the initial design. Again as in the case of P, a regular wiring will be used, though it is complicated by the need to select a subset of the bits. One example distributes a bit to each S-box in turn, skipping every 7th bit (see Table 10). +-----------------------------------+ |TTaabbllee 1100 -- SSaammppllee EExxtteennddeedd DDEESS PPCC22 | +-----------------------------------+ | 1 10 20 29 38 48 | | 2 12 21 30 40 49 | | 3 13 22 31 41 50 | | 5 14 23 33 42 51 | | 6 15 24 34 43 52 | | 7 16 26 35 44 54 | | 8 17 27 36 45 55 | | 9 19 28 37 47 56 | |57 66 76 85 94 104 | |58 68 77 86 96 105 | |59 69 78 87 97 106 | |61 70 79 89 98 107 | |62 71 80 90 99 108 | |63 72 82 91 100 110 | |64 73 83 92 101 111 | |65 75 84 93 103 112 | | | +-----------------------------------+ 55..33.. KKeeyy SScchheedduulliinngg EExxtteennssiioonn In the extended algorithm, the same style of shift and select key scheduling will be used. A new shift schedule will be designed to satisfy the known design criteria, which will involve some interaction with the design of _P_C2, as indicated before. Since sixteen rounds are planned in the extended design (provided analy- ses of the dependence of output bits on input and key prove satis- factory), this implies rotations greater than 2 bits in order to have a total rotation of 112 bits in sixteen rounds. This impacts on the minimum spacing requirement between bits selected in _P_C2. One such Key Schedule proposed is given in Table 11. +-----------------------------------------------------+ | TTaabbllee 1111 -- KKeeyy SScchheedduullee ffoorr aann EExxtteennddeedd DDEESS | +------+----------------------------------------------+ |Round | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | +------+----------------------------------------------+ |Shift | 3 3 3 4 4 4 4 3 3 3 4 4 4 4 3 3 | +------+----------------------------------------------+ |Total | 3 6 9 13 17 21 25 28 31 34 38 42 46 50 53 56 | +------+----------------------------------------------+ -- 2200 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn 55..44.. DDeeppeennddeennccyy AAnnaallyyssiiss ooff AAnn EExxtteennddeedd DDEESS To provide an indication of the suitability of the extended rules, Meyer's dependency analysis was applied to the sample permu- tations developed, as well as to the worst case permutations P and PC2 (given in Tables 15 and 16). The results are given in Table 12 for Ciphertext-Plaintext dependence, Table 13 for Ciphertext-Key dependence with a worst case PC2, and in Table 14 for Ciphertext- Key dependence with the sample PC2. These results show that with the sample permutations, the dependency profile is only one round worse than in the current case (consistent with a doubling of the data lengths). With the worst case permutations however, the pro- file worsens significantly. +--------------------------------------------+ |TTaabbllee 1122 -- DDeeppeennddeennccyy ooff CCiipphheerrtteexxtt bbiittss oonn | | PPllaaiinntteexxtt bbiittss iinn EExxtteennddeedd ((112288--bbiitt)) DDEESS | +---------+-----------------+----------------+ | Round | Sample XDES P | Worst XDES P | +---------+-----------------+----------------+ | 1 | 3.125 | 3.125 | | 2 | 17.68 | 10.55 | | 3 | 50.98 | 21.88 | | 4 | 84.47 | 34.38 | | 5 | 98.44 | 46.88 | | 6 | 100.00 | 59.38 | | 7 | 100.00 | 71.88 | | 8 | 100.00 | 84.38 | | 9 | 100.00 | 94.53 | | 10 | 100.00 | 99.21 | | 11 | 100.00 | 100.00 | | 12 | 100.00 | 100.00 | | | | | +---------+-----------------+----------------+ -- 2211 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn +--------------------------------------------+ |TTaabbllee 1133 -- DDeeppeennddeennccyy ooff CCiipphheerrtteexxtt bbiittss oonn | | KKeeyy bbiittss iinn EExxtteennddeedd ((112288--bbiitt)) DDEESS | | wwiitthh aa WWoorrsstt CCaassee PPCC22 | +---------+-----------------+----------------+ | Round | Sample XDES P | Worst XDES P | +---------+-----------------+----------------+ | 1 | 2.68 | 2.68 | | 2 | 19.08 | 11.05 | | 3 | 57.37 | 22.94 | | 4 | 89.51 | 35.71 | | 5 | 98.44 | 49.33 | | 6 | 99.89 | 63.28 | | 7 | 100.00 | 76.12 | | 8 | 100.00 | 87.44 | | 9 | 100.00 | 95.76 | | 10 | 100.00 | 99.22 | | 11 | 100.00 | 99.89 | | 12 | 100.00 | 100.00 | | | | | +---------+-----------------+----------------+ +--------------------------------------------+ |TTaabbllee 1144 -- DDeeppeennddeennccyy ooff CCiipphheerrtteexxtt bbiittss oonn | | KKeeyy bbiittss iinn EExxtteennddeedd ((112288--bbiitt)) DDEESS | | wwiitthh aa SSaammppllee RReegguullaarr PPCC22 | +---------+-----------------+----------------+ | Round | Sample XDES P | Worst XDES P | +---------+-----------------+----------------+ | 1 | 2.68 | 2.68 | | 2 | 20.54 | 13.39 | | 3 | 61.16 | 31.36 | | 4 | 92.86 | 48.77 | | 5 | 99.55 | 62.95 | | 6 | 100.00 | 76.00 | | 7 | 100.00 | 87.61 | | 8 | 100.00 | 95.65 | | 9 | 100.00 | 99.22 | | 10 | 100.00 | 100.00 | | 11 | 100.00 | 100.00 | | 12 | 100.00 | 100.00 | | | | | +---------+-----------------+----------------+ -- 2222 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn +-------------------------------------+ |TTaabbllee 1155 -- WWoorrsstt CCaassee EExxtteennddeedd DDEESS PP | +-------------------------------------+ | 1 1 1 1 | | 2 2 2 2 | | 3 3 3 3 | | 4 4 4 4 | | 5 5 5 5 | | 6 6 6 6 | | 7 7 7 7 | | 8 8 8 8 | | 9 9 9 9 | | 10 10 10 10 | | 11 11 11 11 | | 12 12 12 12 | | 13 13 13 13 | | 14 14 14 14 | | 15 15 15 15 | | 16 16 16 16 | | | +-------------------------------------+ +---------------------------------------+ |TTaabbllee 1166 -- WWoorrsstt CCaassee EExxtteennddeedd DDEESS PPCC22 | +---------------------------------------+ | 1 2 3 4 5 6 | | 7 8 9 10 11 12 | |13 14 15 16 17 18 | |19 20 21 22 23 24 | |25 26 27 28 29 30 | |31 32 33 34 35 36 | |37 38 39 40 41 42 | |43 44 45 46 47 48 | |57 58 59 60 61 62 | |63 64 65 66 67 68 | |69 70 71 72 73 74 | |75 76 77 78 79 80 | |81 82 83 84 85 86 | |87 88 89 90 91 92 | |93 94 95 96 97 98 | |99 100 101 102 103 104 | | | +---------------------------------------+ 66.. CCoonncclluussiioonn In this paper, all the known design criteria for the S-boxes, P-boxes, and key scheduling in the Data Encryption Standard have been identified. These all appear to be related to the avalanche and completeness effects. The paper concludes with a discussion on how these criteria will be used to design an extended DES, as well as aiding in identifying further design criteria. -- 2233 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn AAcckknnoowwlleeddggeemmeennttss To my supervisors: Dr. Jennifer Seberry, and Dr. Ah Chung Tsoi; the members of the Crypto group: Leisa Condie, Thomas Hard- jono, Arthur Lagos, Mike Newberry, and Dr. Josef Pieprzyk; and to: Dr. George Gerrity, Dr. Andrez Goscinski, Dr. Charles Newton, and Dr. Michael Wagner, for their comments on, suggestions about, and critiques of this paper. Thankyou. RReeffeerreenncceess [ASA85] ASA, "_E_l_e_c_t_r_o_n_i_c_s _F_u_n_d_s _T_r_a_n_s_f_e_r _- _R_e_q_u_i_r_e_m_e_n_t_s _f_o_r _I_n_t_e_r_f_a_c_e_s_, _P_a_r_t _5_, _D_a_t_a _E_n_c_r_y_p_t_i_o_n _A_l_g_o_r_i_t_h_m," AS2805.5-1985, Standards Association of Australia, Sydney, Australia, 1985. [Ber82] T. A. Berson, "Long Key Variants of DES," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _|_P_r_o_c_._| _o_f _C_r_y_p_t_o _8_2, D. Chaum, R. L. Rivest and A. T. Sherman (editors), pp. 311-313, Plenum Press, New York, |August.| 23-25, 1982. [BGK77] D. K. Branstead, J. Gait and S. Katzke, "_R_e_p_o_r_t _o_f _t_h_e _W_o_r_k_s_h_o_p _o_n _C_r_y_p_t_o_g_r_a_p_h_y _i_n _S_u_p_p_o_r_t _o_f _C_o_m_p_u_t_e_r _S_e_c_u_r_i_t_y," NBSIR 77-1291, National Bureau of Standards, |September.| 1977. [BMP87] E. F. Brickell, J. H. Moore and M. R. Purtill, _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _|_P_r_o_c_._| _o_f _C_R_Y_P_T_O_'_8_6, Lecture Notes in Computer Science, no. 263, pp. 3-8, |Springer Verlag|, Berlin, 1987. [Bro89] L. Brown, "A Proposed Design for an Extended DES," in _C_o_m_p_u_t_e_r _S_e_c_u_r_i_t_y _i_n _t_h_e _A_g_e _o_f _I_n_f_o_r_m_a_t_i_o_n, W. J. Caelli (editor), North-Holland, Amsterdam, 1989. [Dav82] D. W. Davies, "Some Regular Properties of the Data Encryption Standard," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _|_P_r_o_c_._| _o_f _C_r_y_p_t_o _8_2, D. Chaum, R. L. Rivest and A. T. Sherman (editors), pp. 89-96, Plenum Press, New York, |August.| 23-25, 1982. [DDF83] M. Davio, Y. Desmedt, M. Fosseprez, R. Govaerts, J. Hulsbosch, P. Neutjens, P. Piret, J. Quisquater, J. Vanderwalle and P. Wouters, "Analytical Characteristics of the DES," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _|_P_r_o_c_._| _o_f _C_r_y_p_t_o _8_3, D. Chaum, R. L. Rivest and A. T. Sherman (editors), pp. 171-202, Plenum Press, New York, |August.| 22-24, 1983. [Den82] D. E. Denning, _C_r_y_p_t_o_g_r_a_p_h_y _a_n_d _D_a_t_a _S_e_c_u_r_i_t_y, Addison- Wesley, 1982. [DiH77] W. Diffie and M. E. Hellman, "Exhaustive Cryptanalysis of the NBS Data Encryption Standard," _C_o_m_p_u_t_e_r, vol. 10, no. 6, pp. 74-84, |June| 1977. -- 2244 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn [Fei73] H. Feistel, "Cryptography and Computer Privacy," _S_c_i_e_n_t_i_f_i_c _A_m_e_r_i_c_a_n, vol. 228, no. 5, pp. 15-23, |May| 1973. [GrT78] E. K. Grossman and B. Tuckerman, "Analysis of a Weakened Feistel-Like Cipher," in _|_P_r_o_c_._| _1_9_7_8 _I_E_E_E _|_C_o_n_f_._| _O_n _C_o_m_m_u_n_i_c_a_t_i_o_n_s, pp. 46.3.1-5, IEEE, 1978. [Hel79] M. E. Hellman, "DES will be totally insecure within ten years," _S_P_E_C_T_R_U_M, vol. 16, no. 7, pp. 31-41, |July| 1979. With rebuttals from George I. Davida, Walter Tuchman, and Dennis Branstad. [HGD84] F. Hoornaert, J. Goubert and Y. Desmedt, "Efficient Hardware Implementation of the DES," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y_: _|_P_r_o_c_._| _o_f _C_r_y_p_t_o _8_4, Lecture Notes in Computer Science, no. 196, G. R. Blakley and D. Chaum (editors), pp. 147-173, |Springer Verlag|, Berlin, |August.| 1984. [KaD79] J. B. Kam and G. I. Davida, "Structured Design of Substitution-Permutation Encryption Networks," _|_I_E_E_E _T_r_a_n_s_. _o_n _C_o_m_p_u_t_e_r_s_|, vol. C-28, no. 10, pp. 747-753, |October.| 1979. [Kon86] A. G. Konheim, _C_r_y_p_t_o_g_r_a_p_h_y, Seminars of Excellence, ORSYS Institute, Amsterdam, |June| 9-11, 1986. notes from a seminar series. [Mey78] C. H. Meyer, "Ciphertext/plaintext and ciphertext/key dependence vs number of rounds for the data encryption standard," in _A_F_I_P_S _|_C_o_n_f_._| _|_P_r_o_c_._| _4_7, pp. 1119-1126, AFIPS Press, Montvale NJ, USA, |June| 1978. [MeM82] C. H. Meyer and S. M. Matyas, _C_r_y_p_t_o_g_r_a_p_h_y_: _A _N_e_w _D_i_m_e_n_s_i_o_n _i_n _D_a_t_a _S_e_c_u_r_i_t_y, |John Wiley & Sons, New York, 1982. [MoS86] J. H. Moore and G. J. Simmons, "Cycle Structure of the Weak and Semi-Weak DES Keys," _E_u_r_o_c_r_y_p_t _8_6 _- _A_b_s_t_r_a_c_t_s _o_f _P_a_p_e_r_s , p. 2.1, Linkoping, Sweden, 20-22 |May| 1986. [Mor86] T. M. Morris-Yates, "_A_n _n_M_O_S _V_L_S_I _I_m_p_l_e_m_e_n_t_a_t_i_o_n _o_f _a _D_a_t_a _E_n_c_r_y_p_t_i_o_n _A_l_g_o_r_i_t_h_m," BEng Honours Thesis, School of Electrical Engineering, Uni. Sydney, |November.| 1986. [NBS77] NBS, "_D_a_t_a _E_n_c_r_y_p_t_i_o_n _S_t_a_n_d_a_r_d _(_D_E_S_)," FIPS PUB 46, US National Bureau of Standards, Washington, DC, |January.| 1977. [PiF89] J. Pieprzyk and G. Finkelstein, "Permutations that Maximize Non-Linearity and Their Cryptographic Significance," in _C_o_m_p_u_t_e_r _S_e_c_u_r_i_t_y _i_n _t_h_e _A_g_e _o_f _I_n_f_o_r_m_a_t_i_o_n, W. J. Caelli (editor), North-Holland, Amsterdam, 1989. -- 2255 -- 66//55//9999 TTRR CCSS8888//3322 DDEESS AAnnaallyyssiiss aanndd EExxtteennssiioonn LLaawwrreennccee BBrroowwnn [QDD86] J. Quisquater, Y. Desmedt and M. Davio, "The Importance of Good Key Scheduling Schemes (How to make a Secure DES scheme with <= 48 bit keys)," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _C_r_y_p_t_o _8_5, Lecture Notes in Computer Science, no. 218, H. C. Williams (editor), pp. 537-542, |Springer Verlag|, Berlin, 1986. [Sch82] I. Schaumuller-Bichl, "Cryptanalysis of the Data Encryption Standard by the Method of Formal Coding," in _C_r_y_p_t_o_g_r_a_p_h_y_: _|_P_r_o_c_._| _o_f _t_h_e _w_o_r_k_s_h_o_p _o_n _C_r_y_p_t_o_g_r_a_p_h_y _(_E_u_r_o_c_r_y_p_t _8_2_), Lecture Notes in Computer Science, no. 149, T. Beth (editor), pp. 235-255, |Springer Verlag|, Berlin, |March.| 29 - |April.| 2, 1982. [SeP89] J. Seberry and J. Pieprzyk, _C_r_y_p_t_o_g_r_a_p_h_y_: _A_n _I_n_t_r_o_d_u_c_t_i_o_n _t_o _C_o_m_p_u_t_e_r _S_e_c_u_r_i_t_y, |Prentice Hall, Englewood Cliffs, NJ|, 1989. [Sha86] A. Shamir, "On the Security of DES," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _C_r_y_p_t_o _8_5, Lecture Notes in Computer Science, no. 218, H. C. Williams (editor), pp. 280-281, |Springer Verlag|, Berlin, 1986. [Sha49] C. E. Shannon, "Communication Theory of Secrecy Systems," _B_e_l_l _S_y_s_t_e_m _T_e_c_h_n_i_c_a_l _J_o_u_r_n_a_l, vol. 28, no. 10, pp. 656-715, |October.| 1949. [WeT86] A. F. Webster and S. E. Tavares, "On the design of S- Boxes," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _C_r_y_p_t_o _8_5, Lecture Notes in Computer Science, no. 218, H. C. Williams (editor), pp. 523-534, |Springer Verlag|, Berlin, 1986. -- 2266 -- 66//55//9999