_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 --