Data Encryption Standard (DES)

"A security system is only as strong as its weakest link. ...It doesn't matter how strong the other parts are." - Niels Ferguson & Bruce Schneier.

There are 5 high-level steps to DES: (1) Generate per round keys (2) Initial Permutation (3) 16 Mangler Rounds (4) Left-Right Swap (5) Inverse Permutation DES (Data Encryption Standard) first adopted in 1977 by the NIST (National Institute of Standards and Technology), is a widely used encryption technique. DES encryption and decryption is a symmetric iterated block cipher process in that only 1 key is used to encrypt and decrypt the same message. Each round is based on the Feistel network of switching each half of the input but only 1 of the halves undergoes the mangler function as described below. To see exactly what a round does view the Feistel structure section.

Mangler Function

1. The mangler function first expands R_n (the right half of the input) from a 32-bit value into a 48-bit value, by breaking R_n into 8 4-bit chunks and expanding each of those chunks into 6-bits as follows:

2. The 48-bit key K_n is broken down into 8 6-bit chunks and Xor'ed with each R_n 6-bit chunk.

3. This 6-bit output is then fed into 1 of 8 S-boxes, which produces a 4-bit output. Each set of 6-bits has its own S-box. For example the 6-bit string 101101 uses its first 1 and last 1 to determine the row and the 2^nd through 5^th symbols to determine the column:

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

00      1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111

01      0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000

10      0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000

11      1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101

4. All 8 4-bit outputs are combined into a 32-bit quantity whose bits are then permuted to ensure good diffusion and the avalanche affect.

The following is a conceptual view of the mangler function where the A's represent R_n, the B's represent the expanded version of R_n, which get Xor'ed with the key as described in step 2 above. Those values then get fed to the S-boxes and then shrunk back to 4-bit values at the C's then finally permuted and a new scrambled 32 bit value is produced:

Key Expansion

Initially a permutation process is performed on the key. Next, for each round, the key undergoes a bitwise left circular shift and a permutation to produce an output (essentially a sub-key) that's applied to the complex function's (as described above). Each sub-key is different because of the repeated bit shifts.

Triple-DES

With ever increasing computing power and speed DES has been vulnerable to a brute-force attack because of its small key size of 56-bits. A Double DES approach sounds good because 2 56-bit keys are used, therefore increasing the key size to 112 bits. However, given a known plaintext-ciphertext pair a "meet-in-the-middle" brute force attack can be achieved by only a factor of 2. One can initially encrypt the plaintext with all 2⁵⁶ possible key values (where 1 result is a matching decryption of the ciphertext). Next decrypt the ciphertext using all possible 2⁵⁶ key values until a result matches the encrypted plaintext. Then the key can be obtained.

So, the next solution is Triple DES. The DES algorithm is used in sequence 3 times in an Encrypt-Decrypt-Encrypt fashion for encryption and for decryption the inverted D-E-D is used. Triple DES uses 2 56-bit keys, for instance when encrypting a plaintext, key 1 is used, key 2, and then key 3 is used for the E-D-E process respectively. Conceptually, a message is scrambled from the first key, it then gets even more scrambled with the second key, and then scrambled yet one more time with the first key to produce the final ciphertext as shown below.

Links

http://www.eff.org/Privacy/Crypto_misc/DESCracker/
http://www.eff.org/DEScracker/
http://www.itl.nist.gov/fipspubs/fip46-2.htm
http://searchsecurity.techtarget.com/sDefinition/0,,sid14_gci213893,00.html
http://snoopy.falkor.gen.nz/~rae/DES.html
http://csrc.ncsl.nist.gov/cryptval/des/des.txt
http://www.x5.net/faqs/crypto/q56.html
http://www.geocities.com/SiliconValley/Code/4704/Feistel.html