Question

Suppose that at round \(i\) in DES, \(L_{i-1}\) is all 0 s, \(R_{i-1}\) is (in hex) deadbeef, and \(K_{i}\) is a5bd96 860841 . Give \(R_{i}\), assuming that we use a simplified \(\mathrm{S}\) box that reduces each 6-bit chunk to 4 bits by dropping the first and last bits.

Short answer

R_i = c529f68

Step-by-step solution

- Convert Hex Values to Binary

Convert the given hex values to binary. For the value of \(R_{i-1} = \text{deadbeef}\), which is in hex, convert it to its binary equivalent. Similarly, convert the key \(K_i = \text{a5bd96}\) to binary. You should get:\(R_{i-1}\) in binary: 11011110101011011011111011101111\(K_i\) in binary: 101001011011110110010110

- Feistel Function

Apply the Feistel function. For this step, expand \(R_{i-1}\) from 32 bits to 48 bits according to the expansion function of DES. Then XOR the expanded \(R_{i-1}\) with the key \(K_i\). Note that the expansion function, XOR, and exact expansion may vary. Here, assume \(E \rightarrow\) Expansion: 01101111010100111010100101010101010101101101111 Perform XOR with \(K_i = 101001011011110110010110\): Result: 1110101010100001010111110011000100001

- Simplified S-box Mapping

Split the XOR result into 6-bit chunks (6-bit each for mapping with simplified S-box) and drop the first and last bits of every 6-bit chunk to get new 4-bit chunks. Simplified mapping results in the following transformations: 111010 -> 1100 (drop 1 and 0) 101010 -> 0101 (drop 1 and 1) 000101 -> 0010 (drop 0 and 1) 011111 -> 1111 (drop 0 and 1) 001100 -> 0110 (drop 0 and 0) 0100001 -> 1000 (drop 0 and 1)

- Combine Substitution Results

Combine the substituted 4-bit results from the simplified S-box: 1100 0101 0010 1111 0110 1000 = R_i in binaryConvert this combined binary R_i result into its hex form: R_i = c529f68

Key concepts

Data Encryption Standard (DES)

The Data Encryption Standard, or DES, is a symmetric key algorithm used for encryption. It transforms plaintext into ciphertext through a series of steps, thus ensuring data security.
DES works with 64-bit blocks of data, using a 56-bit key, which is expanded into 16 subkeys, one for each round of encryption.
The transformation involves complex operations like permutations, substitutions, and bit manipulations, making it challenging to crack without the key.
The core structure of DES is built upon the Feistel Cipher, adding layers of security over the plaintext data. Understanding DES' inner workings helps in grasping its robustness despite its deprecation in favor of more secure algorithms like AES.

Feistel Cipher

A Feistel Cipher is the heart of DES. This structure allows DES to both encrypt and decrypt using the same operations.
Here's how it works:

• Each round of the cipher splits the data into two halves.
• The right half goes through a complex function (in DES, this is the expansion, substitution (S-boxes), and permutation).
• The result from the function is XORed with the left half, and then they swap places for the next round.

This process ensures that even a small change in the input or key drastically alters the resulting ciphertext, a concept known as diffusion.

S-box

The S-box, or substitution box, is a crucial element in the DES function. It introduces non-linearity by transforming the input bits into output bits through a predefined box of substitutions.
In DES, there are 8 S-boxes, each taking a 6-bit input and mapping it to a 4-bit output.
This mapping scrambles the bits thoroughly and is designed to resist cryptanalysis, adding a layer of security.
In simplified exercises, like given in our problem, certain bits might be dropped to size up the results, but the core concept remains the same.

Hexadecimal to Binary Conversion

One of the initial steps in solving the DES exercise involves converting hexadecimal values to binary.
Hexadecimal (hex) is a base-16 number system, often used in computing as a more human-friendly representation of binary-coded values.
Each hex digit represents 4 binary digits (bits). For example, the hex value 'deadbeef' converts to binary as follows:

• d = 1101
• e = 1110
• a = 1010
• d = 1101
• b = 1011
• e = 1110
• e = 1110
• f = 1111

The resulting binary string becomes 11011110101011011011111011101111.

Bit Manipulation

Bit manipulation is a fundamental part of working with DES and other encryption algorithms.
It involves altering individual bits within a binary number, using operations like AND, OR, XOR, shifts, and rotations:

• XOR (exclusive OR): Used in DES to combine bits of data with the key bits, flipping bits which differ in the two inputs.
• Shifts: Moving bits left or right within the binary representation. For example, shifting left by 1 bit is equivalent to multiplying by 2.
• AND/OR: Combining bits to perform bitwise operations, setting or clearing specific bits.

In encryption, these manipulations help in creating complex, non-linear relationships between the plaintext, key, and ciphertext, ensuring security and confusion.