1.3.1 DES (the Data Encryption Standard)

DES, the Data Encryption Standard, was designed by IBM in the 1970s, consulting with the NSA.  DES is a type of cipher known as an iterative block cipher, which breaks data into to blocks and repeats a set of operations on them.  The operations in DES are called a Feistel network, after the inventor.

DES uses a 56-bit key, though products exported from the U.S. were limited to using 40 meaningful key bits [wikipedia/40-bit-encryption]. It was later upgraded to triple-DES, using three 56-bit key pieces and repeating DES three times, giving up to 168 bits of protection.  But it's not just the key size that matters in a block cipher.  The block size itself matters a great deal, as we'll see below.  For DES, that block size is only 64 bits.

DES operates in sixteen rounds, each of which uses a 48-bit subkey generated from the original 56-bit key using a key scheduling algorithm.  In each round, half of the block is tweaked and half initially left alone, then XORed with the tweaked half.  The two halves are swapped before the next round.

The "tweaking" of the right half of the block is done by first expanding the 32 bits into 48 by replicating half of the bits, XORing with the 48-bit subkey, then dividing it into 6-bit chunks and pushing each chunk through one of eight substitution boxes, or S boxes.  Each S box turns 6 bits into 4, using a lookup table defined as part of the algorithm (that is, this operation is not key-dependent).  The S boxes are nonlinear (but not affine), which is the source of the true security of DES; if the S boxes were linear, breaking DES would be easy (or so I am told).

Decrypting DES is exactly the same operation as encrypting, except that the subkeys are used in reverse order.

Slightly more formally, the sequence of operations in a DES encryption is:

1. Apply initial permutation (IP) (a fixed operation)
2. For i = 1 to 16 do
1. divide the block into two 32-bit halves
2. expand the left half to 48 bits (a fixed operation)
3. calculate subkey i
1. split key into two 28-bit halves
2.  rotate each half 1 or 2 bits (a fixed operation according to the key schedule)
3. select a subset of 48 bits (a fixed operation according to  the schedule)
4. XOR subkey i with the left half of the block
5. split into 8 six-bit pieces
6. push each 6-bit piece through a $6\rightarrow 4$ S-box
7. permute and recombine the pieces (a fixed operation)
8. XOR the left half with the right half of the block
9.  swap halves of the block
3. Apply the final permutation (FP) (a fixed operation)

The $6 \rightarrow 4$ S boxes are obviously inherently non-reversible, but the earlier
expansion guarantees that ultimately no information is lost as the block passes through the entire network.

The success of cryptanalysis is often measured in terms of the number of rounds it can break in a multi-round cipher like DES.  e.g., if DES were six rounds instead of sixteen, we could do yea much.  Various attacks have been able to penetrate DES to different depths.  Of course, the more straightforward approach is sheer brute force; as early as 1977, Diffie and Hellman published a critique in which they argued that brute force stood at the edge of feasible, and indeed in 1999, a special-purpose machine named Deep Crack, built by the Electronic Freedom Foundation, cracked a DES key.  Further advances have made it possible even for dedicated hobbyists to crack.

Triple-DES (also called 3DES) has several modes of operation, but is usually used with three independent 56-bit keys, $K1$, $K2$, and $K3$, with encryption performed as $C = E_{K3}(D_{K2}(E_{K1}(P)))$ where $P$ is the plaintext, $E$ and $D$ are the encryption and decryption operations, and $C$ is the ciphertext.

DES was withdrawn as a standard in 2005, after having been replaced by AES in 2001, although the U.S. government still allows 3DES until 2030 for sensitive information.