eWEEK content and product recommendations are editorially independent. We may make money when you click on links to our partners. Learn More.
Though its a hot topic now, the need to encrypt data stored on tapes and hard drives, or transmitted across a network, is far from new.
DES (data encryption standard), the most widely used encryption algorithm in the world, for example, is more than 28 years old.
DES became the bedrock of government cryptology until, in October 2000, it was replaced by the AES (advanced encryption standard), an algorithm much harder to break even with the hardware that advanced enough over the course of nearly three decades, to finally crack DES.
Here well take a look at the migration from DES to AES, especially how DES was supplanted by an algorithm called Rijndael.
DES: The first steps
On May 15, 1973, the NBS (National Bureau of Standards), looking for a cryptographic algorithm strong enough to protect data during transmission and storage, published a notice in the Federal Register asking for proposals from individuals or corporations.
The eventual leader of the ensuing competition was an algorithm developed at IBM that carried the code-name LUCIFER.
After evaluating the algorithm with the “guidance” of the NSA (National Security Agency), the NBS adopted a modification of the LUCIFER algorithm as the new DES on July 15, 1977.
This led to the creation of FIPS 46 (Federal Information Processing Standard) (since updated to FIPS 46-3), which describes the use of DES and the current DES 3 standard.
Not surprisingly, the banking industry became the largest user of encryption outside government.
All of the EFTs (electronic funds transfers) and ATMs (automated teller machines) that use ordinary telephone lines to conduct their business must encrypt the financial data for a semblance of security.
Standards for the wholesale banking industry were set by the ANSI (American National Standards Institute). ANSI X3.92, adopted in 1980, specified the use of the DES algorithm. ATMs use it routinely even today.
How DES works: The gory details
DES works by encrypting groups of 64 message bits, which is the same as 16 hexadecimal numbers. To do the encryption, DES uses “keys” that are notationally 16 hexadecimal numbers long which equals 64 bits.
However, for some reason (possibly due to the “guidance” given to the NBS by NSA) every 8th key bit is ignored in the DES algorithm. This makes the true key size 56 bits.
The resistance to a “forced” or “brute” attack of a encoding system is directly related to its keyspace; or how many possible keys there are to the system.
The more bits used, the more keys are possible. More keys means it takes longer to compute the entire range of possible keys of the keyspace in a forced attack.
Cut eight bits off the top and you reduce the keyspace significantly, making the system easier to crack.
DES is a block cipher, meaning it operates on plain text blocks of a given size (nominally 64 bits) and returns ciphertext blocks of the same size.
So, DES results in a permutation among the 2 to the 64th power possible arrangements of 64 bits, each of which may be either 0 or 1.
Each block of 64 bits is divided into two blocks of 32 bits each, a left half block L and a right half R.
The DES algorithm uses the following steps, which were well-explained by J. Orlin Grabbe in his article The DES Algorithm Illustrated (Laissez Faire City Times, Vol 2, No. 28).
Heres How it Works
Heres how the math works, step by step:
- Step 1: Create 16 subkeys, each of which is 48-bits long.
The 64-bit key is permuted according to a specified order or “table.” If first entry in the table is “27”, this means that the 27th bit of the original key K becomes the first bit of the permuted key K+.
If the tables second entry was 36, then the 36th bit of the original key becomes the second bit of the permuted key, and so on. Note that only 56 bits of the original key appear in the permuted key.
Next, split this key into left and right halves, C0 and D0, where each half has 28 bits. With C0 and D0 defined, we now create sixteen blocks Cn and Dn, 1<=n<=16.
Each pair of blocks Cn and Dn is formed from the previous pair Cn-1 and Dn-1, respectively, for n=1, 2, …, 16 by using a table identifying of “left shifts” that say which bit is operated upon.
In all cases, by a single left shift is meant a rotation of the bits one place to the left. After one left shift the bits in the 28 positions are the bits that were previously in positions 2, 3, and so on up to bit 28.
Form the keys Kn, for 1<=n<=16, by applying another permutation table to each of the concatenated pairs CnDn. Each pair has 56 bits, but the table only uses 48 of these, because every 8th bit is ignored.
- Step 2: Encode each 64-bit block of data.
There is an initial permutation IP of the 64 bits of the message data M. This rearranges the bits according to the permutation table, where the entries in the table show the new arrangement of the bits from their initial order.
Proceed through 16 iterations, for 1<=n<=16, using a function f which operates on two blocks—a data block of 32 bits and a key Kn of 48 bits—to produce a block of 32 bits.
Let + denote XOR addition, (bit-by-bit addition modulo 2). Then for n going from 1 to 16 we calculate Ln=Rn-1 Rn=Ln-1 + f(Rn-1,Kn).
That is, in each iteration, we take the right 32 bits of the previous result and make them the left 32 bits of the current step. For the right 32 bits in the current step, we XOR the left 32 bits of the previous step with the calculation F.
To calculate F, we first expand each block Rn-1 from 32 bits to 48 bits. This is done by using a selection table that repeats some of the bits in Rn-1.
The use of this selection table becomes the function F. So, F(Rn-1) has a 32 bit input block, and a 48 bit output block. Let F be such that the 48 bits of its output, written as 8 blocks of 6 bits each, are obtained by selecting the bits in its inputs in order according to a known table.
We have expanded Rn-1 from 32 bits to 48 bits, using the selection table, and XORed the result with the key Kn.
There are now 48 bits, or eight groups of six bits. Each group of six bits now undergoes a transformation that is central to the algorithm: we use them as addresses in tables called “S boxes.”
Each group of six bits gives us an address in a different S box. Located at that address will be a 4-bit number which replaces the original 6 bits. The net result is that the eight groups of 6 bits are transformed into eight groups of 4 bits (the 4-bit outputs from the S boxes) for 32 bits total.
The final stage in the calculation of F is to do a permutation P of the S-box output to obtain the final value of F. F is of the form F=P(S1(B1)S2(B2)…S8(B8)).
The permutation P yields a 32-bit output from a 32-bit input by permuting the bits of the input block.
Decryption is simply the inverse of encryption, following the same steps as above, but reversing the order in which the subkeys are applied.
Triple DES (DES 3 in government-speak) is just DES done three times with two keys used in a particular order. Triple-DES can also be done with three separate keys instead of only two. The number of possible keys in DES 3 is 2^112, compared to 2^56 possible keys for DES
The Advanced Encryption Standard effort
It was obvious to crypto specialists in government as far back as 1993 that DES security was going to be compromised at some point.
Even assuming the NSA had a backdoor built into DES to allow routing decryption of messages—as Diffie and Hellman, who discovered the beauty of public-key cryptography, seem to have alleged in a 1975 letter to the NSA)—DES was starting to get long in the tooth.
It wasnt that efficient a way to do things. It couldnt work well on hardware “smart cards” that were starting to show up. But it took until 1997 for the NIST (National Institute of Science and Technology) to start looking for its successor under the banner of the AES project.
Next page: The Advantages of AES
The Advantages of AES
In documents coming out of an April 1997 AES Workshop, NIST listed these goals for AES:
- It should provide a strong cryptoalgorithm for government and commercial use.
- It should support Standard Codebook Modes. (Note: The DES algorithm turns a message block into a cipher block. If each block is encrypted individually, the mode of encryption is called Electronic Code Book (ECB) mode. There are two other modes of DES encryption, namely Chain Block Coding (CBC) and Cipher Feedback (CFB), which make each cipher block dependent on all the previous messages blocks through an initial XOR operation. Since each mode was in governmental/banking use, compatibility in how AES would handle information was desired.)
- It should be significantly more efficient than DES 3
- It should have a variable key size so that security could be increased when needed
- It should be selected in a fair and open manner
- It should be evaluable by (sufficiently expert) members of the public.
Candidates were judged not only on how well they encrypted, but also how well they could be used in widely varying environments.
Candidates were judged by the following criteria:
A.1 AES shall be publicly defined.
A.2 AES shall be a symmetric block cipher.
A.3 AES shall be designed so that the key length may be increased as needed.
A.4 AES shall be implementable in both hardware and software.
A.5 AES shall either be a) freely available or b) available under terms consistent with the American National Standards Institute (ANSI) patent policy. (Note: This meant that royalty-encumbered algorithms—the ones that would fall under ANSI policy—would also be considered . This was dropped, thereby making sure a non-encumbered (i.e., patent-free) algorithm would be the only one selectable)
A.6 Algorithms which meet the above requirements will be judged based on the following factors:
a) security (i.e., the effort required to cryptanalyze),
b) computational efficiency,
c) memory requirements,
d) hardware and software suitability,
e) simplicity,
f) flexibility, and
g) licensing requirements
(Note: see A5 above)
Rijndael: The AES algorithm winner
In October 2000 NIST selected Rijndael as the AES algorithm. This does not replace DES 3—yet—as the way the government encrypts routinely because it still has to go through a vetting process where the “stakeholders” express their views. But it sure greases its path to do so. Rijndael is an iterated block cipher with a variable block length and a variable key length. The block length and the key length can be independently specified to 128, 192 or 256 bits.
Several operations in Rijndael (pronounce it “rain doll” in English) are defined at byte level, with bytes representing elements in the finite field GF(2^8), which is representative of the 8 bits in a byte. Other operations are defined in terms of 4-byte words.
Addition , as usual, corresponds with the simple bitwise EXOR at the byte level.
In the polynomial representation, multiplication in GF(2^8) corresponds with multiplication of polynomials modulo an irreducible binary polynomial of degree 8. (A polynomial is irreducible if it has no divisors other than 1 and itself.) For Rijndael, this polynomial is called m( x ) and given by: m( x ) = (x^8 + x^4 + x^3+ x + 1) or 11B in hexadecimal representation. The result will be a binary polynomial of degree below 8. Unlike addition, there is no simple operation at the byte level.
Next page: A Better Round Transformation
A Better Round Transformation
Down with the Feistel Structure!
In most ciphers, the round transformation has the well-known Feistel Structure. In this structure typically part of the bits of the intermediate state are simply transposed unchanged to another position. (Those tables we discussed back in the part about DES that substitute bits by a fixed tabular means are an example of this linear kind of structure.) The round transformation of Rijndael does not have this venerable Feistel structure, in which half the data block is used to modify the other, the two change places.
Instead, the round transformation is composed of three distinct invertible uniform transformations, called layers. (Uniform means here that every bit of the state is treated in a similar way.)
The linear mixing layer guarantees high diffusion over multiple rounds. The non-linear layer uses parallel application of S-boxes that have the desired (hence, optimum) worst-case nonlinearity properties. The S-boxes are non-linear. Thats the key conceptual difference between DES and Rijndael. The key addition layer is a simple EXOR of the Round Key to the intermediate State, as is noted below.
The round transformation is composed of four different transformations.
In pseudo C notation they are:
Round(State,RoundKey)
{ ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State,RoundKey);
(EXORing a Round Key to the State) }
The final round of the cipher is slightly different. It is defined by: FinalRound(State,RoundKey)
{ ByteSub(State) ;
ShiftRow(State) ;
AddRoundKey(State,RoundKey);
}
In this notation, the “functions” (Round, ByteSub, ShiftRow, …) operate on arrays to which pointers (State, RoundKey) are provided. The ByteSub Transformation is a non-linear byte substitution, operating on each of the State bytes independently. In ShiftRow, the rows of the State are cyclically shifted over different offsets. In MixColumn, the columns of the State are considered as polynomials over GF(2^8) and multiplied modulo x^4 + 1 with a fixed polynomial c( x ), given by c( x ) = 03 x^3 + 01 x^2+ 01 x + 02. This polynomial is coprime to x^4 + 1 and therefore invertible.
The Round Keys are derived from the Cipher Key by means of the key schedule. This has two components: the Key Expansion and the Round Key Selection. The total number of Round Key bits is equal to the block length multiplied by the number of rounds plus 1. (e.g., for a block length of 128 bits and 10 rounds, 1408 Round Key bits are needed).
The Cipher Key is expanded into an Expanded Key. Round Keys are taken from this Expanded Key in the following way: the first Round Key consists of the first Nb (Nb = block length ) words, the second one of the following Nb words, and so on.
The cipher consists of: an initial Round Key addition, Nr-1 Rounds, a final round.
In pseudo C code:
Rijndael(State,CipherKey)
{ KeyExpansion(CipherKey,ExpandedKey) ;
AddRoundKey(State,ExpandedKey);
For( i=1 ; i
FinalRound(State,ExpandedKey + Nb*Nr);
}
If the key expansion is done beforehand the cipher can be specified in terms of the Expanded Key.
Rijndael(State,ExpandedKey)
{ AddRoundKey(State,ExpandedKey);
For( i=1 ; i
FinalRound(State,ExpandedKey + Nb*Nr);
}
Since Rijndael is invertible, the deciphering process just reverses the steps described above. Technical details can be found in the Rijndael specification.
In closing, developers would do well to consider how to integrate the security advances that will follow the widespread use of Rijndael as a cryptoalgorithm. AES will soon supplant DES as the standard demanded by the general business community, and the art of the field will no doubt follow.