A Current Perspective on Encryption Algorithms
Dr Lawrie Brown
School of Computer Science,
Australian Defence Force Academy,
Canberra, Australia
Email: Lawrie.Brown@adfa.edu.au
Superceeded by substantially revised version presented to
AUUG98, Sept 1998.
Abstract
This talk will present a perspective on the current state of play in the
field of encryption algorithms, in particular on private key block
ciphers which are widely used for bulk data and link encryption. With
the recent call by the US NIST for submissions to define an Advanced
Encryption Standard to eventually replace the DES, there has been
increased activity in this field. I will briefly describe some of the
known candidates, including the local LOKI97 algorithm.
Introduction
With growing awareness of, and concerns about, computer and
communications security, there is increasing incorporation of
cryptographic algorithms into such systems. This paper presents a brief
overview of the current state of cryptographic algorithms, with an
emphasis on private key block ciphers. It is prompted in part by the US
NIST (National Institute of Standards and Technology) call for
submissions of candidate algorithms for an Advanced Encryption Standard,
due later this year.
Types of Encryption Algorithms
Cryptographic algorithms can be broadly catagorised as follows:
 private (single, shared) key algorithms
 are used for bulk data encryption, as they are comparatively
fast. They do require a secret key to be known by both parties.
Examples include: DES, Blowfish, IDEA, LOKI, RC4.
 public (two) key algorithms
 are used for key validation & distribution, good because a public
key is used, but limited by their computational cost compared
to private key schemes. Examples include: DiffieHellman, ElGamal, RSA
 signature algorithms
 are used to sign & authenticate data, and are also usually public key
based. Examples include: ElGamal, RSA, DSA
 hash algorithms
 are used to compress data down to a fixed size for signing.
Examples include: MD5, Haval, SHA
In practice, many systems involve a combination of these algorithms,
with public key algorithms being used to exchange session keys and
to authenticate a hash of the information, and private key algorithms
to encrypt the data (eg. as in PGP secure email). See any good
crypto text for details, eg Stallings [Stal95], or
Schneier [Schn96].
Block Ciphers Past
In this talk, I will be focusing on Block Ciphers, which are the most
common form of private key algorithms. These operate on a fixed size
data block (eg 64 bits), use a single secret, shared key (eg 56,64,
or128 bits), and generally involve multiple rounds (832) of some
simple, nonlinear function which uses half the value as input, and
whose output is XOR'd with the other half. This is known as a feistel
structure, invented by Horst Feistel of IBM in the early '70's, and its
great advantage is its easy inversion for decryption. There are
various standard modes of use which allow a variable amount of
information to be processed by the algorithm's fixed size inputs and
outputs. For bulk data  ECB, CBC; and for stream data  CFB, OFB.
The best known and most widely used block cipher is the DES, which has
a 64 bit data block and a 56 bit key. It evolved from the earlier
Lucifer algorithm, developed by Feistel and colleagues at IBM in the
early 70's. It has been the standard algorithm for banking and other
applications since 1977.
Any block cipher can theoretically be attacked by exhaustively trying
all possible keys, whether this is feasible or not depends on the
size of the key. If an attack faster than exhaustive search is possible,
then the cipher is regarded as, at least theoretically, broken.
Recently a brute force recovery of a 56bit DES key was demonstrated
[RSAD97], illustrating the advances in
computational speeds in the years since its standardisation.
Also since the early 90's, theoretical attacks on the DES, which are
faster than exhaustive key search, have been developed as discussed
below. In response to this, as an interim measure, we see the
deployment of TripleDES. This uses two (112 bit) or three (162 bit)
keys and three passes of the DES algorithm on each block (at
consequently 1/3 the speed). In the longer term, the US NIST is
looking at standardising a new algorithm.
Aside from DES, a number of other block ciphers have been proposed
in the intervening years. In the late 90's, several proposals were
published by the academic community. The best known of these include:
 FEAL
 a 64bit, nround (where n has grown from 4 to 32+) feistel block cipher
with a 64 or 128 bit key, designed by Shimizu and Miyaguchi from NTT
Japan in 1987. Implemented in both hardware and software, it has been
widely used in Japan. A number of attacks have been developed against
it, which has led to revised versions with more rounds and larger keys.
 IDEA
 a 64bit, 8 round iterated block cipher with a 128bit key,
designed by X. Lai and J. Massey in 1990. It uses the concept of
"mixing operations from different algebraic groups". Best known
for its use in PGP, SSH and other systems, it is one of the
more widely used algorithms at the present time, and is still
believed secure.
 LOKI91
 a 64bit, 16 round, symmetric block cipher with a 64bit key. It
was originally designed by Brown, Pieprzyk and Seberry in 1990
[BrPS90], and later redesigned (and renamed
LOKI91), with improved security in 1991 [BKPS91].
It is also believed secure, and is used by several companies
wanting a licence and patent free Australian algorithm.
Also around this time, Biham and Shamir announced the (re)discovery (in
the public arena) of differential cryptanalysis  a powerful general
technique for attacking iterated block ciphers [BiSh3b].
Subsequently, Matsui announced the discovery
of linear cryptanalysis [Mats93]; and Biham of
related key attacks [Biha94c]. All of these
attacks utilise knowledge of the structure of the cipher to accumulate
information from extremely large numbers of observed encryptions to
obtain information about the (unknown) key used. The success of these
attacks depends on the number of observed encryptions, and decreases
rapidly with increasing numbers of rounds. Eventually a breakeven point
is reached where exhaustive search is faster, and even where the number
of observations required is greater than the total number possible. Thus
these attacks are possible and (theoretically) faster against some
ciphers, eg DES or some FEAL versions, and not against others (eg IDEA,
LOKI91).
In the light of this new (in the public community) knowledge, and
experience with the preceding ciphers, a number of others were
presented. The better known of these include:
 BLOWFISH
 a 64bit, 16 round feistel block cipher with a variable length key,
designed by B. Schneier in 1994. It is optimised for bulk data
encrpytion (since key changes are slow), and uses four large 8*32 bit
random substitution boxes generated from the supplied key, whose outputs are
combined using addition and xor. Used in SSH and other packages, this
cipher is also well known, and is unencumbered by patent or licencing issues.
 CAST
 a 64bit, 8 round feistel block cipher with a 64bit key, designed
by C. Adams and S. Tavares in 1993. It uses six 8*32 bit substitution
boxes (some with data in, some with subkey in) whose outputs are
combined using xor. These substitution boxes are designed for and fixed
per application. It is used in a number of products in Canada (where it
was designed).
 RC2, RC5
 two private key block ciphers developed by RSA Data Security Inc.
The details of both are proprietary, though the RC5 design has
subsequently been published and subject to some analysis. They are
parameterisable, with various sized data and keys, and number of rounds,
possible. These ciphers have been widely licenced and used in products
such as Netscape. However because of their proprietary nature, public
analysis has been limited (nb. RC4 is a stream cipher by the same
people, also widely used, with details released due to its reverse
engineering).
 SAFER
 a 64bit, 6 or higher round, iterated block cipher with
64 or 128 bit keys, designed by J. Massey in 1994.
 TEA
 a simple 64bit, 32 round feistel block cipher with a 128bit key,
designed by Wheeler & Needham [WhNe94] in 1994.
It uses a very simple round function composed of alternating additions
and xor's along with left and right shifts,
iterated over many rounds to provide sufficient complexity.
Has a surprising degree of security for such a simple cipher.
As these ciphers are newer, there has not been as much opportunity for
analysis. Some have already been adopted in a number of systems though.
Most are also characterised by using the same 64 bit data block size as
DES, and either 64 or 128 bit keys (or 40 when lobotomised to insecurity
by US export laws). This is changing in the next generation being
developed for the AES call, as discussed below.
Comparative Speeds
As an illustration, a number of these algorithms have been implemented
in Java (using the Cryptix library [Cryp97]).
In one run, interpreted on our rather loaded SPARC Solaris 1000 system,
the following comparative times were obtained:
Table of Comparative Block Ciphers Timings
IJCE Timing Encryption (1MByte) Key Init
Algorithm Time (ms) Rate (Kbps) 1000 pairs (ms)
   
Blowfish 13592 617 46536
CAST5 15023 558 665
DES 26208 320 279
TripleDES 86904 96 971
IDEA 24696 339 408
LOKI91 15681 534 61
LOKI97 (+) 42340 198 1878
RC2 24073 348 553
RC4 (*) 8113 1033 1267
SAFER 34566 242 1323
Square 18580 451 1061
nb. (*) RC4 is stream cipher; (+) LOKI97 is a proposed new cipher (see below).
Advanced Encryption Standard (AES)
It is clear given the advances in the cryptanalysis of DES, that a replacement
standard encryption algorithm is needed. The US NIST issued a request for
possible candidates in Sept 97 [AES97].
As noted (by Bruce Schneier) at a meeting discussing the proposed call:
Miles Smid presented NIST's goals for AES. They wanted a strong
block encryption algorithm for government and commercial use,
one that would support "standard codebook modes" of encryption,
"significantly more efficient than TripleDES," and with a variable key size.
In the call, they note:
It is intended that the AES will specify an unclassified, publicly
disclosed encryption algorithm available royaltyfree worldwide that is
capable of protecting sensitive government information well into the
next century.
AES Requirements
NIST have specified that proposed algorithms must implement a symmetric
block cipher, with a block size of 128 bits, and keys sizes of 128, 192
and 256 bits (at least). They want an algorithm whose security is at
least as good as TripleDES, but with significantly improved efficiency.
Submissions are due by June 15, 1998. These submissions are to include a
complete specification of the algorithm, its design rationale, computational
efficiency, and expected strength against known forms of attack. Also
to be included are reference implementations in Java (using the Sun JCE 1.2
framework) and C, as well as extensive validation and test values.
Following the submission deadline, NIST will review all submissions for
compliance with the minimum requirements, and will then make all such
publically available.
AES Evaluation
Following submission, there will be two phases of public evaluation.
During the first phase, NIST will evaluate the algorithms, including
using publically submitted evaluations, and select a shortlist.
These will then be more extensively evaluated during the second phase
to select the final candidate algorithm. In the evaluations,
security is the prime consideration, then efficiency and flexibility.
NIST have committed to releasing all nonclassified evaluations of
the candidate algorithms.
AES Candidates
NIST have a policy of not naming any proposed candidates until after the
submission deadline. However, as of Jan 98, NIST have announced that 16
groups have indicated they intend to submit a candidate algorithm.
Apart from our own LOKI97, discussed below, I have not yet seen any
other groups publically announce their intention to submit. However,
personally I'd expect to see variants of Blowfish, CAST, IDEA, SAFER,
and something from NTT Japan. Possibly we may see RC5 or a variant
(the standard version can be configured to meet the AES requirements)
if RSA DSI decide the benefits of submission outway their current
proprietary stance. Hopefully more groups will publically announce their
intentions in the near future.
LOKI97
LOKI97 has evolved from the earlier LOKI89 and LOKI91 ciphers. Whilst
LOKI91 is currently regarded as a secure cipher, immune to both
differential and linear cryptanalysis, its does have some modest
weaknesses in its key schedule and needs an increase in the key size to
overcome possible brute force attacks. The decision to perform this
redesign was timely given the AES Call [AES97].
The proposed LOKI97 cipher is a 16 round Feistel cipher on 128bit data
using a complex nonlinear function. It has a 256bit key schedule which
can be initialised using 128, 192, or 256bit keys. The nonlinear
function features a double layer of substitutionpermutation boxes in
each round (compared to the single layer in most existing ciphers), and
is used in both the key schedule and the data encryption computation.
It also includes a keyed permutation, as well as the more common fixed
substitution and permutations seen in previous versions.
The key schedule is thus vastly more nonlinear (but correspondingly slower)
than previously. The overall computational cost of each encryption round
is about double that of LOKI91, but the anticipated security is also,
hopefully, correspondingly greater.
The key schedule uses 48 rounds (i=1,48)
to compute
the 48 subkeys SK_{i}
as follows:
SK_{i} = K1_{i} = K4_{i1} xor g_{i}(K1_{i1},K3_{i1},K2_{i1})
K4_{i} = K3_{i1}, K3_{i} = K2_{i1}, K2_{i} = K1_{i1}
g_{i}(K1,K3,K2) = f(K1+K3+(Delta*i),K2)
Delta = (sqrt(5)1)*2^{63}
In the data encryption computation,
the 16 rounds (i=16,1)
are as follows:
R_{i1} = L_{i} xor f(R_{i}SK_{3i},SK_{3i1})
L_{i1} = R_{i}SK_{3i}SK_{3i2}
The nonlinear function f is specified as follows:
f(A,B) = Sb(P(Sa(E(KP(A,B)))),B)
composed of keyed permutation KP
, expansion function
E
, a column of 8 substitution boxes Sa
, fixed
permutation P
, and a second column of substitution boxes
with data and key inputs Sb
.
Further details of the design of LOKI97 are available from
[BrLO97b].
Other Observations
Some personal observations about other aspects of cryptographic algorithms.
Key escrow is dead! It has been overtaken by events (including the
AES), is simply not wanted by many around the world, and is bypassed by
the widespread availability of good encryption products without it.
However, key backup is a useful idea, used voluntary by organisations for
good management reasons. This will become more common, and supported,
in products. It is distinct from key escrow in that it applies
to archival data and key access, not communications sessions.
40bit block cipher keys are manifestly insecure! Repeated demonstrations
have illustrated that they can be broken by bruteforce in less than a
week by any group with access to a reasonable pool of workstations
(eg a few labs at the Uni). As discussed by a group of cryptographers
[BDRS98], key lengths should be 75 bits or more
for moderate term security.
To support widespread interaction amongst large communities, we
need (public key) certificate authorities, and we need them now!
Its time to stop arguing about the politics, and do it!
Also to improve security, good, strong, encryption is needed now
in many products, particularly those involving network communications.
With the development of new algorithms, and their public evaluation,
this should be easier than ever before, if only people will address
the political issues and accept its necessity.
Conclusions
This paper presents a brief survey of block ciphers, their past,
and their further development in response to the AES call.
References
 AES97

"Advanced Encryption Standard Call",
NIST, 1997.
http://csrc.ncsl.nist.gov/encryption/aes/aes_home.htm.
 BDRS96

M. Blaze, W. Diffie, R. Rivest, B. Schneier, T. Shimomura, E. Thompson, and M. Weiner,
"Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security",
Jan 1996.
http://www.counterpane.com/keylength.html.
 BKPS91

Lawrence Brown, Matthew Kwan, Josef Pieprzyk, Jennifer Seberry,
"Improving Resistance to Differential Cryptanalysis and the Redesign of LOKI",
in Advances in Cryptology  Asiacrypt'91,
Lecture Notes in Computer Science, Vol 739, SpringerVerlag, pp 3650, 1991.
 BiSh93

Eli Biham, Adi Shamir,
"Differential Cryptanalysis of the Data Encryption Standard",
SpringerVerlag, New York, 1993.
 Biha94c

Eli Biham,
"New Types of Cryptanalytic Attacks Using Related Keys",
Journal of Cryptology, Vol 7, No 4, pp 229246, 1994.
 BrLO97b

L. Brown,
"Design of LOKI97",
Australian Defence Force Academy, Canberra, Australia, Technical Note, Dec 1997.
http://lpb.canb.auug.org.au/adfa/papers/ssp97/loki97b.html.
 BrPS90

Lawrence Brown, Josef Pieprzyk, Jennifer Seberry,
"LOKI  A Cryptographic Primitive for Authentication and Secrecy Applications",
in Advances in Cryptology: Auscrypt '90,
Lecture Notes in Computer Science, Vol 453, SpringerVerlag, pp 229236, 1990.
 Cryp97

"Cryptix Java Cryptographic Library",
1997.
http://www.systemics.com/docs/cryptix/.
 Mats93

Mitsuru Matsui,
"Linear Cryptanalysis Method for DES Cipher",
in Advances in Cryptology  Eurocrypt'93,
Lecture Notes in Computer Science, Vol 765, SpringerVerlag, pp 386397, 1993.
 RSAD97

"Government encryption standard DES takes a fall",
RSA Data Security Inc, 1997.
http://www.rsa.com/des/.
 Schn96

Bruce Schneier,
"Applied Cryptography  Protocols, Algorithms and Source Code in C",
2nd edn, John Wiley and Sons, New York, 1996.
 Stal95

W. Stallings,
"Network and Internetwork Security  Principles and Practice",
PrenticeHall, 1995.
http://www.shore.net/~ws/Security.html.
 WhNe94

David J. Wheeler, Roger M. Needham,
"TEA, a Tiny Encryption Algorithm",
in Fast Software Encryption 2,
Lecture Notes in Computer Science, Vol 1008, SpringerVerlag, pp 363366, 1994.
http://www.cl.cam.ac.uk/ftp/papers/djwrmn/djwrmntea.html.
This paper was presented to the
AUUG (Canberra) Summer Conference, Feb 1998.
The latest version of this paper may be found at:
http://lpb.canb.auug.org.au/adfa/papers/cauugs98/.
Last updated: 16 Feb 98.