A Current Perspective on Encryption Algorithms
Dr Lawrie Brown
School of Computer Science,
Australian Defence Force Academy,
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. I will initially
survey some of the more popular and interesting algorithms currently in
use. Then I'll describe the recent call by the US NIST for submissions
to define an Advanced Encryption Standard to eventually replace the DES.
I will sketch the requirements they've given and briefly describe the
candidates, and the current state of their evaluation.
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. These are widely used for
applications requiring bulk data or link encryption.
It has been prompted in part by the US
NIST (National Institute of Standards and Technology) call for
submissions of candidate algorithms for an Advanced Encryption Standard,
to replace the existing DES, which is currently underway.
Types of Encryption Algorithms
Cryptographic algorithms can be broadly categorised as follows:
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 [Stal98], or
- 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 (and thus slow speed)
compared to private key schemes. Examples include: Diffie-Hellman, 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
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 (8-32) of some
simple, non-linear 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 encrypting bulk data, the ECB or CBC modes are used;
for stream data, the CFB or OFB modes.
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 several
brute force recoveries of 56-bit DES keys have been demonstrated using a
large distributed network of computers [RSAD97],
and using specialised hardware [EFF98a]. These
graphically illustrate the advances made in computational speeds in
recent years. In January this year (1999) a key was recovered in less
than 23 hours using the combined resources of both groups.
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 Triple-DES. 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 80's, several proposals were
published by the academic community. The best known of these include:
- a 64-bit, n-round (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.
- a 64-bit, 8 round iterated block cipher with a 128-bit 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. It is patented though and licensing may be needed.
- a 64-bit, 16 round, symmetric block cipher with a 64-bit key. It
was originally designed by Brown, Pieprzyk and Seberry in 1990
[BrPS90], and later re-designed (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 [BiSh93].
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 break-even 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,
In the light of this new (in the public community) knowledge, and
experience with the preceding ciphers, a number of others were
developed during the early 90's. The better known of these include:
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.
- a 64-bit, 16 round feistel block cipher with a variable length key,
designed by B. Schneier in 1994. It is optomised for bulk data
encryption (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.
- a 64-bit, 8 round feistel block cipher with a 64-bit 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), and may need to be licenced.
- 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
- a 64-bit, 6 or higher round, iterated block cipher with
64 or 128 bit keys, designed by J. Massey in 1994.
- a 128-bit, 8-round block cipher,
designed by Joan Daemen and Vincent Rijmen in 1997,
with emphasis on resistance against differential and linear cryptanalysis.
- a simple 64-bit, 32 round feistel block cipher with a 128-bit 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.
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.
As an illustration, a number of these algorithms have been implemented
in Java (using the Cryptix library [Cryp97]).
In one run, interpreted on a Pentium2/266 Linux 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 20506 409 79290
CAST5 23772 352 976
DES 48629 172 519
TripleDES 160807 52 1790
IDEA 43409 193 734
LOKI91 31071 269 76
RC2 43329 193 790
RC4 (*) 12945 648 2382
SAFER 41442 202 2219
Square 29610 283 2166
nb. (*) RC4 is stream cipher;
Choosing a Cipher
Selecting between the competing ciphers is not easy. Apart from slightly
different currently known security levels, questions of speed, code size,
and any patent or licencing issues need to be considered. As a general
rule, do rely on ciphers that are known, have been publicly analysed,
and in some use. Different applications are likely to require different
tradeoffs and hence choices.
Block Ciphers Future
Given the rapid advances in hardware speeds, and the development of
new cryptanalytic techniques, it has become clear that firstly the
DES must be replaced soon, and that a general increase in
the block and key sizes used, is needed. Thus the AES call.
Advanced Encryption Standard (AES)
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 Triple-DES," 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 royalty-free worldwide that is
capable of protecting sensitive government information well into the
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 Triple-DES, but with significantly improved efficiency.
Submissions were due by June 15, 1998. These submissions had 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 were reference implementations in Java (based on the Sun JCE 1.2
framework) and C, as well as extensive validation and test values.
NIST has planned for two phases of evaluation of the candidate algorithms.
During the first phase, NIST will evaluate the algorithms, including
using publicly submitted evaluations, and select a shortlist of at most 5.
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 non-classified evaluations of
the candidate algorithms.
Following the submission deadline, NIST reviewed all submissions for
compliance with the minimum requirements, and announced
at the First AES conference on 20-22nd August 1998,
that 15 algorithms had been accepted as complete and proper
for evaluation in phase 1. A further 6 algorithms were rejected as incomplete.
These algorithms are (as detailed at the AES web site
- CAST-256 - Adams (Entrust Tech., Canada)
- A 48-round unbalanced feistel cipher using the same round functions
as CAST-128, which use + - XOR rotates and 4 fixed 6-bit S-boxes;
with a key schedule also using an unbalanced feistel cipher
- CRYPTON - Lim (Future Systems, Korea)
- A 12-round iterative cipher with a round function
using & | XOR rotates and 2 fixed 8-bit S-boxes;
with various key lengths supported, derived from the previous SQUARE cipher
- DEAL - Knudsen (U. Bergen, Norway), Outerbridge (UK)
- A rather different proposal, a 6 to 8 round feistel cipher
which uses the existing DES as the round function.
Thus a lot of existing analysis can be leveraged, but at a cost
in speed [Knud98]
- DFC - Gilbert, Girault, Hoogvorst, Noilhan, Pornin, Poupard, Stern, Vaudenay (ENS, France)
- An 8-round feistel cipher designed based on a decorrelation technique
and using + x and a permutation in the round function;
with a 4-round key schedule [GGHN98].
- E2 - NTT, Japan
- A 12-round feistel cipher, using a non-linear function comprised of
substitution using a single fixed 8-bit S-box, a permutation,
XOR mixing operations, and a byte rotation
- FROG - Georgoudis, Leroux, Chaves (TecApro, South Africa)
- An 8-round cipher, with each round performing 4 basic operations
(with XOR, substitution using a single fixed 8-bit S-box,
and table value replacement)
on each byte of its input [GeLC98]
- Hasty Pudding - Schroeppel, Orman (U. Arizona, USA)
- An 8-round feistel cipher, which modifies 8 internal 64-bit variables
as well as the data using + - x & | XOR rotates and a lookup table
- LOKI97 - Brown, Pieprzyk (ADFA/UOW, Australia)
- A 16-round feistel cipher using a complex round function f
with two S-P layers with fixed 11-bit and 13-bit S-boxes, a permutation,
and + XOR combinations; and with a 256-bit key schedule using 48 rounds of
an unbalanced feistel network using the same complex round function f
- Magenta - Deutsche Telecom, Germany
- A 6 to 8 round feistel cipher, with a round function that uses a
large number of substitutions using a single fixed S-box (based on
exponentiation on GF(28)), which combined together with
key bits using XOR [JaHu98].
- MARS - IBM, USA
- A 8+16+8-round unbalanced feistel cipher with 4 distinct phases:
key addition and 8 rounds of unkeyed forward mixing,
8 rounds of keyed forwards transformation,
8 rounds of keyed backwards transformation,
and 8 rounds of unkeyed backwards mixing and keyed subtraction.
The rounds use + - x rotates XOR and 2 fixed 8-bit S-boxes
- RC6 - Rivest, Robshaw, Sidney, Yin (RSA Labs/MIT, USA)
- A 20-round iterative cipher, developed from RC5 (and fully parameterised),
which uses a number of 32-bit operations (+ - x XOR rotates)
to mix data in each round [RBSY98].
- RIJNDAEL - Daemen, Rijmen (Banksys/Katholieke Universiteit Leuven, Belgium)
- A 10 to 14-round iterative cipher, using byte substitution, row shifting,
column mixing and key addition, as well as an
initial and final round of key addition, derived from the previous SQUARE
- SAFER+ - Massey (Cylink, USA)
- An 8 to 16-round iterative cipher, derived from the earlier SAFER,
which uses + x XOR and 2 fixed 8-bit S-boxes
- SERPENT - Anderson (Cambridge, UK), Biham (Technion, Israel), Knudsen (U. Bergen, Norway)
- A 32-round feistel cipher, with key mixing using XOR and rotates,
substitutions using 8 key dependent 4-bit S-boxes,
and a linear transformation, in each round [AnBK98].
- TWOFISH - Schneier, Kelsey, Whiting, Wagner, Hall, Ferguson (Counterpane Systems, USA)
- A 16-round feistel cipher using 4 key dependent 8-bit S-boxes,
matrix transforms, rotations, and
based in part on Blowfish [SKWW98].
Some analysis on these algorithms has been announced, with more results
expected at the AES2 and FSE'99 conferences in March 99. To date,
significant problems have been found with DEAL, FROG, LOKI97, and MAGENTA,
as well as some minor caveats on DFC and MARS
(see [KnRi98] for references).
There is a spread of choice between those algorithms, contrasting those
with fewer complex rounds, verses many simple rounds; those using
conservative verses novel design approaches; and with small verses
large security margins (see [Biha98c]).
All of these choices are under debate at present.
I expect that at least some "big-name" submissions will likely make it through
the first cut at AES2, though its still not clear as to the selection.
Information on the progress with analysis can be found at the
US NIST AES web site [AES97],
and at the AES Block Cipher Lounge [KnRi98].
I do believe that if you are designing products which use cryptographic
algorithms, you certainly ought to be planning to incorporate the
final AES algorithm in your product. This requires planning for the
use of 128-bit data blocks, and one or more of 128, 192 or 256 bit keys.
There are significant speed differences between the candidate algorithms.
In part this reflects the different design choices, and there is some
debate that at least some of the conservatively designed algorithms
(esp. SERPENT) could afford to use fewer rounds to raise its speed.
[SKWW98b] reports that as currently designed,
the fasted algorithms on 32-bit CPU's are Twofish, Rijndael, Crypton,
RC6, Mars, Serpent & E2. If the rounds specified are "adjusted" for fair
speed/security (by some assumptions) then Serpent & Mars improve to 2nd &
3rd place. On other platforms & in hardware, these change somewhat.
The consequences are still being debated.
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.
Up to 56-bit block cipher keys are manifestly insecure for all but very
short period communications session security! Repeated demonstrations
have illustrated that 40-bit keys can be broken by brute-force in a
few hours or days by any group with access to a reasonable pool of
workstations (eg a few labs at the Uni). More recently, 56-bit DES
keys have been searched by a group who invested a moderate (US$250k)
amount in building dedicated hardware to search for any key in a day
or less [EFF98a]. It is clear, that as discussed
by a group of cryptographers in 96 [BDRS96],
key lengths should be 80 bits or more for moderate term security.
If smaller key size algorithms must be used, then great care is
needed in the system design to minimise and understand the risks.
To support wide-spread 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! As well,
suitable laws which recognise the validity of digital signatures
is required to provide business with legal guarantees for their use.
Lastly, 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 governments will address
the political issues and accept its necessity and need for unrestricted
This paper presents a brief survey of block ciphers, their past,
and their further development in response to the AES call.
Continuing changes and developments can be expected in the short term,
though the selection of a final AES algorithm should give some direction
in the medium term.
"Advanced Encryption Standard Call",
"The CAST-256 Encryption Algorithm",
Entrust Technologies, Canada, AES submission, Jun 1998.
Ross Anderson, Eli Biham, Lars Knudsen,
Cambridge UK, Technion Israel, U. Bergen Norway, AES submission, Jun 1998.
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",
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, Springer-Verlag, pp 36-50, 1991.
Also issued as ADFA TR CS38/91.
Eli Biham, Adi Shamir,
"Differential Cryptanalysis of the Data Encryption Standard",
Springer-Verlag, New York, 1993.
"New Types of Cryptanalytic Attacks Using Related Keys",
Journal of Cryptology, Vol 7, No 4, pp 229-246, 1994.
"Design Tradeoffs of the AES Candidates",
Lecture Notes in Computer Science, Springer-Verlag, 1998.
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, Springer-Verlag, pp 229-236, 1990.
Also issued as ADFA TR CS1/90.
Lawrie Brown, Josef Pieprzyk,
"Introducing the New LOKI97 Block Cipher",
Australian Defence Force Academy, Canberra, Australia, AES Submission, Jun 1998.
Ian Grigg, Raif Naffah,
"Cryptix Java Cryptographic Library",
Joan Daemen, Vincent Rijmen,
"AES Proposal: Rijndael",
Banksys/Katholieke Universiteit Leuven, Belgium, AES submission, Jun 1998.
Electronic Frontier Foundation,
Henri Gilbert, Marc Girault, Philippe Hoogvorst, Fabricc Noilhan, Thomas Pornin, Guillaume Poupard, Jacques Stern, Serge Vaudney,
"Decorrelated Fast Cipher: an AES Candidate",
Ecole Normale Supérieure, France, AES submission, Jun 1998.
Dianelos Georgoudis, Damian Leroux, Billy Simón Chaves,
"The "FROG" Encryption Algorithm",
TecApro Intl., South Africa, AES submission, Jun 1998.
Carolynn Burwick, Don Coppersmith, Edward D'Avignon, Rosario Gennaro, Shai Halevi, Charanjit Jutla, Stephen M. Matyas Jr., Luke O'Connor, Mohammad Peyravian, David Safford, Nevenko Zunic,
"MARS - a candidate cipher for AES",
IBM, USA, AES submission, Jun 1998.
M.J. Jacobson, K. Huber,
"The MAGENTA Block Cipher Algorithm",
Deutsche Telecom, Darmstadt, Germany, AES submission, Jun 1998.
Lars Knudsen, Vincent Rijmen,
"AES Block Cipher Lounge",
UiB, Norway, 1998.
"DEAL: A 128-bit Block Cipher",
University of Bergen, Norway, Technical Report, No 151, Feb 1998.
Chae Hoon Lim,
"CRYPTON : A new 128-bit block cipher",
Future Systems, Korea, AES submission, Jun 1998.
Cylink, USA, Jun 1998.
"Linear Cryptanalysis Method for DES Cipher",
in Advances in Cryptology - Eurocrypt'93,
Lecture Notes in Computer Science, Vol 765, Springer-Verlag, pp 386-397, 1993.
Kazumaro Aoki, Masayuki Kanda, Tsutomu Matsumoto, Shiho Moriai, Kazuo Ohta, Miyako Ookubo, Youichi Takashima, Hiroki Ueda,
"E2 - a 128-bit Block Cipher",
NTT, Japan, AES submission, Jun 1998.
R. Rivest, M.J.B. Robshaw, R. Sidney, Y.L. Yin,
"The RC6 Block Cipher",
RSA Labs/MIT, USA, AES submission, Jun 1998.
RSA Data Security Inc,
"Government encryption standard DES takes a fall",
Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson,
"Twofish: A 128-bit Block Cipher",
Counterpane Systems, USA, AES submission, Jun 1998.
B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall, N. Ferguson,
"Performance Comparison of the AES Submissions",
Counterpane Systems, Dec 1998.
Rich Schroeppel, Hilarie Orman,
"An Overview of the Hasty Pudding Cipher",
University of Arizona, Arizona, USA, AES submission, Jun 1998.
"Applied Cryptography - Protocols, Algorithms and Source Code in C",
2nd edn, John Wiley and Sons, New York, 1996.
"Cryptography and Network Security - Principles and Practice",
2nd edn, Prentice-Hall, 1998.
David J. Wheeler, Roger M. Needham,
"TEA, a Tiny Encryption Algorithm",
in Fast Software Encryption 2,
Lecture Notes in Computer Science, Vol 1008, Springer-Verlag, pp 363-366, 1994.
The latest version of this paper may be found at:
Last updated: 25 Feb 99.