Cryptography was once the domain of generals and curious children, but the advent of the Information Age changed that. In the early 1970s the National Security Agency (NSA) and the National Bureau of Standards (NBS) realized that non-combatant adults needed to protect their sensitive, but unclassified, information. Though NSA is the usual government agency for building cryptosystems, the agency was unwilling to design a cryptosystem for public use. Instead NBS issued a public solicitation for a cryptosystem. IBM responded. The company submitted a cryptosystem with a 56-bit key. The new algorithm became the Data Encryption Standard (DES).
Many in industry and academia were skeptical of DES. Concern centered on whether NSA had placed a trapdoor, a shortcut to decryption, in the algorithm. There were also objections to DES’s key length; critics believed the relatively short key length1 had been chosen so that NSA could read DES-encrypted traffic. (IBM said its own engineers had insisted on parity bits for the register-to-register transfer of key data, thus decreasing the key length to 56 from the original 64.)
During the next two decades there were frequent battles over cryptography. Using export controls and threats of other legal action, the U.S. government attempted to stop the spread of strong cryptography. Seeking to build secure computer systems, industry found export controls on cryptography to be a serious blockage (though, to be sure, not the only one). [4]
Industry battles centered on bits: how many would the government allow in exported products? Under a 1992 agreement, the magic number was 40 bits. DES is 56 bits. With narrow exceptions, products incorporating DES could not be exported. A 1996 National Research Council report on cryptography policy recommended an immediate loosening of export controls. No changes occurred until 1998, when a $250,000 special-purpose machine built by the Electronic Frontier Foundation cracked a DES-encrypted message in 56 hours [5]. (This has since been improved to 22 hours through a combination of 100,000 networked PCs and the EFF machine.) At that point, U.S. export controls were relaxed to permit DES in exported products. In recent months export controls have been further eased.
A New Standard
A DES replacement was overdue. In 1997 the National Institute of Standards and Technology (NIST) announced a competition for the algorithm’s replacement, and held public meetings to discuss the criteria for a proposed Advanced Encryption Standard (AES). Key length was most important. A 1996 ad hoc committee had argued 90 bits was currently the minimum key length needed to provide data security for 20 years [1]. NIST sought that much security and more—encrypted files should remain confidential well after AES was retired. NIST settled on a minimum key length of 128 bits.2
Given the government’s intransigence over exporting strong cryptography, initial reaction was mistrustful. One concern was the role of the NSA in the process. Another was foreign participation; after all, cryptanalysis expertise is international. Both concerns seem to have been allayed. While NSA is—appropriately enough—studying the candidates, there have been no complaints about its part in NIST’s evaluation. And NIST allowed foreign participation in the AES competition.
After public input, NIST settled on straight forward requirements: the algorithm must implement symmetric (secret) key cryptography, the algorithm must be a block cipher, and the algorithm must work on 128-bit blocks and with three key sizes: 128, 192, and 256 bits. If selected, candidates would have to be available worldwide on a nonexclusive, royalty-free basis. Evaluations would be on security, cost, and implementation flexibility. As simplicity aids in understanding, implementing, and assessing the security of the candidates, design simplicity would count. The winner should work in a variety of venues, including 8-bit processors, smartcards, ATM networks, HDTV, voice, and satellite communications. A year into the evaluation procedure, NIST would determine five finalists, a year later, the winner (or winners—NIST might pick more than one). NIST’s biggest challenge was determining the candidates’ strength. Cryptanalysis is a young science without an overarching theory. Certifying a 128-bit symmetric key algorithm is a voyage into the unknown. NIST could use mathematical arguments and various measures (for example, how much a candidate’s output was indistinguishable from a random permutation) to establish an algorithm’s security. But such approaches are only as strong as the imagined attack model. At the end one is left with statements of the form: “We tried, and algorithm X could not be attacked by methods D, L, or S.” Such an approach does not inspire confidence.
If an algorithm uses a k-bit key, the measure of security is how close the algorithm is to being 2k-secure, that is, whether there are significantly better methods for breaking the system than a brute-force search of the entire key space. (An assumption, first codified by Kerckhoffs in the 18th century, holds that security of a cryptosystem should rest entirely in the secrecy of the key, and not in the secrecy of the algorithm.) Sometimes an algorithm’s weakness is readily apparent, but frequently weaknesses may take years to discover. With DES, one strong form of attack—differential cryptanalysis—had apparently been known to the algorithm’s designers, but linear cryptanalysis, discovered in 1993, seems to be new. DES was indeed at least theoretically vulnerable to this type of attack.
Cryptosystem Design
The simplest techniques for encrypting a block of symbols are substitution and transposition. Substitution replaces a symbol by another; transposition permutes the symbols of a block around. Cryptanalysis can be viewed as trying to determine the plaintext by approximating the encryption function. Viewed this way, linear functions of the input and key are poor design choices; such functions can be easily solved. Thus nonlinear functions form the basis of cryptographic design. But cryptographic functions must be invertible, fast to compute, and should have small key size and memory requirements. So linear functions end up playing an essential role. A proper combination of simple operations such as XOR (exclusive or addition modulo 2, sometimes written as
), substitution, and permutation, produces a cryptosystem whose strength is greater than the sum of its parts.
These operations are all that is behind DES, which is an iterated block cipher, a cryptosystem on a block of symbols that sequentially repeats an internal function, called a round. It is currently customary to encrypt data using a primitive that operates on a block of symbols of moderate size. Although there are non-iterative block ciphers (RSA), iteration is a natural way to procede because that yields a small object (this is useful in hardware) with good complexity.
Some version of self invertibility is also useful. This enables one object (a chip, a piece of software) to both encrypt and decrypt. Feistel ciphers, in which the 2tbit input is split into t-bit halves L0, R0 and mapped after r rounds to Lr, Rr, succinctly accomplish this. In the ith round, the right half of the previous round becomes the new left half, Li ← Ri1, while the new right half Ri is a function of a round subkey Ki (derived from the key K), and both halves from the previous round, Ri ← Li1
(Ri1, Ki ) where
is an arbitrary function. Decryption is the algorithm run in reverse, with subkeys used in the opposite order. DES is a 16-round Feistel cipher.
One school of thought in cryptosystem design lets technology strongly guide the choice of operations, thereby obtaining algorithmic complexity with high-speed performance. NSA takes a different tack. Any widely deployed system will be implemented across a variety of hardware and software systems, so the agency believes in “keep it simple,” and prefers to use elementary primitives such as XOR and table look-up. As opposed to more complex operations such as floating-point arithmetic, these functions act the same way regardless of system architecture. There are countless other tradeoffs, with perhaps the most fundamental being between those algorithms that are simpler to verify, and those that are more complex but more difficult to verify. In a block-structured cryptosystem, this particular issue plays out on the question of rounds: should there be many simple rounds or fewer, more complex ones? Even relatively simple cryptosystems can be secure when run for 32 rounds.
System designers typically begin with a set of capabilities (this may be the architectures or processors on which the algorithm will run) and a set of performance constraints. While cryptosystem design should be a standardized procedure in much the way that bridge building is, the fact is bridge building is much better understood. The purpose of a cryptosystem is to make decryption of messages extremely difficult without the key. The design of a cryptosystem has a dual objective: ensure cryptanalysis is difficult while enabling certification of the algorithm’s security. The complexity of the two tasks and a lack of knowledge about how to achieve the second generally results in cryptosystems being designed with cryptanalysis well in mind, system certifiability much less so.
Some rules of thumb are standard. No output bit should be a linear function of the input bits; indeed, no linear function of the output bits should be a linear function of the input bits [3]. This does not mean that linear functions cannot be part of a cryptosystem, but that the system must include nonlinearity. In block-structured algorithms nonlinearity is frequently achieved by using look-up tables called S-boxes (for substitution boxes).
Cryptanalytic Attacks
The most serious attacks on block-structured algorithms to date are differential and linear cryptanalysis. Differential cryptanalysis, first reported publicly by Israeli researchers Eli Biham and Adi Shamir, is a chosen-plaintext attack that relies on the idea that a fixed input difference may, with high probability, generate a particular output difference. By encrypting pairs of plaintexts X, X‘ with prescribed bitwise difference DX = X
X‘, and seeing which key bits are “suggested” by the output difference, key bits are determined.
Linear cryptanalysis, discovered by Japanese cryptographer Mitsuru Matsui, works by finding linear relationships between plaintext, ciphertext, and key bits that reveal information about the key.
Let B[i] denote the ith bit of an array B, and B[i1, i2, …, ik] = B[i1]
B[i2]
…
B[ik], and P, C and K be the plaintext, ciphertext, and key respectively. Fundamentally one is seeking relationships of the form: P[i1, i2, …, ia]
C[j1, j2,… jb] = K[k1, k2, …, kc].
In the case of DES, both differential and linear cryptanalysis are theoretical rather than practical attacks. Yet these are very powerful cryptanalytic techniques that cannot be ignored.
No mathematical theory accounts for attacks that are “out of the box.” Paul Kocher successfully broke a number of secure algorithms using timing and power-analysis attacks. Using a known-ciphertext attack, Kocher timed decryption to determine which operations were being used. This revealed which decryption key bits were a “1.” Using this approach, Kocher found the exponents used in the Diffie-Hellman key-exchange algorithm and factored the modulus used for the RSA algorithm [6]. Power-analysis attacks rely on the remarkably effective observation that the power consumed during encryption and decryption depends on the operation being performed and the data being processed [7]. Kocher’s attacks, which rely on the physical aspects of the implementation, had not been part of any model previous considered by cryptographers.
The AES Candidates
AES candidates were due June, 15, 1998. Of the 21 submitted, 15 met NIST’s criteria: LOKI97 (Australia), Rijndael (Belgium), CAST-256 and DEAL (Canada), FROG (Costa Rica), DFC (France), Magenta (Germany), E2 (Japan), CRYPTON (Korea), Hasty Pudding Cipher (U.S.), MARS, RC6, SAFER+ and Twofish (U.S.), and Serpent (U.K., Israel, Norway).3 In August 1999, NIST announced the five finalists: MARS, RC6, Rijndael, Serpent, and Twofish. These were widely accepted—along with some support for E2—as the “best” submissions, and NIST reported that NSA called these “appropriate choices.” The winner—or winners—will be determined this summer.
For the winners, different cooks added their own ingredients to the cryptographic brew. The five finalists, for example, include an “extended” Feistel network (MARS), two standard Feistel networks (RC6, Twofish), a substitution-permutation network (Serpent), and an algorithm that relies on finite field operations to construct the S-box (Rijndael). MARS and RC6 use multiplication to perform diffusion, but MARS multiplies key words by data words, while RC6 multiplies words that are a combination of key and data. Twofish uses “key-dependent” S-boxes that are constructed on the fly. In any given round, Serpent implements one S-box in parallel—32 copies of it. No other finalist (or candidate) does that.
The AES Finalists
I will briefly describe each of the finalists, explaining the design principles behind them. Full descriptions, including implementation details, are available at the NIST Web site (aes.nist.gov).
In MARS, IBM designers use the well-established Feistel network, the reasonable idea that multiplication provides good diffusion properties, the fact that all modern processors support multiplication of 32-bit numbers, and their intuition that an algorithm in which the top and bottom rounds of a cipher employ different functions than the middle ones is better resistant to differential and linear cryptanalysis.
Symmetry in a cryptosystem (symmetry within a round function, the same round functions at the beginning and end of the algorithm), simplifies the system’s architecture and its security analysis. But to thwart various types of attacks, MARS designers chose to make their algorithm asymmetric; the last eight rounds of MARS process words in a different order than the first eight. And the central 16 rounds—the core—are different from the first and last eight mixing rounds. MARS’s S-boxes were built using SHA-1 (SHA-1, the Secure Hash Algorithm, is a Federal Information Processing Standard) applied to some fixed constants, specifically, expansions of the fractional parts of
and p. (To assure users the algorithm has no trapdoors, algorithm designers are careful to explain their choice of fixed parameters.)
The mixing rounds employ
, rotation, and addition, while the core uses
, multiplication, data-dependent rotations, and S-box lookup. Both the mixing and core rounds of MARS are complex, and the algorithm’s key schedule is also intricate. NIST commented that MARS’s “complexity makes analysis difficult in a restricted timeframe” [8]. This complexity may work against MARS being chosen as an AES.
RC6, a 20-round Feistel cipher out of RSA Security, is much simpler. RC6 operates on four registers (A, B, C, D) of 32-bit words. RC6 treats the four words in pairs, (A, B), (C, D), and permutes the pairs in the last step of each round (A, B, C, D) ← (B, C, D, A), thus mixing them:
- B = B + K0
- D = D + K1
- for i = 1 to r do :
- t = (B × (2B + 1)) <<< 5
- u = (D × (2D + 1)) <<< 5
- A = ((A
t) <<< u) + K2i
- C = ((C
u) <<< t) + K2i+1
- (A, B, C, D) = (B, C, D, A)
where a <<< b, a “data-dependent” rotation, means rotate the w-bit word a to the left by the amount given by the least significant log w bits of b, and the Ki‘s are round subkeys. (Although at first RC6 does not appear to be a Feistel cipher, during a round the only action on blocks B and D are rotations to blocks A and C. Thus one can model L = (B, D), R = (A, C) and RC6 is a standard Feistel network.) Aside from pre-whitening and post-whitening steps. Whitening is simple: XOR key material with the input (or output) to a block algorithm. This is to prevent attackers from acquiring plaintext/ciphertext pairs.
RC6’s key schedule is simple. RC6’s strength lies in the resistance to differential and linear cryptanalysis provided by the data-dependent rotations and in the diffusion provided by the quadratic function
(x) = x(2x+1).
Twofish, proposed by Counterpane Systems, a U.S.-based cryptographic consulting firm, is a 16-round Feistel network with two modifications. One is a one-bit rotation before and after the data enters the round function proper. The other alteration is key-based S-boxes. Twofish’s designers believe dynamically varying S-boxes enhance security.
Key-dependent S-boxes are unusual. While randomly constructed S-boxes are vulnerable to differential-cryptanalysis attacks, DES’s S-boxes were explicitly constructed to resist differential cryptanalysis. In any particular instantiation of Twofish, some key-dependent S-boxes may be weak, but the fact that the S-boxes are dynamically constructed complicates differential and linear cryptanalysis attacks. The four S-boxes are distinct and are constructed from permutations that satisfy good differential and linear properties.
The S-box operation is followed by matrix multiplication, addition modulo 232, and addition of key bits. Bit rotations are put in to thwart an attack that relies on the byte alignment of the S-boxes and matrix multiplications. Matrix multiplication diffuses bits. And addition mod 232 provides further mixing. Twofish’s key schedule is relatively straightforward. But NIST warned that Twofish’s overall complexity “has drawn some concern” (see [8], p. 53).
Serpent, created by three cryptographers from the U.K., Israel, and Denmark, is a conservative design. There are 32 rounds—a high number—each of which consists of XORing the key and the intermediate data, a pass through S-boxes, and a linear function that combines fixed rotations and XOR (in the last round, the linear function is replaced by a key-mixing operation). While the rules used to generate the linear transformation appear ad hoc (a <<< 7 here, an
there), they function as advertised: the linear transformation increases avalanche. After three rounds, each plaintext bit affects all data bits.
Each round of Serpent has 32 identical S-boxes (each 4-bit to 4-bit) applied in parallel. And herein lies the cleverness of Serpent. The bits are operated upon independently, and a 32-bit processor neatly works on the 128-bit data segment. The fact that each round uses 32 identical S-boxes means the action of the S-boxes on bits 0, 1, 2, 3 is identical to the action on bits 4, 5, 6, 7; bits 8, 9, 10, 11; and so forth. So bits 0, 1, 2, 3 are fed to the first input of the processor and operated upon through a series of Boolean operations, while simultaneously bits 4, 5, 6, 7 are fed to the second input of the processor and operated upon by the same set of operations, and so forth. The result is bits 0, 4, …, 124 of the output. Now the processor can compute the next set of outputs. The inputs have already been fed in. Again, since the S-boxes are replicated, the same operation is done on all 32 bits of the processor. The outputs are bits 1, 5, …, 125 of the output. This process is repeated twice more, and thus all 128 bits of output are computed. This is followed by the linear transformation that diffuses the results of the bits. During these operations, the processor is used to its fullest.
The S-boxes are created from DES’s via a simple program, and Serpent’s key schedule is simple. The algorithm’s security is based on high number of rounds, which provides strong resistance to differential and linear cryptanalysis.
Rijndael, developed by two Belgian cryptographers, relies more directly on algebraic constructs than the other algorithms. Let GF(28) be the finite field defined by the irreducible polynomial x8+ x4+x3+ x +1 over GF(2); view the 128 bits = 16 bytes as elements of the field. The data is placed in a 4 × 4 array of elements of GF(28).
Rijndael has 10 rounds, each consisting of four operations: ByteSub, ShiftRow, MixColumn, and AddRoundKey (the last round skips the MixColumn operation). ByteSub, the S-box operation, views individual bytes as elements of GF(28), and first inverts them (0 is sent to 0), and then maps the elements via an affine function. ByteSub operations were chosen for their resistance to differential and linear cryptanalysis. ShiftRow cyclicly shifts the elements of the ith row of the array i elements to the right, while MixColumn diffuses the bits of a column by viewing the elements of the column as coefficients of a polynomial and performing a polynomial multiplication. Finally RoundKey XORs the key with the array elements. The key schedule for Rijndael is a simple expansion using XOR and cyclic shift.
Determining the Winner(s)
The finalists have varying strengths and weaknesses. RC6 and Rijndael have simple definitions; MARS and, to a lesser extent, Twofish have designs that complicate analysis. Serpent is slow on virtually all platforms, but the algorithm has a large “security margin” (a high number of rounds relative to differential and linear attacks that are successful on reduced-round versions of the algorithm). RC6 has a low security margin, MARS, a large one.
The successful candidates are not perfect. All have serious problems in smart cards, where the attacker has limited access to the card’s performance while encrypting. Their use of multiplication and rotation makes MARS and RC6 vulnerable to timing attacks. So is Twofish, although less so. But a differential power-analysis attack exhibited far more serious problems. Taking power samples of the whitening process from 100 independent block encryptions, a rogue smart-card implementation leaked all 128 bits of Twofish’s key [2]. This was not due to a peculiarity of Twofish—all the round-one AES candidates were equally vulnerable to this attack. There are ways around such penetrabilities, but these come at a cost of time and space, neither of which is in great supply in smart cards. Perhaps smart cards are not an appropriate venue for the same algorithm expected to secure international ecommerce. A special-purpose algorithm might serve better.
When NBS put forth DES in 1975 the electronic world was in a fledgling state. Few anticipated the phenomenal growth of the Internet and e-commerce. AES is an ambitious undertaking. It is only two decades since public work on cryptography numbered more than a handful of researchers.4 NIST’s venture is predicated on the idea that in the more than 20 years since the sanctification of DES and the birth of public-key cryptography, cryptographic expertise outside the spy agencies has grown to the point that an algorithm to protect international commerce and communications can be developed by the public sector. AES is an interesting experiment—and a strong endorsement of the public expertise that has developed in so brief a time.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment