Simplified DES

S-DES overviewSearch on YouTubeBookmarkSaved

Inputs and outputsSearch on YouTubeBookmarkSaved

The S-DES encryption algorithm takes two inputs:

• an 8-bit block of plaintext (for example $10111101$)
• a 10-bit key

It produces an 8-bit block of ciphertext as output.

The S-DES decryption algorithm takes an 8-bit block of ciphertext and the same 10-bit key. It produces the original 8-bit block of plaintext.

Comparison with DESSearch on YouTubeBookmarkSaved

S-DES is a teaching cipher with the same structure as DES but small parameters. Professor Edward Schaefer of Santa Clara University developed it. It is not secure.

Five encryption functionsSearch on YouTubeBookmarkSaved

The encryption algorithm involves five functions, in this order:

1. An initial permutation (IP).
2. A complex function $f_K$. It does both permutation and substitution and depends on a key input.
3. A simple permutation function SW that switches the two halves of the data.
4. The function $f_K$ again.
5. A permutation function that is the inverse of the initial permutation ($\text{IP}^{-1}$).

The slide "Simplified DES Encryption Detail" shows the two $f_K$ blocks. Each $f_K$ block contains the function $F$, with E/P, XOR with the subkey, S0, S1 and P4.

Composition of functionsSearch on YouTubeBookmarkSaved

The slide writes the algorithm as a composition of functions:

$$\text{ciphertext} = \text{IP}^{-1}\Big(f_{K_2}\big(\text{SW}(f_{K_1}(\text{IP}(\text{plaintext})))\big)\Big)$$

where

$$K_1 = \text{P8}(\text{Shift}(\text{P10}(\text{key}))), \qquad K_2 = \text{P8}(\text{Shift}(\text{Shift}(\text{P10}(\text{key}))))$$

Decryption is essentially the reverse of encryption:

$$\text{plaintext} = \text{IP}^{-1}\Big(f_{K_1}\big(\text{SW}(f_{K_2}(\text{IP}(\text{ciphertext})))\big)\Big)$$

Thus there are:

• Two permutation functions, IP and $\text{IP}^{-1}$, with $\text{IP}^{-1}(\text{IP}(X)) = X$.
• Two permutation/substitution functions $f_K$. Each uses one subkey.
• One switch function SW. It interchanges the left and right 4 bits, so the second $f_K$ operates on a different set of bits.

Initial and final permutationsSearch on YouTubeBookmarkSaved

Each table entry names the input bit that goes to that output position.

Slide example:

The result is $\text{IP}^{-1}(\text{IP}(X)) = X$.

The round functionSearch on YouTubeBookmarkSaved

The function f_KSearch on YouTubeBookmarkSaved

Let L be the left 4 bits and R the right 4 bits of the 8-bit input. Let SK be a subkey. Then:

$$f_K(L, R) = (L \oplus F(R, SK), \; R)$$

Here $\oplus$ is the bit-by-bit exclusive-OR. Thus $f_K$ changes the left half only. The right half passes through unchanged.

Slide example: assume the output of the IP stage is $10111101$. Then $L, R = 1011, 1101$. Assume $F(1101, SK) = 1110$ for some subkey. This value changes with the subkey.

$$f_K(1011, 1101) = (1011 \oplus 1110, 1101) = (0101, 1101)$$

Inside FSearch on YouTubeBookmarkSaved

$F$ takes the right 4 bits and an 8-bit subkey:

Expansion and key mixingSearch on YouTubeBookmarkSaved

E/P maps the 4 input bits $n_1, n_2, n_3, n_4$ to 8 bits:

The slide arranges the 8 bits in two rows:

$$\begin{aligned} &n_4 \;\; n_1 \;\; n_2 \;\; n_3 \quad \text{(left half)} \\ &n_2 \;\; n_3 \;\; n_4 \;\; n_1 \quad \text{(right half)} \end{aligned}$$

XOR the 8-bit subkey $K_1 = k_{11} k_{12} \ldots k_{18}$ into these bits:

$$\begin{aligned} &n_4 \oplus k_{11}, \;\; n_1 \oplus k_{12}, \;\; n_2 \oplus k_{13}, \;\; n_3 \oplus k_{14} \\ &n_2 \oplus k_{15}, \;\; n_3 \oplus k_{16}, \;\; n_4 \oplus k_{17}, \;\; n_1 \oplus k_{18} \end{aligned}$$

Rename these 8 bits:

Row 1 goes into S-box S0. Row 2 goes into S-box S1. Each S-box gives a 2-bit output.

S-boxesSearch on YouTubeBookmarkSaved

The slide gives the S-boxes in decimal:

To use an S-box:

1. Use the first and fourth input bits as a 2-bit row number.
2. Use the second and third input bits as a 2-bit column number.
3. Write the entry at that row and column as 2 bits. This is the output.

Slide example: S0 entry $(0,0)$ is $1 = 01$. S1 entry $(1,1)$ is $0 = 00$.

P4 and the switchSearch on YouTubeBookmarkSaved

P4 permutes the 2 bits from S0 and the 2 bits from S1:

A 4-bit input $a\,b\,c\,d$ leaves P4 as $b\,d\,c\,a$. The P4 output is the output of $F$. Then $f_K$ XORs it into the left half.

The switch function SW interchanges the left and right halves. Thus the second $f_K$, with subkey $K_2$, operates on different data. The second $f_K$ works the same as the first. Decryption uses all the same functions, run backwards.

Key generationSearch on YouTubeBookmarkSaved

Key schedule stepsSearch on YouTubeBookmarkSaved

S-DES uses a 10-bit key shared between sender and receiver. The key schedule produces two 8-bit subkeys for particular stages of encryption and decryption.

1. Apply P10 to the 10-bit key.
2. Split the result into two 5-bit halves.
3. Do a circular left shift by 1 (LS-1) on each half.
4. Apply P8 to select and permute 8 of the 10 bits. The result is $K_1$.
5. Do a circular left shift by 2 more (LS-2) on each half from step 3.
6. Apply P8 again. The result is $K_2$.

Subkey K1Search on YouTubeBookmarkSaved

Slide example key: $1010000010$.

P10 takes bits $(3,5,2,7,4,10,1,9,8,6)$ of $1010000010$. The result is $10000\;01100$.

P8 takes bits $(6,3,7,4,8,5,10,9)$ of $0000111000$:

$$K_1 = 10100100$$

Subkey K2Search on YouTubeBookmarkSaved

Take the output of LS-1 and shift each half by 2 more positions:

P8 on $0010000011$ gives:

$$K_2 = 01000011$$

Worked encryptionSearch on YouTubeBookmarkSaved

Round 1Search on YouTubeBookmarkSaved

The last two slides run one full encryption. Key: $1010000010$, so $K_1 = 10100100$ and $K_2 = 01000011$. Plaintext: $11110011$.

Switch and round 2Search on YouTubeBookmarkSaved

SW gives $L = 1101$ and $R = 0100$.

Final permutationSearch on YouTubeBookmarkSaved

$\text{IP}^{-1}$ takes bits $(4,1,3,5,7,2,8,6)$ of $10000100$. These bits are $(0,1,0,0,0,0,0,1)$. So:

$$\text{ciphertext} = 01000001$$

DecryptionSearch on YouTubeBookmarkSaved

Reverse subkey orderSearch on YouTubeBookmarkSaved

Decryption uses the same functions, with the subkeys in reverse order:

1. Apply IP to the ciphertext.
2. Apply $f_K$ with $K_2$.
3. Apply SW.
4. Apply $f_K$ with $K_1$.
5. Apply $\text{IP}^{-1}$.

Decryption of $01000001$ with this key gives $11110011$ again.

Role of each partSearch on YouTubeBookmarkSaved

Quick self-testSearch on YouTubeBookmarkSaved

What are the block size and key size of S-DES?

The block is 8 bits. The key is 10 bits. The key schedule makes two 8-bit subkeys, $K_1$ and $K_2$.

Name the five functions of S-DES encryption in order.

IP, $f_K$ with $K_1$, SW, $f_K$ with $K_2$, and $\text{IP}^{-1}$. So ciphertext $= \text{IP}^{-1}(f_{K_2}(\text{SW}(f_{K_1}(\text{IP}(\text{plaintext})))))$.

Give the IP and inverse IP tables.

IP = 2 6 3 1 4 8 5 7. $\text{IP}^{-1}$ = 4 1 3 5 7 2 8 6. The slide example maps $01001101$ to $11000110$ and back.

Define f_K and say what happens to each half.

$f_K(L, R) = (L \oplus F(R, SK), R)$. The left half is XORed with the output of $F$. The right half does not change.

How is F(R, SK) built?

E/P (4 1 2 3 2 3 4 1) expands 4 bits to 8 bits. XOR with the 8-bit subkey. The left 4 bits go to S0 and the right 4 bits go to S1. Each S-box gives 2 bits. P4 (2 4 3 1) permutes the 4 bits.

How do you read an S-box?

Bits 1 and 4 give the row. Bits 2 and 3 give the column. The entry, written as 2 bits, is the output.

Produce K1 and K2 from key 1010000010.

P10 gives $10000\;01100$. LS-1 gives $00001\;11000$. P8 gives $K_1 = 10100100$. LS-2 gives $00100\;00011$. P8 gives $K_2 = 01000011$.

Encrypt plaintext 11110011 with key 1010000010.

IP gives $10111101$. Round 1: E/P $11101011$, XOR $K_1$ $01001111$, S0 $11$, S1 $11$, P4 $1111$, XOR $L$ gives $0100$. SW gives $1101\;0100$. Round 2: E/P $00101000$, XOR $K_2$ $01101011$, S0 $10$, S1 $01$, P4 $0101$, XOR $L$ gives $1000$. $\text{IP}^{-1}(10000100) = 01000001$.

How does decryption differ from encryption?

The functions are the same. The subkey order is reversed: the first $f_K$ uses $K_2$ and the second $f_K$ uses $K_1$.