A Current Perspective on Encryption Algorithms

Dr Lawrie Brown

School of Computer Science, Australian Defence Force Academy, Canberra, Australia

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: 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 [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 (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 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 56-bit 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 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 90's, several proposals were published by the academic community. The best known of these include:

FEAL: 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.
IDEA: 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.
LOKI91: 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 [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 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 presented. The better known of these include:

BLOWFISH: a 64-bit, 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 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).
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 64-bit, 6 or higher round, iterated block cipher with 64 or 128 bit keys, designed by J. Massey in 1994.
TEA: 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 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 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 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 non-classified 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].

[LOKI97 Overview] The proposed LOKI97 cipher is a 16 round Feistel cipher on 128-bit data using a complex non-linear function. It has a 256-bit key schedule which can be initialised using 128, 192, or 256-bit keys. The nonlinear function features a double layer of substitution-permutation 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 non-linear (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_i-1 xor g_i(K1_i-1,K3_i-1,K2_i-1)
K4_i = K3_i-1, K3_i = K2_i-1, K2_i = K1_i-1
g_i(K1,K3,K2) = f(K1+K3+(Delta*i),K2)
Delta = (sqrt(5)-1)*2⁶³

[LOKI97 Function f] In the data encryption computation, the 16 rounds (i=16,1) are as follows:

R_i-1 = L_i xor f(R_i-SK_3i,SK_3i-1)
L_i-1 = R_i-SK_3i-SK_3i-2

The non-linear 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.

40-bit block cipher keys are manifestly insecure! Repeated demonstrations have illustrated that they can be broken by brute-force 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 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!

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, Springer-Verlag, pp 36-50, 1991.
BiSh93: Eli Biham, Adi Shamir, "Differential Cryptanalysis of the Data Encryption Standard", Springer-Verlag, New York, 1993.
Biha94c: Eli Biham, "New Types of Cryptanalytic Attacks Using Related Keys", Journal of Cryptology, Vol 7, No 4, pp 229-246, 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, Springer-Verlag, pp 229-236, 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, Springer-Verlag, pp 386-397, 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", Prentice-Hall, 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, Springer-Verlag, pp 363-366, 1994. http://www.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.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.