Table of Contents
The Data Encryption Standard, aka LUCIFER, was created by IBM and submitted Aug 6, 1974 as a DES candidate. In 1980 it was adopted formally as the standard for the banking industry. As early as 1975 the security of DES was doubted by some, such as Martin Hellman and Whit Diffie because of its (relatively) small key space. In 1998 DES was cracked by the EFF in a total time of 56 hours. To rise to this task the EFF built a dedicated DES cracking machine called Deep Crack, which contained 27 boards of 64 chips designed to test every possible DES key. Until the keyspace had been exhaustively searched NIST continued to renew the certification of DES as a 'secure' algorithm. Sometime in the late 1990s (1999?), triple-DES was certified as a FIPS approved standard, and recommended for use instead of DES.
DES is a Feistel Network, which has a particular structure which can be seen in the figure below. Each side of the drawing is performing an operation on half of the data. At each node on the side, a function is performed, then the sides are either recombined or moved over to the other side of the network for the next round. At the end the data is recombined forming the completed output.
The round keys are generated from the 64 bit secret key. First the 64 bit key is trimmed down to 56 bits and ordered in a particular manner. The 56 bit permutation is split in half and each half is then taken and rotated varying amounts to generate 16 different pairs of 28 bits. The pairs are concatenated back to form 56 bit values. Each one of these is then subjected to another permutation which picks 48 bits out of the 56. The 16 48-bit keys are the sub keys used during encryption.
There are several modes that DES encryption can operate with. Electronic codebook, Cipher Block Chaining, Cipher Feedback, and Output feedback. These modes are not DES specific, and can be used with most block encryption methods (Skipjack is another FIPS algorithm that is used in all of these modes).
Electronic Codebook
Cipher Block Chaining
Cipher Feedback
Output Feedback
Permute the plain-text
An initial permutation rearranges the plain-text, and splits it in half, forming a left and right half. Each part is 32 bits long.
The main work part of DES is 16 iterations of the following:
Li = Ri-1 Ri = Li-1 ⊕ f(Ri-1, Ki)
The function f is a little more complex than it looks above. It takes as arguments a part of the current text to be operated on and a round key.
Each block is first expanded from 32 to 48 bits, using another permutation table to decide which bits get duplicated and reordered. The table looks like this:
| 32 | 1 | 2 | 3 | 4 | 5 |
| 4 | 5 | 6 | 7 | 8 | 9 |
| 8 | 9 | 10 | 11 | 12 | 13 |
| 12 | 13 | 14 | 15 | 16 | 17 |
| 16 | 17 | 18 | 19 | 20 | 21 |
| 20 | 21 | 22 | 23 | 24 | 25 |
| 24 | 25 | 26 | 27 | 28 | 29 |
| 28 | 29 | 30 | 31 | 32 | 1 |
With the resulting 48 bits, groups of 6 are taken and used to look up values in tables called "S-Boxes". The 6 bits are used as indexes into the tables which at each location contains a 4 bit value. All 8 groups of 6 are transformed back to 32 bit values. ???? The key material is then XORed with the current 32 bits.
![[Note]](images/note.png) | Note |
|---|---|
I need to make this section a little more clear | |
The decryption is basically the inverse of the encryption, except different tables are used (inverse S-Boxes).
Triple DES is just DES applied three times, using two or three different keys (very important!). The first key is used to encrypt, the second to decrypt and the third to encrypt again (EDE). When we looked at simple ciphers, applying a substitution multiple times gained no more strength than doing it once. This is not the case with DES. Using 2 or 3 keys produces a encryption with an equivalent key of about 112 bits.
Because you can use triple DES
DES can be broken in under 24 hours
To defeat DES, new methods of of attack needed to be created. Two different types of analysis have been developed for the purpose of defeating DES. Both serve to provide analysis of block ciphers in general. It should be noted that all of the transformations that occur within the DES encryption are LINEAR except the S-box substitution. This is very important for the analysis of DES and other block ciphers in general.
| Note |
|---|---|
| This is confusing and not completely right | |
The idea behind Linear cryptanalysis consists of assigning linear approximations to S box substitutions. This can be done by looking at the input bits and the output bits and determine statistical relationships between the 2 for a specific S-box.
It is important to realize here that when looking at the different bits, an XOR operation is a linear operation. This can be seen by looking at X1 ⊕ X2 = 0, which results in the conclusion X1 = X2, and also X1 ⊕ X2 = 1, resulting in X1 != X2. Combinations of XOR can then be produced. Statements such as X1 ⊕ X2 = 0, and X2 ⊕ X3 = 0, result in X1 = X3.
Once each S-Box has been analyzed, output statistics can be determined by combining the expressions for each S-box that have been determined. This will give a probability of a certain input given an output (the relationships are linear remember?). Using this knowledge we can come up with plain-texts with high probabilities. How do we construct an attack using this?
| Note |
|---|---|
| This is confusing and not completely right | |
Differential Cryptanalysis is very similar to Linear, except that Differential cryptanalysis considers the difference in input strings to the S-Box when correlating to the output. This attack basically consists of varying the input to the S-Boxes and determining which output bits change. How do we construct an attack using this?