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


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:
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
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 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 (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, LOKI91).

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:

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 engineering).
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.
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 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 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 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.

AES Evaluation

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.

AES Candidates

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 [AES97]):
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 [Adam98].
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 [Lim98].
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 [NTT98]
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 [ScOr98]
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 [BrPi98a]
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].
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 [IBM98].
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 cipher [DaRi98].
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 [Mass98].
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.

Comparative Speeds

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.

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.

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 use.


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.


NIST, "Advanced Encryption Standard Call", NIST, 1997. http://www.nist.gov/aes/.
Carlisle Adams, "The CAST-256 Encryption Algorithm", Entrust Technologies, Canada, AES submission, Jun 1998. http://www.entrust.com/resources/pdf/cast-256.pdf.
Ross Anderson, Eli Biham, Lars Knudsen, "SERPENT", Cambridge UK, Technion Israel, U. Bergen Norway, AES submission, Jun 1998. http://www.cl.cam.ac.uk/ftp/users/rja14/serpent.pdf.
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.
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.
Eli Biham, "New Types of Cryptanalytic Attacks Using Related Keys", Journal of Cryptology, Vol 7, No 4, pp 229-246, 1994.
E. Biham, "Design Tradeoffs of the AES Candidates", in Asiacrypt'98, 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. http://lpb.canb.auug.org.au/adfa/research/loki97/.
Ian Grigg, Raif Naffah, "Cryptix Java Cryptographic Library", 1997. http://www.systemics.com/docs/cryptix/.
Joan Daemen, Vincent Rijmen, "AES Proposal: Rijndael", Banksys/Katholieke Universiteit Leuven, Belgium, AES submission, Jun 1998. http://www.esat.kuleuven.ac.be/~rijmen/rijndael/.
Electronic Frontier Foundation, "Cracking DES", O'Reilly, 1998. 1-56592-520-3. http://www.oreilly.com/catalog/crackdes/.
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. http://www.dmi.ens.fr/~vaudenay/dfc.html.
Dianelos Georgoudis, Damian Leroux, Billy Simón Chaves, "The "FROG" Encryption Algorithm", TecApro Intl., South Africa, AES submission, Jun 1998. http://www.tecapro.com/aesfrog.htm.
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. http://www.research.ibm.com/security/mars.html.
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. http://www.ii.uib.no/~larsr/aes.html.
Lars Knudsen, "DEAL: A 128-bit Block Cipher", University of Bergen, Norway, Technical Report, No 151, Feb 1998. http://www.ii.uib.no/~larsr/newblock.html.
Chae Hoon Lim, "CRYPTON : A new 128-bit block cipher", Future Systems, Korea, AES submission, Jun 1998. http://crypt.future.co.kr/~chlim/crypton.html.
James Massey, "SAFER+", Cylink, USA, Jun 1998. http://www.cylink.com/SAFER.
Mitsuru Matsui, "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. http://info.isl.ntt.co.jp/e2/.
R. Rivest, M.J.B. Robshaw, R. Sidney, Y.L. Yin, "The RC6 Block Cipher", RSA Labs/MIT, USA, AES submission, Jun 1998. http://theory.lcs.mit.edu/~rivest/rc6.pdf.
RSA Data Security Inc, "Government encryption standard DES takes a fall", 1997. http://www.rsa.com/des/.
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. http://www.counterpane.com/twofish.html.
B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall, N. Ferguson, "Performance Comparison of the AES Submissions", Counterpane Systems, Dec 1998. http://www.counterpane.com/AES-performance.html.
Rich Schroeppel, Hilarie Orman, "An Overview of the Hasty Pudding Cipher", University of Arizona, Arizona, USA, AES submission, Jun 1998. http://www.cs.arizona.edu/~rcs/hpc/.
Bruce Schneier, "Applied Cryptography - Protocols, Algorithms and Source Code in C", 2nd edn, John Wiley and Sons, New York, 1996.
W. Stallings, "Cryptography and Network Security - Principles and Practice", 2nd edn, Prentice-Hall, 1998. http://www.shore.net/~ws/Security.html.
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. http://www.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html.

The latest version of this paper may be found at: http://lpb.canb.auug.org.au/adfa/papers/unz99.html.
Last updated: 25 Feb 99.