 | How a well-established encryption standard was supplanted by a contest-winning algorithm
Larry Loeb (larryloeb@prodigy.net)
Author
01 Nov 2000 The Data Encryption Standard (DES) that has enjoyed widespread use since the 1970s is showing signs of age, and a new algorithm -- Rijndael -- is well on its way to becoming the new standard. Here, Larry Loeb offers the specifics of each algorithm and some insight as to why the change is taking place. The DES algorithm is the most widely used
encryption algorithm in the world. Advances in hardware since its inception
have caught up with it of late, and in October 2000, it was replaced as
the bedrock of government cryptology by the inclusion of another encryption
algorithm into the Advanced Encryption Standard (AES). AES is the designated
standard cryptosystem that will be used in the future by government and
banking users. AES uses a cryptoalgorithm for the actual encoding of data
that differs from the previous DES standard. We'll look at how this
came about and how DES's algorithm was supplanted by an algorithm called
Rijndael in AES.
DES: The first steps
On May 15, 1973, the National Bureau of Standards (NBS) published a
notice in the Federal Register soliciting proposals for cryptographic algorithms
to protect data during transmission and storage. IBM submitted a candidate
that it had developed internally under the name LUCIFER. After evaluating
the algorithm with the "guidance" of the National Security Agency (NSA),
the NBS adopted a modification of the LUCIFER algorithm as the new Data
Encryption Standard on July 15, 1977. This led to the creation of
Federal Information Processing Standard (FIPS) 46 (since updated to FIPS
46-3) (see Resources) which describes the use
of DES and the current DES 3 standard. The banking industry is the largest user of
encryption outside government. All those electronic funds transfers (EFTs)
and automated teller machines (ATMs) 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
American National Standards Institute (ANSI). ANSI X3.92, adopted in 1980,
specified the use of the DES algorithm. Your ATM routinely uses it 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 (or 64 bits). However, for some
reason (possibly due to the "guidance" given to the NBS by the NSA) every
eighth 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 an encoding
system is directly related to its keyspace, or how many possible keys there
are to the system. More bits used translates to more possible keys. 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
limit the keyspace to a great degree, thus making the system easier to
crack. DES is a block cipher. That means it operates on plain text blocks of
a given size (nominally 64 bits) and returns cipher text blocks of the
same size. So, DES results in a permutation among the 264 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 block R. The DES algorithm uses the following steps:
- Create 16 subkeys, each of which is 48 bits long. The
64-bit key is permuted according to a specified order, or "table." If the 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 table's second
entry is 36, then the 36th bit of the original key becomes the second bit
of the permuted key, and so on. This is a linear substitution method that
creates a linear permutation. 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 16 blocks Cn and
Dn, where 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 "left shifts" that say which bit is operated
upon. In all cases, a single left shift means 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 eighth bit is ignored.
- 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 describe the new arrangement of the bits from their
initial order. This is the linear table structure we've seen before.
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 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 eight blocks of six 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 four-bit number that replaces the
original six bits. The net result is that the eight groups of six bits
are transformed into eight groups of four bits (the four-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 through the process above.
Decryption is simply the inverse of encryption, following the same steps
as above, but reversing the order in which the subkeys are applied. The
DES algorithm is invertible. 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 2112, compared to the 256 possible keys
for DES. The Advanced Encryption Standard effort
It was obvious to the Government as far back as 1993 that DES security
was going to be compromised at some point. Even if we posit that the NSA
built a backdoor into DES that allowed the government to do routine decryption
of DES messages (as public key discoverers Diffie and Hellman seem to have
alleged in a letter to the NSA in 1975), it was a cipher that was starting
to get long in the tooth. It wasn't that efficient a way to do things.
It couldn't work well on hardware (such as the 'smart cards' that were starting to show up). But it took until 1997 for the National Institute of Science
and Technology (NIST) to start looking for its successor under the banner
of the AES project. The following initial goals of the AES effort were stated in an April 1997 AES
Workshop:
- Strong cryptoalgorithm for government and commercial use
- Support of standard codebook modes
Note: The DES algorithm permutes a message block into a cipher
block. If each block is encrypted individually, then 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
message blocks through an initial XOR operation. Because each mode
was in governmental/banking use, compatibility in how AES would handle
information was needed.
- Significantly more efficient than DES 3
- Variable key size so that security could be increased when
needed
- Selected in a fair and open manner
- Can be publicly defined
- Can be publicly evaluated
The draft minimum acceptability requirements and evaluation criteria
for AES were: 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 can be increased as
needed. A.4 AES shall be able to be implemented 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 ensuring that a non-encumbered (that is, patent-free)
algorithm would be the only one that could be selected.
A.6 Algorithms that meet the above requirements will be judged based
on the following factors:
- Security (the effort required to cryptanalyze)
- Computational efficiency
- Memory requirements
- Hardware and software suitability
- Simplicity
- Flexibility
- Licensing requirements (see A5 above)
Rijndael: The AES algorithm winner
In October 2000, the NIST selected Rijndael (pronounced "Rhine dale")
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
the wheels 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 are defined at byte level, with bytes
representing elements in the finite field GF(28), which is representative
of the eight bits in a byte. Other operations are defined in terms of four-byte
words. Addition, as usual, corresponds with the simple bitwise EXOR at the
byte level. In the polynomial representation, multiplication in GF(28)
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) = (x8 + x4 + x3 + 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. 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. (An example of this linear kind of structure are those tables we discussed back in the DES discussion that substitute bits by a fixed tabular means.) The round transformation of Rijndael does not have this venerable Feistel structure.
Instead, the round transformation is composed of three distinct invertible
uniform transformations, called layers. ("Uniform" here means 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. That's the key conceptual difference between DES and Rijndael,
in my opinion. 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(28) and multiplied modulo
x4 + 1 with a fixed polynomial c( x ), given by c( x ) = '03'
x3 + '01' x2 + '01' x + '02'. This polynomial is coprime
to x4 + 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 (for example, 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, and
a final round.
In pseudo C code:
Rijndael(State,CipherKey)
{
KeyExpansion(CipherKey,ExpandedKey);
AddRoundKey(State,ExpandedKey);
For( i=1 ; i<Nr ; i++ ) Round(State,ExpandedKey + Nb*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<Nr ; i++ ) Round(State,ExpandedKey + Nb*i);
FinalRound(State,ExpandedKey + Nb*Nr);
}
|
Since Rijndael is invertible, the decyphering process just reverses
the steps described above. You can find technical details in the Rijndael
specification (see
Resources). 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. Resources About the author
Larry Loeb has been writing and consulting since the 20th century about computer topics. He has published a book on SET, the protocol developed
by Visa and Mastercard for secure electronic transactions. He can usually
be contacted at larryloeb@prodigy.net should there be any questions, bribes,
or offers of a questionable nature.
|
| |
