S-DES Book Chapter

1. Simplified DES (S-DES) Key Generation Solved Example in Cryptograhy by Vidya Mahesh HuddarMahesh Huddar · S-DES key generation: P10, shifts, P8, K1 and K2, 6 minS - DES Decryption || Simplified data encryption standard(S-DES) || Explanation with exampleLectures by Shreedarshan K · S-DES decryption with an example (K2 first, then K1), 14 minSimplified DES Example (CSS322, Lecture 5, 2013)Steven Gordon · long lecture: a complete S-DES example, 44 min

Chapter overviewSearch on YouTubeBookmarkSaved

Purpose of S-DESSearch on YouTubeBookmarkSaved

This page follows the book section 3.1 on Simplified DES (S-DES). The book puts S-DES before full DES. A study of S-DES makes DES easier to understand.

• S-DES is an educational algorithm. It is not a secure algorithm.
• It has similar properties and structure to DES, but much smaller parameters.
• Professor Edward Schaefer of Santa Clara University developed it ([SCHA96]).
• The book tells you to work through an example by hand while you read.
• A footnote says that you can skip S-DES on a first reading. If the details of DES confuse you, come back to S-DES.

Inputs and outputsSearch on YouTubeBookmarkSaved

The S-DES encryption algorithm takes an 8-bit block of plaintext (example: $10111101$) and a 10-bit key. It produces an 8-bit block of ciphertext.

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

Five functionsSearch on YouTubeBookmarkSaved

The encryption algorithm has five functions:

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

The book repeats a lesson from chapter 2. Multiple stages of permutation and substitution give a more complex algorithm. This makes cryptanalysis more difficult.

Composition formSearch on YouTubeBookmarkSaved

The book writes encryption as a composition of functions (Figure 3.1):

The two subkeys are:

Decryption formSearch on YouTubeBookmarkSaved

Decryption is essentially the reverse of encryption. The subkey order changes:

Key generationSearch on YouTubeBookmarkSaved

Why a 10-bit keySearch on YouTubeBookmarkSaved

The function $f_K$ takes the data and an 8-bit key. The book gives three possible designs:

The key first goes through the permutation P10. Then a shift operation occurs. The shift output goes through P8 and gives subkey $K_1$. The shift output also goes into a second shift and a second P8. This gives subkey $K_2$ (Figure 3.2).

P10 and P8Search on YouTubeBookmarkSaved

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

Call the 10-bit key $(k_1, k_2, \dots, k_{10})$. The book defines P10 as:

Read each table from left to right. Each position gives the input bit for that output position. Thus the first output bit is input bit 3. The second output bit is input bit 5. P8 selects and permutes 8 of the 10 bits.

Worked key scheduleSearch on YouTubeBookmarkSaved

The book uses the key $1010000010$:

1. Apply P8 to the LS-1 output $0000111000$. The result is $K_1 = 10100100$.
2. Go back to the two 5-bit strings from LS-1.
3. Do a circular left shift of 2 positions on each string.
4. Apply P8 to $0010000011$. The result is $K_2 = 01000011$.

Encryption detailSearch on YouTubeBookmarkSaved

Initial and final permutationsSearch on YouTubeBookmarkSaved

The input is an 8-bit block of plaintext. IP permutes it first:

IP keeps all 8 bits of the plaintext, but it mixes them. At the end of the algorithm, the inverse permutation occurs:

An example shows that the second permutation is the reverse of the first: $\text{IP}^{-1}(\text{IP}(X)) = X$.

The function f_KSearch on YouTubeBookmarkSaved

$f_K$ is the most complex part of S-DES. It combines permutation and substitution functions. Let L be the leftmost 4 bits and R the rightmost 4 bits of the 8-bit input. Let F be a mapping from 4-bit strings to 4-bit strings. F is not necessarily one-to-one.

SK is a subkey. $\oplus$ is the bit-by-bit exclusive-OR.

Book example: the IP output is $10111101$. Assume $F(1101, SK) = 1110$ for some key SK. Then $1011 \oplus 1110 = 0101$, so:

Expansion and permutationSearch on YouTubeBookmarkSaved

The mapping $F$ takes a 4-bit number $(n_1, n_2, n_3, n_4)$. The first operation is an expansion/permutation:

The book shows the 8 output bits in two rows:

XOR with the subkeySearch on YouTubeBookmarkSaved

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

Rename the 8 bits:

The first 4 bits (row 0) go into S-box S0. S0 gives a 2-bit output. The other 4 bits (row 1) go into S1. S1 gives another 2-bit output.

The S-boxesSearch on YouTubeBookmarkSaved

The entries are 2-bit values, shown 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 in base 2. This is the 2-bit output.

Book example: $(p_{0,0}, p_{0,3}) = (00)$ and $(p_{0,1}, p_{0,2}) = (10)$. Read row 0, column 2 of S0. The entry is 3, or $11$ in binary. $(p_{1,0}, p_{1,3})$ and $(p_{1,1}, p_{1,2})$ select a row and column of S1 in the same way.

P4 permutationSearch on YouTubeBookmarkSaved

The 4 bits from S0 and S1 go through one more permutation:

The output of P4 is the output of the function $F$.

The switch functionSearch on YouTubeBookmarkSaved

$f_K$ changes only the leftmost 4 bits of its input. The switch function SW interchanges the left 4 bits and the right 4 bits. Thus the second $f_K$ operates on a different 4 bits.

In the second instance, the E/P, S0, S1 and P4 functions do not change. Only the key input changes to $K_2$.

Analysis of S-DESSearch on YouTubeBookmarkSaved

Brute-force attackSearch on YouTubeBookmarkSaved

A brute-force attack on S-DES is certainly feasible. A 10-bit key gives only $2^{10} = 1024$ possible keys. The attacker tries each key on the ciphertext. Then the attacker checks if the result is reasonable plaintext.

Known-plaintext equationsSearch on YouTubeBookmarkSaved

The book considers a known-plaintext attack:

• The attacker knows one plaintext $(p_1, \dots, p_8)$ and its ciphertext $(c_1, \dots, c_8)$.
• The key $(k_1, \dots, k_{10})$ is unknown.

Each $c_i$ is a polynomial function $g_i$ of the $p_j$ and $k_j$ bits. Thus the algorithm becomes 8 nonlinear equations in 10 unknowns. There are a number of possible solutions. The attacker can calculate and analyze each solution.

Source of nonlinearitySearch on YouTubeBookmarkSaved

• All the permutations and additions are linear maps.
• The S-boxes give the nonlinearity.

Rename the S0 input $(p_{0,0}, p_{0,1}, p_{0,2}, p_{0,3}) = (a, b, c, d)$. Rename the S1 input $(p_{1,0}, p_{1,1}, p_{1,2}, p_{1,3}) = (w, x, y, z)$. Let the 4-bit output be $(q, r, s, t)$. These equations define S0:

All additions are modulo 2. Similar equations define S1. The algorithm alternates linear maps and these nonlinear maps. This gives complex polynomial expressions for the ciphertext bits. Thus cryptanalysis is difficult.

Scale of the problemSearch on YouTubeBookmarkSaved

The book says that a reader can try to find these equations with a symbolic processor. Either the reader or the software stops before much progress occurs.

Relationship to DESSearch on YouTubeBookmarkSaved

DES compositionSearch on YouTubeBookmarkSaved

DES operates on 64-bit blocks of input. The book writes the DES encryption scheme as:

DES uses a 56-bit key. The key schedule calculates sixteen 48-bit subkeys. It starts with an initial permutation of 56 bits. A sequence of shifts and permutations of 48 bits follows.

Scaled-up partsSearch on YouTubeBookmarkSaved

The book draws the DES expansion as a matrix of 8 rows. Each row has 6 bits:

n32 | n1  n2  n3  n4  | n5
n4  | n5  n6  n7  n8  | n9
 .  |       .         |  .
n28 | n29 n30 n31 n32 | n1

XOR this matrix with a 48-bit subkey. Each of the 8 rows then goes into one S-box.

Quick self-testSearch on YouTubeBookmarkSaved