DES is a product block encryption algorithm (a cipher) in which 16 iterations, or rounds, of the substitution and transposition (permutation) process are cascaded. The block size is 64 bits, so that a 64bit block of data (plaintext) can be encrypted into a 64bit ciphertext. The key, which controls the transformation, also consists of 64 bits. Only 56 of these, however, are at the user's disposal; the remaining eight bits are employed for checking parity. The actual key length is therefore 56 bits.
Subsets of the key bits are designated K_{1}, K_{2}, etc., with the subscript indicating the number of the round. The cipher function (substitution and transposition) that is used with the key bits in each round is labeled f. At each intermediate stage of the transformation process, the cipher output from the preceding stage is partitioned into the 32 leftmost bits, L_{i}, and the 32 rightmost bits, R_{i}. R_{i} is transposed to become the lefthand part of the next higher intermediate cipher, L_{i+1}. The righthand half of the next cipher, R_{i+1}, however, is a complex function of the key and of the entire preceding intermediate cipher. The essential feature to the security of the DES is that f involves a very special nonlinear substitutioni.e., f(A) + f(B) f(A + B)specified by the Bureau of Standards[?] in tabulated functions known as Sboxes. This operation results in a 32bit number, which is logically added to Ri to produce the lefthand half of the new intermediate cipher. This process is repeated, 16 times in all. To decrypt a cipher, the process is carried out in reverse order, with the 16th round being first. The DES algorithm lends itself to integratedchip implementation. By 1984 the Bureau of Standards had certified over 35 LSI and VLSIchip implementations of the DES, most on single 40pin chips, some of which operate at speeds of several million bits per second.
When the cipher was first released, the design criteria for the Sboxes was not released. With the National Security Agency's involvement in the design of the Sboxes, most security researchers were wary of DES. In 1990 with the independent discovery and open publication by Biham and Shamir of differential cryptanalysis, it turned out that at least some of the wariness was uncalled for. The primary design criteria for the Sboxes seems to have been (and has been claimed to have been by IBM personnel involved) to strengthen them against differential cryptanalysis. The secrecy behind the design criteria at the time appears to have been due to the fact that the technique was not known to the public at the time. Notably, DES is theoretically vulnerable to a technique discovered later by Matsui, linear cryptanalysis. It is unknown whether the NSA or IBM were aware of linear cryptanalysis at the time DES was finalized, but most knowledgeable observers think not.
Because the key length is only 56 bits, DES can be, and has been, broken by the brute force attack method of running through all possible keys. It is believed that one of the reasons this reduced key length was chosen was that NSA in the mid'70s possessed enough computer power to brute force break keys of this length. In the years since, computer hardware progress has been such that most anyone now can have sufficient computational capacity. The EFF, a cyberspace civil rights group (with neither much funding nor personnel), did it in a little more than 2 days' search at about the same time at least one attorney from the US Justice Department was publicly announcing that DES was and would remain unbreakable. Many former DES users now use Triple DES (3DES) which was described and analyzed by one of DES's patentees (see FIPS 463); it involves DES encryption of each data block three times with different keys. 3DES is widely regarded as adequately secure for now, though it is quite slow. Note, however, that there are several ways to use DES three times; only one of those is Tuchman's 3DES.
After another, long delayed competition, (NIST) has selected a new cipher, the Advanced Encryption Standard (AES) to replace DES (fall '01). AES was submitted by its designers under the name Rijndael.
Search Encyclopedia

Featured Article

