OOnn tthhee DDeessiiggnn ooff PPeerrmmuuttaattiioonn PP iinn DDEESS TTyyppee CCrryyppttoossyysstteemmss _L_a_w_r_e_n_c_e _B_r_o_w_n _a_n_d _J_e_n_n_i_f_e_r _S_e_b_e_r_r_y_, Department of Computer Science, University College, UNSW, Australian Defence Force Academy, Canberra ACT 2600. Australia. AAbbssttrraacctt This paper reviews some possible design criteria for the permutation _P in a DES style cryptosystem. These permuta- tions provide the diffusion component in a substitution- permutation network. Some empirical rules which seem to account for the derivation of the permutation used in the DES are first presented. Then it is noted that these permu- tations may be regarded as latin-squares which link the outputs of S-boxes to their inputs at the next stage. A subset of these with an extremely regular structure, and which perform well in a dependency analysis are then pre- sented and suggested for use in future schemes of both cur- rent and extended versions of the DES. 11.. IInnttrroodduuccttiioonn The Data Encryption Standard (DES) [NBS77] is currently the only certified encryption standard. It has achieved wide utiliza- tion, particularly in the banking and electronic funds transfer areas, and is an Australian standard [ASA85] among others. However at the time of its introduction, there was a consider- able amount of controversy both due to the classification of its design criteria, and with the choice of a 56-bit key as being too small [DiH77], [Hel79]. 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. In Brown [Bro89], the design criteria used in the DES, both those reported in the literature, and those noted by the author, were discussed. This paper further considers the design of the permutation box _P, which provides the diffusion component of a ssuubb-- ssttiittuuttiioonn--ppeerrmmuuttaattiioonn network in DES type cryptosystems. Such sys- tems were original devised by Shannon [Sha49], who termed this arrangement a mmiixxiinngg ttrraannssffoorrmmaattiioonn. The S-boxes provided ccoonnffuussiioonn of the input, and the P-boxes provided ddiiffffuussiioonn of the S-box out- puts across the inputs to the next stage. 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]. They ensure that every output bit becomes a func- tion of each input bit in as few rounds as possible. Meyer [Mey78] EEuurrooccrryypptt 8899 OOnn tthhee DDeessiiggnn ooff PPeerrmmuuttaattiioonn PP LLaawwrreennccee BBrroowwnn (also in [MeM82]) has quantified this property for the DES, by showing that after 5 rounds, every output bit is a function of all input bits. The authors have used this form of analysis as a mea- sure of effectiveness in the design of permutation _P. It is intended that as a result of this work, the design of the permuta- tion _P in an extended DES style scheme may be performed on a sounder theoretical basis. 22.. CCuurrrreenntt PP--bbooxx DDeessiiggnn CCrriitteerriiaa The central component of the DES cryptosystem is the function _g. It is a composition of an expansion function _E which provides an autoclave function, eight substitution boxes (S-boxes) _S which ccoonnffuussee the input bits, and then permutation _P which ddiiffffuusseess the outputs from each S-box to the inputs of a number of S-boxes in the next stage. A more detailed description of these functions may be found in [NBS77], [ASA85] or [SeP89]. For the purposes of this analysis, it is convenient to regard the DES as a 48-bit mixing function, as detailed in Davio et al [DDF83], which emphasizes the analysis of the functional composition _P._S._E. In Brown [Bro89], the following analysis of, and design rules for, permutation _P were derived by analysing this _S._P._E functional composition, which forms one round of the S-P network: _R(_i)=_L(_i-1)_X_O_R_P(_S(_E(_R(_i-1))_X_O_R_K(_i))). The input of permutation _P may be 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. Instead of express- ing 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 of the S-boxes at the next stage (see Table 1). 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 con- sidered as three pairs _a_b _c_d and _e_f. +-----------------------------------------------+ | TTaabbllee 11 -- PP..EE PPeerrmmuuttaattiioonn | +------+-----------------------+----------------+ |S-box | Inputs from S-boxes | Excluded S-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 the authors noted that permutation _P ensures that: -- 22 -- EEuurrooccrryypptt 8899 OOnn tthhee DDeessiiggnn ooff PPeerrmmuuttaattiioonn PP LLaawwrreennccee BBrroowwnn +o 1 each of the S-box input bits _a_b _c_d _e_f come from the outputs of different S-boxes. +o 2 none of the input bits _a_b _c_d _e_f to a given S-box S(i) comes from the output of that same S-box S(i). +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 as noted in [Dav82]. These rules all appear consistent with the implementation of the avalanche and completeness effects by ensuring that every out- put bit becomes a function of each input bit in as few rounds as possible. Permutations satisfying these criteria have been generated. A total of 178 permutations were found, from 96 possible exclusion sets (the mandatory wirings required by rules 3 and 4 were arbi- trarily assigned to bits _c and _e/_a respectively). Each of these permutations could generate a number of possible permutations 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. However, the authors believe these variations are not significant, and note that they do not change the result of the dependency anal- ysis. Davies [Dav82] and Davio et al [DDF83] have also observed that a functionly equivalent _S._P._E combination can be formed by rearranging the order of the S-box output bits (by rearranging columns), and by then altering permutation _P to compensate. To provide a measure of the effectiveness of the derived per- mutations, Meyer's analysis [Mey78], [MeM82] of ciphertext depen- dence on plaintext bits was extended for these newly derived permu- tations. Briefly, following Meyer, this analysis may be described as follows. 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 depen- dency 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 authors repeated this analy- sis for the current DES, and extended it by analysing each of the 178 empirically generated permutations, as well as the worst case _P (see Table 2), with results as shown in columns 2, 3, and 6 of Table 3. -- 33 -- EEuurrooccrryypptt 8899 OOnn tthhee DDeessiiggnn ooff PPeerrmmuuttaattiioonn PP LLaawwrreennccee BBrroowwnn +----------------------------------------------------------------+ | TTaabbllee 22 -- 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 | +----------------------------------------------------------------+ 33.. FFuurrtthheerr AAnnaallyyssiiss ooff tthhee DDeessiiggnn ooff PPeerrmmuuttaattiioonn PP On closer examination, it was noted that these empirically derived rules for the design of permutation _P, when written as in Table 1, actually result in a latin square. Note that the permuta- tion _P used in the current DES is not a latin square, however it may be transformed into one by selectively swapping some _a_b/_e_f and _c_d pairs to align the highlighted values in Table 1 into the same columns. This transformation makes no difference to the dependency result obtained. A llaattiinn ssqquuaarree is a square of numbers in which each number occurs exactly once in each row and each column (see [DeK74]). Such a result cannot be accidental, and must be related to the desired properties of permutation _P, namely to provide maxi- mal diffusion among the S-boxes. In order to explore this further, some possible permutations which could be used in a DES type sys- tem, and which form a latin-square when written as specified above, were generated. A sample space of 657096 such permutations were generated. These were analysed for effectiveness using Meyer's ciphertext dependence on plaintext, with results as summarized in column 4 of Table 3. The P-box used in the current DES has a propagation profile that falls fairly close to to the median of the 178 permutations generated by my empirical rules. It thus appears to be a fairly representative example of them. In turn, these also fall within the range found for the permutations derived from latin-squares, which obviously encompass the criteria needed to design them. In conjunction with the substantially inferior profile of the worst case P-box, this 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. 44.. AAnnaallyyssiiss ooff tthhee BBeesstt LLaattiinn--SSqquuaarree PPeerrmmuuttaattiioonnss PP From the sample space of 657096 permutations, those resulting in the highest percentage values in the dependency analysis were extracted, a total of 20. When examined, half of the columns (namely the _a_b/_e_f columns) of these permutations were found to be identical, with values as given in Table 4. These columns provide inputs to two S-boxes due to expansion function _E. Further, they were found to be nearly identical to the values generated by apply- ing a difference function of [-2+1_c_d-1+2] _c,_d_a_r_b_i_t_a_r_y (4.1) -- 44 -- EEuurrooccrryypptt 8899 OOnn tthhee DDeessiiggnn ooff PPeerrmmuuttaattiioonn PP LLaawwrreennccee BBrroowwnn to the input S-box number, as shown in full in Table 4. +----------------------------------------------------------------+ | TTaabbllee 44 -- FFiixxeedd CCoolluummnnss iinn SSaammppllee PPeerrmmuuttaattiioonnss PP | +----------------------------------------------------------------+ |Replicated pattern in the best sample permutations | |3 . . 7 8 . . 1 4 . . 5 2 . . 3 6 . . 4 7 . . 8 5 . . 6 1 . . 2 | +----------------------------------------------------------------+ |Pattern generated by a [-2 +1 c d -1 +2] difference function | |2 . . 8 33 . . 1 4 . . 2 5 . . 3 6 . . 4 7 . . 5 8 . . 6 1 . . 77 | +----------------------------------------------------------------+ From this, the authors suggested that permutations with a fixed _a_b/_e_f column structure whose values are those generated by difference function (4.1) may perform well. Permutations of this form were generated, a total of 264 being found. The results of the dependency analysis on these permutations is given in column 5 of Table 3. Those providing the best results were extracted, 100 being found. These were found to be grouped into pairs, with only columns _c and _d interchanged. These pairs in turn were grouped by exclusion set (the set of values not used as inputs to each S-box). The only difference between them is the swapping of some of the _c_d bits, a transformation which makes no difference to the dependency results. A total of 18 exclusion sets were found among the best permutations, and a sample from each is given in Table 5. The authors noted that among these permutations are two which may be generated with difference functions [-2+1+4-3-1+2], and (4.2) [-2+1+3+4-1+2] (4.3) being the first and last entries in Table 5 respectively. These would, the authors believe, be a good choice for implementation in a practical scheme because of their regular structure. 55.. AA RReegguullaarr FFoorrmm ffoorr PPeerrmmuuttaattiioonn PP As further confirmation of this result, all permutations P which have the form of a difference function on the target S-box were constructed, 120 being found. There cipher-plaintext bit dependency propogation is given in Table 3. The 8 best of these are indeed the regular permutations formed using the difference func- tions (4.2) and (4.3), and their equivalents formed by swapping _a_b/_e_f or _c_d columns. They are listed in Table 6. These permuta- tions would thus seem to be excellent candidates for any reimple- mentation of the DES using 64-bit blocks. -- 55 -- EEuurrooccrryypptt 8899 OOnn tthhee DDeessiiggnn ooff PPeerrmmuuttaattiioonn PP LLaawwrreennccee BBrroowwnn +---------------------------------------------------------------------+ | TTaabbllee 66 -- BBeesstt RReegguullaarr FFoorrmm PPeerrmmuuttaattiioonnss PP | +---------------------------------------------------------------------+ |7 4 5 3 8 5 6 4 1 6 7 5 2 7 8 6 3 8 1 7 4 1 2 8 5 2 3 1 6 3 4 2 | |7 5 4 3 8 6 5 4 1 7 6 5 2 8 7 6 3 1 8 7 4 2 1 8 5 3 2 1 6 4 3 2 | |7 5 6 3 8 6 7 4 1 7 8 5 2 8 1 6 3 1 2 7 4 2 3 8 5 3 4 1 6 4 5 2 | |7 6 5 3 8 7 6 4 1 8 7 5 2 1 8 6 3 2 1 7 4 3 2 8 5 4 3 1 6 5 4 2 | |2 4 5 8 3 5 6 1 4 6 7 2 5 7 8 3 6 8 1 4 7 1 2 5 8 2 3 6 1 3 4 7 | |2 5 4 8 3 6 5 1 4 7 6 2 5 8 7 3 6 1 8 4 7 2 1 5 8 3 2 6 1 4 3 7 | |2 5 6 8 3 6 7 1 4 7 8 2 5 8 1 3 6 1 2 4 7 2 3 5 8 3 4 6 1 4 5 7 | |2 6 5 8 3 7 6 1 4 8 7 2 5 1 8 3 6 2 1 4 7 3 2 5 8 4 3 6 1 5 4 7 | +---------------------------------------------------------------------+ 66.. RReegguullaarr PPeerrmmuuttaattiioonnss PP iinn AAnn EExxtteennddeedd DDEESS Permutations of this form were then generated for an extended DES using 128-bit blocks. The 4 best of these were produced using a difference function [-2+1-7+7-1+2] (6.1) and its equivalents by column swapping, as shown in Table 7. The cipher-plaintext dependency results are given in Table 8 (along with those for a worst case, and sample permutations given in a previous paper [Bro89]). These best permutations, and they alone, resulted in complete dependency of ciphertext bits on all plaintext bits in 5 rounds, the same as for the current size scheme. Thus these permutations would seem to be excellent candidates for use in our proposed extended scheme. 77.. CCoonncclluussiioonn A set of empirical design rules for the permutaion _P in a DES style cryptosystem is descibed. It is then noted that permutations generated according to these rules are all latin-squares. When a sample of these latin-square permutations were generated, they were found to span those generated using the empirical rules. The best of these permutations suggested that permutations having a fixed column structure as generated by difference function (4.1) would perform optimally. Permutations with this structure were gener- ated, and the best of these analysed. They were found to include the permutations generated using difference functions (4.2) and (4.3), which are suggested for use in practical DES type schemes because of their regularity. An extension of these results to an extended DES was then analysed, and 4 permutations formed by dif- ference function (6.1) were found to result in complete ciphertext dependency on plaintext bits after 5 rounds, a result that is the same as with the current size scheme. Such permutations are thus suggested for use in any extended schemes. -- 66 -- EEuurrooccrryypptt 8899 OOnn tthhee DDeessiiggnn ooff PPeerrmmuuttaattiioonn PP LLaawwrreennccee BBrroowwnn +-----------------------------------------------------------------------------------------------------------------------------------------------------------------+ | TTaabbllee 77 -- BBeesstt RReegguullaarr FFoorrmm EExxtteennddeedd PPeerrmmuuttaattiioonnss PP | +-----------------------------------------------------------------------------------------------------------------------------------------------------------------+ |2 10 8 16 3 11 9 1 4 12 10 2 5 13 11 3 6 14 12 4 7 15 13 5 8 16 14 6 9 1 15 7 10 2 16 8 11 3 1 9 12 4 2 10 13 5 3 11 14 6 4 12 15 7 5 13 16 8 6 14 1 9 7 15 | |2 8 10 16 3 9 11 1 4 10 12 2 5 11 13 3 6 12 14 4 7 13 15 5 8 14 16 6 9 15 1 7 10 16 2 8 11 1 3 9 12 2 4 10 13 3 5 11 14 4 6 12 15 5 7 13 16 6 8 14 1 7 9 15 | |15 10 8 3 16 11 9 4 1 12 10 5 2 13 11 6 3 14 12 7 4 15 13 8 5 16 14 9 6 1 15 10 7 2 16 11 8 3 1 12 9 4 2 13 10 5 3 14 11 6 4 15 12 7 5 16 13 8 6 1 14 9 7 2 | |15 8 10 3 16 9 11 4 1 10 12 5 2 11 13 6 3 12 14 7 4 13 15 8 5 14 16 9 6 15 1 10 7 16 2 11 8 1 3 12 9 2 4 13 10 3 5 14 11 4 6 15 12 5 7 16 13 6 8 1 14 7 9 2 | +-----------------------------------------------------------------------------------------------------------------------------------------------------------------+ AAcckknnoowwlleeddggeemmeennttss To the members of the Computer Security Research (Crypto) Group, and the other staff in the Department, for their comments on this paper. 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. [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. [DeK74] J. Denes and A. D. Keedwell, _L_a_t_i_n _S_q_u_a_r_e_s _a_n_d _t_h_e_i_r _A_p_p_l_i_c_a_t_i_o_n_s, English Universities Press Limited, London UK, 1974. [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. [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. -- 77 -- EEuurrooccrryypptt 8899 OOnn tthhee DDeessiiggnn ooff PPeerrmmuuttaattiioonn PP LLaawwrreennccee BBrroowwnn [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. [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. [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. [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. [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. [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. -- 88 --