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