Data Encryption Standard (DES)

• Chapter 4 focuses on cryptographic algorithms, specifically symmetric ciphers within the DES family

Important Links

• Computer Security: Principles and Practice 4/E, by William Stallings & Lawrie Brown, Pearson Press, ISBN 10: 1-292-22061-9, ISBN 13: 978-1-292-22061-1, year 2018
• Cryptography and Network Security: Principles and Practice, 7th Edition by William Stallings, ISBN 10:1-292-15858-1 ISBN 13: 978-1-292-15858-7, year 2017
• RSA Labs (de facto) provides resources and information related to RSA cryptography
• Cryptool offers educational resources

Objectives

• Review the history of DES
• Define the basic structure of DES
• Describe building elements of DES
• Outline the process for generating round keys in DES

Introduction to DES

• Data Encryption Standard (DES) is a symmetric-key block cipher officially published by NIST
• DES employs two basic cryptography techniques: Confusion and Diffusion
• Shanan introduced the principles of confusion and diffusion, breaking dependencies and introducing randomness in the ciphertext
• Diffusion is achieved by ensuring each plaintext affects many cipher digits through permutation using a P-Box
• Confusion is reached through substitution algorithms using the XOR operation and the S-Box
• Confusion seeks to make the relationship between the ciphertext and encryption key complex, referred to as an S-P Network

General Depiction

• General depiction of DES encryption algorithm
• Diagram outlines the steps
• Key steps include but are not limited to: initial permutation, rounds of encryption (16 in total), key generation process and final permutation

Key Generation Process

• Diagram illustrates the detailed process of key generation
• Includes steps such as parity drop, shift left operations, and compression D-box to derive the round keys

Shifting

• Rounds 1, 2, 9, 16 shift one bit
• Others shift two bits

Parity-bit Drop Table

• The table outlines the parity-bit drop permutation for the key

Number of Bits Shifts

• Numerical table provides the number of bits to shift for each round in DES

Key-Compression Table

• Compression D-box changes the 58 bits to 48 bits, which are used as a key for a round

DES Overview

• DES (Data Encryption Standard) is a block cipher
• Encryption and decryption with DES diagrams demonstrate the use of a 56-bit key

DES Structure

• The encryption process is made of two permutations (P-boxes), initial and final permutations, and sixteen Feistel rounds
• A general structure of DES illustrates the initial and final permutations, the 16 rounds, and the round-key generator
• A 56-bit cipher key is used to generate 48-bit round keys

Initial and Final Permutations

• There are steps in DES
• Tables show specifics of initial and final permutation tables

Example 6.1

• Find the output of the initial permutation box when the input is given in hexadecimal as: 0x0002 0000 0000 0001
• The input has only two 1s (bit 15 and bit 64); the output must also have only two 1s (the nature of straight permutation)
• Using Table 6.1, find the output related to these two bits

Rounds in DES

• DES uses 16 rounds known as a Feistel cipher
• Function 'f' is used with right half of an incoming Key to generate the key

DES Function

• The heart of DES applies 48-bit key to the rightmost 32 bits, outputting 32 bits
• It involves an expansion P-box, XOR operation, S-Boxes, and a straight P-box

Expansion P-Box

• Since R1-1 (32 bit input) is a 32-bit input and K₁ (48 bit input Key) is a 48-bit key, expand R1-1 to 48 bits
• It uses Table 6.2 to define this P-box.

XOR

• After the expansion permutation, XOR operation on the expanded right section and the round key
• the right section and the key are 48-bits in length
• the round key is used only in this operation

S-Boxes

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

S-Box Rule

• Transformation includes the first and the last bit determining the rows
• Middle bits specify columns, outputting a 4-bit result

Table 3.3 S-box1

• Shows the permutation for S-box 1

Example 6.3

• Input to S-box 1 is 100011, output is1100

Example 6.4

• Input to S-box 8 is 000000, output is 1101

Example 3.5

• Example plaintext and key with their ciphertext counterpart

Table 3.15

• Trace of data for example 3.5

Example 3.6

• Demonstrates how Bob can decipher the ciphertext from Alice using the same key
• Shows interesting points in the ciphertex

Properties

• Two desired properties of a block cipher are the avalanche effect and the completeness
• The avalanche effect signifies that a small change in the plaintext or key should create a significant change in the ciphertext
• The completeness effect means that each bit of the ciphertext should depend on many bits of the plaintext

Design Criteria

• S-Boxes provide confusion and diffusion of bits between rounds
• P-Boxes provide diffusion of bits
• DES uses sixteen rounds of Feistel ciphers

Double DES

• Uses two keys, K1 and K2
• Perform DES on the plaintext using K1 to get encrypt text
• Again perform DES on the encrypt text using K2
• The final output is the encryption of the encrypted text
• Double DES has a 112-bit key and enciphers blocks of 64 bits

Triple DES

• Developed in 1999 by IBM, led by Walter Tuchman to prevent meet-in-the-middle
• It has a 168 bit key and enciphers blocks of 64 bits
• Triple DES uses three 64-bit keys, with a total key length of 192 bits
• The plain text block is first encrypted with k1, then encrypted with k2 and finally with the k3
• It's three times slower than DES
• Triple DES is incorporated in many products including PGP and S/MIME

International Data Encryption Algorithm (IDEA)

• IDEA is a symmetric block cipher, using a 128-bit key to encrypt data in 64-bit blocks
• It utilizes both diffusion and confusion for encryption
• The 64-bit input is divided into four portions (p1 to p4) and there are eight rounds

RC5 (Ron's Code 5)

• RC5 is designed by Ron Rivest for RSA Security 1994
• It has a variable key size, number of rounds, and size of RC5data blocks is variable
• The blocks can range from 32 to 128 bits
• The number of rounds can range from 0 to 255, with the key size ranging from 0 to 2040 bits

Problems in Symmetric Cryptography

• The major problem with symmetric cryptography is that the process of transferring keys to the recipient is prone to security risks
• Transferring keys over to the recipient via email or IRC is insecure

Asymmetric Cryptography

• Security risks involved in secret key cryptography have been overcome to a large extent in public key cryptography
• Public key cryptography uses a key pair instead of just one secret key.
• One key, known as the private key, is always kept secret by the key holder.

Security of DES

• DES, as the first block cipher, has undergone much scrutiny
• Attempted attacks: brute-force, differential cryptanalysis, and linear cryptanalysis

DES Brute Force Attack

• The brute force attack is feasible due to the relatively small key length (56 bit) and computational power
• You can break any cipher by trying all keys that possibly exist
• The time taken to break a cipher is proportional to the length of the key
• Keys are randomly generated and applied to the ciphertext until the legitimate is generated
• This key decrypts the data into its original form

Differential Cryptanalysis Attack

• Looks at pairs of ciphertexts whose plaintext have some specific differences, analyzing these differences as the plaintext propagates through the various rounds of DES when they are encrypted with the same key
• The technique chooses pairs of plaintext with a fixed difference
• Two plaintexts can be chosen at random, as long as they satisfy specific difference conditions
• Using the differences in the resulting ciphertexts, different probabilities can be assigned to different keys

Linear Cryptanalysis Attack

• Invented by Mitsuru Mastui in 1993
• If one XORs some of the plaintext bits together, XORing some ciphertext bits together, and then XORing the results, you will get a single bit that is the XOR of some of the key bits
• A large number of plaintexts/ciphertexts pairs are used to guess the values of the key bits