DES

IntroductionSearch on YouTubeBookmarkSaved

HistorySearch on YouTubeBookmarkSaved

DES came from a public request for proposals:

• In 1973, NIST published a request for proposals for a national symmetric-key cryptosystem.
• A proposal from IBM, a modification of a project called Lucifer, was accepted as DES.
• DES was published in the Federal Register in March 1975 as a draft of the Federal Information Processing Standard (FIPS).

DES is the historical reference block cipher. Its structure is a larger version of S-DES, so many steps look familiar.

OverviewSearch on YouTubeBookmarkSaved

DES is a block cipher. It encrypts 64-bit blocks with a 56-bit key (deck Figure 6.1):

The key enters the key generator as 64 bits with parity bits. The parity drop removes 8 bits, so the real key has 56 bits. The key space is:

$$2^{56} = 7.2 \times 10^{16} \text{ values}$$

DES structureSearch on YouTubeBookmarkSaved

General structureSearch on YouTubeBookmarkSaved

DES uses 16 rounds. Each round is a Feistel cipher. The full pipeline:

1. The 64-bit plaintext goes through the initial permutation (IP).
2. The key goes through Permuted Choice 1 (PC-1), the parity drop, which gives 56 bits.
3. For each round, the key generator does a left circular shift on the two 28-bit key halves. Then Permuted Choice 2 (PC-2) compresses the 56 bits to the 48-bit round key $K_i$.
4. Each of the 16 rounds uses one round key $K_1 \dots K_{16}$.
5. A 32-bit swap and the inverse initial permutation ($\text{IP}^{-1}$), also called the final permutation, give the 64-bit ciphertext.

The deck shows two equal views of the end of the cipher. The Stallings figure has 16 rounds with a swap in each round, then one extra 32-bit swap. The Forouzan figure has no swapper in round 16. The two views give the same ciphertext.

Initial and final permutationsSearch on YouTubeBookmarkSaved

The initial permutation moves each of the 64 bits to a new position. For example, input bit 1 goes to output position 40, and input bit 2 goes to output position 8. The final permutation is the exact inverse of the IP. Read each table left to right, row by row. Entry $n$ gives the input bit that goes to output position $n$.

Initial permutation:

Final permutation:

Permutation examplesSearch on YouTubeBookmarkSaved

Example 1. Find the output of the final permutation when the input is:

$$0x0000 \; 0080 \; 0000 \; 0002$$

Only bits 25 and 63 are 1s. The final permutation sends input bit 25 to output bit 64 and input bit 63 to output bit 15. The result is:

$$0x0002 \; 0000 \; 0000 \; 0001$$

Example 2. Prove that the IP and the final permutation are inverses. Find the IP output when the input is $0x0002 \; 0000 \; 0000 \; 0001$.

The input has only two 1s, so the output also has only two 1s. From the IP table, input bit 15 becomes output bit 63, and input bit 64 becomes output bit 25. The output has 1s at bits 25 and 63:

$$0x0000 \; 0080 \; 0000 \; 0002$$

The round trip gives the start value again. Thus the two permutations are inverses, as IP and IP$^{-1}$ are in S-DES.

A roundSearch on YouTubeBookmarkSaved

Each round takes $L_{i-1}$ and $R_{i-1}$ (32 bits each) and has two parts:

• Mixer: $L_{i-1}$ XORs with $f(R_{i-1}, K_i)$.
• Swapper: the two halves change places.

$$L_i = R_{i-1}, \qquad R_i = L_{i-1} \oplus f(R_{i-1}, K_i)$$

The DES functionSearch on YouTubeBookmarkSaved

Function overviewSearch on YouTubeBookmarkSaved

The heart of DES is the DES function. It applies a 48-bit key to the rightmost 32 bits and produces a 32-bit output.

$$f(R_{i-1}, K_i) \longrightarrow \text{32-bit output}$$

The DES function has four parts:

1. Expansion P-box: $R_{i-1}$ expands from 32 bits to 48 bits.
2. XOR: the expanded $R_{i-1}$ XORs with the 48-bit round key $K_i$.
3. S-boxes: 8 substitution boxes change the 48 bits back to 32 bits.
4. Straight P-box: a 32-bit permutation gives the 32-bit output.

Expansion P-boxSearch on YouTubeBookmarkSaved

$R_{i-1}$ has 32 bits and $K_i$ has 48 bits, so DES first expands $R_{i-1}$ to 48 bits. The input splits into eight 4-bit sections. Each section becomes 6 bits: it gets one bit from each neighbor section. Thus 16 of the 32 input bits appear twice. At the ends, the bits wrap around: output bit 1 takes input bit 32, and the last output bit takes input bit 1.

The relation between input and output can be written as a formula, but DES uses this table to define the P-box. Compare it with E/P in S-DES, which expands 4 bits to 8 bits for the same reason.

XOR with the round keySearch on YouTubeBookmarkSaved

After the expansion permutation, DES XORs the expanded right section with the round key. Both inputs have 48 bits. DES uses the round key only in this operation.

S-boxesSearch on YouTubeBookmarkSaved

The S-boxes do the real mixing (confusion). DES uses 8 S-boxes, each with a 6-bit input and a 4-bit output:

$$48 \text{ bits} \longrightarrow 8 \times 6 \text{ bits} \longrightarrow 8 \times 4 \text{ bits} \longrightarrow 32 \text{ bits}$$

Each 6-bit chunk selects one row and one column of its S-box:

• Bit 1 and bit 6 together give a 2-bit row (0..3).
• Bits 2..5 (the middle 4) give a 4-bit column (0..15).
• The table entry (0..15) is the 4-bit output.

Each S-box table has 4 rows and 16 columns, so it has $2^6 = 64$ entries. This is the DES version of the S-DES rule, where the outer bits also give the row.

S-box examplesSearch on YouTubeBookmarkSaved

Example 1. The input to S-box 1 is $100011$. The first and sixth bits give $11$, which is row 3. The remaining bits $0001$ give column 1. Row 3, column 1 of S-box 1 holds $12$, which is $1100$:

$$100011 \longrightarrow 1100$$

Example 2. The input to S-box 8 is $000000$. The first and sixth bits give $00$, which is row 0. The remaining bits $0000$ give column 0. Row 0, column 0 of S-box 8 holds $13$, which is $1101$:

$$000000 \longrightarrow 1101$$

S-box tablesSearch on YouTubeBookmarkSaved

The deck shows only S-box 1. For the other seven boxes, it refers to the textbook. All eight tables are here for reference.

S-box 1:

S-box 2:

S-box 3:

S-box 4:

S-box 5:

S-box 6:

S-box 7:

S-box 8:

Straight permutationSearch on YouTubeBookmarkSaved

The straight permutation keeps the size at 32 bits and changes the bit order:

After this P-box, the DES function returns 32 bits for the Feistel XOR.

Key generationSearch on YouTubeBookmarkSaved

Parity-bit dropSearch on YouTubeBookmarkSaved

The round-key generator receives a 64-bit key with parity bits. It drops the 8 parity bits (bits 8, 16, ..., 64) and permutes the other 56 bits. The deck's parity-bit drop table (PC-1):

The output splits into two halves of 28 bits. The left half is the first 28 entries (up to 36 in row 4). The right half is the last 28 entries (from 63 in row 4).

Shift scheduleSearch on YouTubeBookmarkSaved

In each round, the two halves do a left circular shift:

The total shift over the 16 rounds is $4 \times 1 + 12 \times 2 = 28$ bits. That is one full cycle of a 28-bit half, so each half is back at its start position after round 16.

Key compressionSearch on YouTubeBookmarkSaved

After the shift in each round, the 56 bits go through the compression P-box (PC-2). It drops 8 bits and gives the 48-bit round key. The deck's key-compression table:

Key generation summarySearch on YouTubeBookmarkSaved

$$K_i = \text{PC-2}(\text{shift}(\text{PC-1}(\text{key})))$$

The shifts accumulate round by round, with 1 or 2 bits in each round. Each round key is used once, in the XOR of the DES function.

Worked exampleSearch on YouTubeBookmarkSaved

Encryption traceSearch on YouTubeBookmarkSaved

The deck runs one full encryption. All values are hexadecimal. Key: $AABB09182736CCDD$. Plaintext: $123456ABCD132536$. Ciphertext: $C0B7A8D05F3A829C$.

The Left column shows $L_i$ and the Right column shows $R_i$ after each round. Each $L_i$ equals $R_{i-1}$ from the round before. Round 16 has no swap, so $R_{16} = R_{15}$.

After combination: $19BA9212CF26B472$. After the final permutation:

$$\text{ciphertext} = C0B7A8D05F3A829C$$

Decryption traceSearch on YouTubeBookmarkSaved

Bob, at the destination, decrypts the ciphertext from Alice with the same key. Decryption uses the same algorithm with the round keys in reverse order. Bob applies the IP, then 16 rounds with $K_{16}$ first and $K_1$ last, then the final permutation.

After combination: $14A7D67818CA18AD$. After the final permutation:

$$\text{plaintext} = 123456ABCD132536$$

The values in the decryption trace are the encryption values in reverse order. The Feistel structure lets decryption use the same rounds; only the key order changes.

DES analysisSearch on YouTubeBookmarkSaved

Avalanche effectSearch on YouTubeBookmarkSaved

Critics have analyzed DES in detail. Tests measure how strong DES is in some properties that a block cipher must have. Two of these properties are the avalanche effect and completeness.

To check the avalanche effect, the deck encrypts two plaintext blocks with the same key, $22234512987ABB23$. The plaintexts differ only in the rightmost bit:

The two ciphertext blocks differ in 29 bits. Thus a change of about 1.5 percent of the plaintext ($1/64$) gives a change of about 45 percent of the ciphertext ($29/64$).

Number of bit differences after each round:

The difference spreads fast. From round 4 on, it stays between 28 and 39 of the 64 bits.

Completeness effectSearch on YouTubeBookmarkSaved

Completeness effect means that each bit of the ciphertext must depend on many bits of the plaintext.

Key sizeSearch on YouTubeBookmarkSaved

• A 56-bit key gives $2^{56} = 7.2 \times 10^{16}$ values.
• A brute-force search looked hard, but advances have made it possible:
  • 1997: broken on the Internet in a few months.
  • 1998: broken on dedicated hardware (EFF) in a few days.
  • 1999: broken by the two methods together in 22 hours.
• The attacker must still recognize the plaintext when a test key is correct.
• These results forced users to consider alternatives to DES.

Timing attacksSearch on YouTubeBookmarkSaved

Timing attacks attack the actual implementation of the cipher, not the algorithm:

• They use knowledge of the effects of an implementation to find some or all subkey bits.
• They use the fact that calculations can take different times, which depend on the input values.

Triple DESSearch on YouTubeBookmarkSaved

AlgorithmSearch on YouTubeBookmarkSaved

Triple DES (3DES) is the practical answer to the short DES key.

• 3DES uses a block of 64 bits.
• It uses three DES keys $K_1$, $K_2$, $K_3$, each of 56 bits.
• The encryption follows an EDE sequence:

$$C = E(K_3, D(K_2, E(K_1, P)))$$

• In words: DES encrypt with $K_1$, DES decrypt with $K_2$, then DES encrypt with $K_3$.

DecryptionSearch on YouTubeBookmarkSaved

Decryption does the reverse steps. It uses the keys in reverse order, and each cipher becomes its reverse cipher:

$$P = D(K_1, E(K_2, D(K_3, C)))$$

The deck figure shows encryption as DES cipher ($K_1$), DES reverse cipher ($K_2$), DES cipher ($K_3$). Decryption runs from the ciphertext: DES reverse cipher ($K_3$), DES cipher ($K_2$), DES reverse cipher ($K_1$).

ApplicationsSearch on YouTubeBookmarkSaved

• The electronic payment industry uses Triple DES and continues to develop and publish standards based on it.
• Microsoft OneNote and Microsoft Outlook 2007 use Triple DES to password-protect user content.

BenefitsSearch on YouTubeBookmarkSaved

• With a 168-bit key length, 3DES is not open to brute-force attack.
• 3DES is based on the DES algorithm, so it is easy to change existing software to use Triple DES.

DrawbacksSearch on YouTubeBookmarkSaved

• It has three times as many rounds as DES, so it is slower.
• It uses a 64-bit block size. For both efficiency and security, a larger block size is better.
• Thus NIST issued a call for proposals for the Advanced Encryption Standard (AES) to replace DES.

Quick self-testSearch on YouTubeBookmarkSaved

What are the input and output sizes in DES, and what happens to the key bits?

The input is a 64-bit plaintext and the output is a 64-bit ciphertext. The key has 56 bits. The key generator receives 64 bits with 8 parity bits, and the parity drop (PC-1) removes the parity bits first.

How many rounds does DES use and what cipher type is each round?

DES uses 16 rounds, and each round is a Feistel cipher. The round splits the 64-bit state into two 32-bit halves. It applies the DES function to the right half with the round key. It XORs the result into the left half, then swaps the halves.

Show that the IP and the final permutation are inverses, with the deck example.

Input $0x0000 0080 0000 0002$ has bits 25 and 63 set. The final permutation sends bit 25 to output 64 and bit 63 to output 15, which gives $0x0002 0000 0000 0001$. The IP sends bit 15 to 63 and bit 64 to 25, which gives $0x0000 0080 0000 0002$ again.

List the four parts of the DES function and their sizes.

Expansion P-box: 32 to 48 bits. XOR with the 48-bit round key. Eight S-boxes: eight 6-bit inputs give eight 4-bit outputs, so 48 bits become 32 bits. Straight P-box: 32 to 32 bits.

How does an S-box change a 6-bit input into 4 bits?

Bit 1 and bit 6 give a 2-bit row index (0..3). Bits 2 to 5 give a 4-bit column index (0..15). The table entry at that row and column is the 4-bit output. Example: S-box 1, input $100011$, row 3 and column 1 give 12, so the output is $1100$.

Give the DES key schedule sizes and the shift schedule.

PC-1 keeps 56 of the 64 key bits and splits them into two 28-bit halves. In each round, the halves do a left circular shift. The shift is 1 bit in rounds 1, 2, 9 and 16, and 2 bits in the other 12 rounds. The total is 28 bits, one full cycle. PC-2 then compresses 56 bits to the 48-bit $K_i$.

Trace the deck's worked encryption example.

Key $AABB09182736CCDD$, plaintext $123456ABCD132536$. After the IP: $14A7D67818CA18AD$, so $L_0 = 14A7D678$ and $R_0 = 18CA18AD$. After 16 rounds with keys $194CD072DE8C$ to $181C5D75C66D$, $L_{16} = 19BA9212$ and $R_{16} = CF26B472$. The combination is $19BA9212CF26B472$, and the final permutation gives $C0B7A8D05F3A829C$.

How does Bob decrypt, with the deck trace?

Bob uses the same rounds with the keys in reverse order. After the IP, ciphertext $C0B7A8D05F3A829C$ gives $L_0 = 19BA9212$ and $R_0 = CF26B472$. Round 1 uses $K_{16} = 181C5D75C66D$ and round 16 uses $K_1 = 194CD072DE8C$. The combination is $14A7D67818CA18AD$, and the final permutation gives $123456ABCD132536$.

Define the avalanche effect and the completeness effect with the deck numbers.

Avalanche: with key $22234512987ABB23$, the plaintexts $0000000000000000$ and $0000000000000001$ give ciphertexts that differ in 29 bits. A 1.5 percent change in the plaintext gives a 45 percent change in the ciphertext. Completeness: each ciphertext bit must depend on many plaintext bits.

Give the strength record of DES and describe timing attacks.

DES has $2^{56} = 7.2 \times 10^{16}$ keys. It was broken in 1997 on the Internet in a few months. In 1998, the EFF's dedicated hardware broke it in a few days. In 1999, the two methods together broke it in 22 hours. Timing attacks use the different calculation times of an implementation to find some or all subkey bits.

Give the 3DES formula, its benefits and its drawbacks.

$C = E(K_3, D(K_2, E(K_1, P)))$ with three 56-bit keys, and $P = D(K_1, E(K_2, D(K_3, C)))$. Benefits: the 168-bit key stops brute force, and existing DES software is easy to change. Drawbacks: three times the rounds makes it slower, and the 64-bit block is small. Thus NIST called for AES as the replacement.