338
THE SHADE CIPHER:
C.
Adams
Entrust Technologies Limited
750
Heron
Road
Ottawa,
Canada,
K1V
1A7
AN EFFICIENT HAS ASED FEISTEL NETWO
ABSTRACT
In this paper we propose
SHADE,
a balanced Feistel
network that
uses a
modified hash function that accepts
two fixed-size inputs (each of which is the size of the
function output)
as
the round function. This new hash
function blends many of the concepts of MD5 and
SHA-
1,
with some modifications and extensions. A complete
description of the SHADE cipher, including key
schedule, blocksize, round (hash) function, and number
of rounds,
is
presented.
1.
INTRODUCTION
Luby and Rackoff have shown
[I]
that provably secure
pseudorandom permutations can be constructed using
provably secure pseudorandom functions. They achieve
this by building a pseudorandom permutation as a three-
or four-round Feistel network
[2,
31
and using the
pseudorandom functions as the component round
hctions in this network. Although provably secure
pseudorandom functions can be constructed from
provably secure pseudorandom bit generators [4] (and
pseudorandom bit generators whose security rests, for
example, on the difficulty of computing discrete
logarithms
[5]
or factoring
[6]
have been constructed), in
practice such pseudorandom functions execute very
slowly, making the Luby-Rackoff ciphers impractical for
many environments.
Some researchers (see, for example,
[7,
8,
9]),
attracted by the promise of the Luby-Rackoff design,
have replaced provably secure pseudorandom functions
(due to their inefficiency) with hash functions such
as
MD5
[lo],
SHA-1 [Ill, or RIPE-MD [12]. One of the
difficulties with this approach is that such ciphers tend to
be “unbalanced” Feistel networks (in which the plaintext
is split
into
two
pieces
of
unequal size) and
may
need to
incorporate another primitive, such as a stream cipher, to
deal
with
the unbalance.
In this paper we construct balanced Feistel networks
using a new hash hction as the round function.
Although still not provably secure, some confidence may
be gained from the fact that the resulting cipher more
closely resembles the Feistel network which has been
examined
so
carefully in the cryptologic community,
while still resting upon the theoretical underpinnings of
Luby and Rackoff. The hash function used here blends
many of the concepts from
MD5
and SHA-1 with
specific extensions and modifications
so
that it accepts
two
fixed-size inputs, each of which is the size of the
function
output.
The
design principles of this hash
function, along with other aspects of the cipher, are
discussed in some detail.
The remainder of this paper is organized as follows.
Section
2
introduces the concepts and terminology which
will be useful for understanding the remainder
of
the
paper. Section
3
provides a description
of
SHADE,
and
Section
4
discusses the principles involved in its design.
Section
5
comments on the performance of this algorithm
and the paper closes in Section
6
with some concluding
remarks.
2.
CONCEPTS
AND
TERMINOLOGY
This section briefly explains the concepts and
terminology which will be needed throughout the
remainder of the paper. Further details and background
can be found in the papers in which these concepts are
introduced
[
1,2,
31.
2.1.
Feistel Ciphers
Feistel,
et
al,
in
[2,
31
made Shannon’s suggestion of
“mixing transfomations” for cryptographic applications
[I31
more concrete by introducing the Substitution-
Permutation Network. SPNs are alternating layers
of
nonlinear substitution boxes (s-boxes) and linear
permutations which serve to scramble the bits of the
plaintext in a key-dependent way to create the ciphertext;
an s-box layer and a permutation layer together are often
referred to as a single “round”. The input to the cipher is
a “block”
of
plaintext
2n
bits in length. There are
two
general classes
of
SPNs: those which operate on the
full
2n
bits of data in each round; and those which operate on
fewer than
2n
bits (i.e., partial blocks) and then swap the
partial blocks between rounds (the Data Encryption
Standard, DES [14], was constructed
using
this
approach). Note that the second class is what is typically
meant in the cryptographic literature by the terms
“Feistel cipher” and “Feistel network”.
The general structure
of
a Feistel network is shown
in the following diagram. Basic operation is
as
follows.
A message block
of
2n
bits is input and split into a left
half
Lo
and a right half
Ro.
The right half and a subkey
KO
are input to a “round function”,
fo,
the output of
which
is
used
to
modify (through
XOR
addition) the
left
half. Swapping the left and right halves completes round
one. This process continues for as many rounds as are
defined for the cipher
(r
in
the diagram). After the final
round (which does not contain a swap
in
order to
simplify implementation
of
the decryption process), the
left and right halves are concatenated to form the
ciphertext.
CCECE’97
0-7803-3716-6
/97/$5.00
0
1997 IEEE