Upload
dhanesh-goel
View
226
Download
0
Embed Size (px)
Citation preview
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 1/74
6.1Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Chapter 6
Data Encryption Standard(DES)
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 2/74
6.2
6-1 INTRODUCTION
The Data Encryption Standard (DES) is a symmetric- key block cipher published by the National Institute of
Standards and Technology (NIST).
6.1.1 History
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).
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 3/74
6.3
DES is a block cipher, as shown in Figure 6.1.
6.1.2 Overview
Figure 6.1 Encryption and decryption with DES
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 4/74
6.4
6-2 DES STRUCTURE
The encryption process is made of two permutations
(P-boxes), which we call initial and final
permutations, and sixteen Feistel rounds.
6.2.1 Initial and Final Permutations
6.2.2 Rounds
6.2.3 Cipher and Reverse Cipher
6.2.4 Examples
Topics discussed in this section:
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 5/74
6.5
6-2 Continue
Figure 6.2 General structure of DES
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 6/74
6.6
6.2.1 Initial and Final Permutations
Figure 6.3 Initial and final permutation steps in DES
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 7/746.7
6.2.1 Continue
Table 6.1 Initial and final permutation tables
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 8/746.8
Example 6.1
6.2.1 Continued
Find the output of the initial permutation box when the input
is given in hexadecimal as:
Only bit 25 and bit 64 are 1s; the other bits are 0s. In the final
permutation, bit 25 becomes bit 64 and bit 63 becomes bit 15.
The result is
Solution
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 9/746.9
Example 6.2
6.2.1 Continued
Prove that the initial and final permutations are the inverse
of each other by finding the output of the final permutation if
the input is
The input has only two 1s; the output must also have only two
1s. Using Table 6.1, we can find the output related to these
two bits. Bit 15 in the input becomes bit 63 in the output. Bit64 in the input becomes bit 25 in the output. So the output
has only two 1s, bit 25 and bit 63. The result in hexadecimal is
Solution
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 10/746.10
DES uses 16 rounds. Each round of DES is a Feistel
cipher.
6.2.2 Rounds
Figure 6.4 A round in DES
(encryption site)
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 11/746.11
The heart of DES is the DES function. The DES function
applies a 48-bit key to the rightmost 32 bits to produce a
32-bit output.
6.2.2 Continued DES Function
Figure 6.5 DES function
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 12/746.12
Expansion P-box
Since R I−1 is a 32-bit input and K I is a 48-bit key, we first
need to expand R I−1 to 48 bits.
6.2.2 Continue
Figure 6.6 Expansion permutation
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 13/746.13
Although the relationship between the input and output
can be defined mathematically, DES uses Table 6.2 to
define this P-box.
6.2.2 Continue
Table 6.6 Expansion P-box table
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 14/746.14
Whitener (XOR)
After the expansion permutation, DES uses the XOR
operation on the expanded right section and the round
key. Note that both the right section and the key are 48-
bits in length. Also note that the round key is used only in this operation.
6.2.2 Continue
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 15/746.15
S-Boxes
The S-boxes do the real mixing (confusion). DES uses 8
S-boxes, each with a 6-bit input and a 4-bit output. See
Figure 6.7.
6.2.2 Continue
Figure 6.7 S-boxes
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 16/746.16
6.2.2 Continue
Figure 6.8 S-box rule
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 17/746.17
Table 6.3 shows the permutation for S-box 1. For the rest
of the boxes see the textbook.
6.2.2 Continue
Table 6.3 S-box 1
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 18/746.18
Example 6.3
6.2.2 Continued
The input to S-box 1 is 100011. What is the output?
If we write the first and the sixth bits together, we get 11 in
binary, which is 3 in decimal. The remaining bits are 0001 in
binary, which is 1 in decimal. We look for the value in row 3,
column 1, in Table 6.3 (S-box 1). The result is 12 in decimal,which in binary is 1100. So the input 100011 yields the output
1100.
Solution
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 19/746.19
Using mixers and swappers, we can create the cipher and
reverse cipher, each having 16 rounds.
6.2.3 Cipher and Reverse Cipher
First Approach
To achieve this goal, one approach is to make the last
round (round 16) different from the others; it has only a
mixer and no swapper.
In the first approach, there is no swapper in
the last round.
Note
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 20/746.20
6.2.3 Continued
Figure 6.9 DES cipher and reverse cipher for the first approach
d
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 21/746.21
Alternative Approach
6.2.3 Continued
We can make all 16 rounds the same by including one
swapper to the 16th round and add an extra swapper after
that (two swappers cancel the effect of each other).
Key Generation
The round-key generator creates sixteen 48-bit keys out
of a 56-bit cipher key.
6 2 3 C i d
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 22/746.22
6.2.3 Continued
Figure 6.10 Key generation
6 2 3 C i d
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 23/74
6.23
6.2.3 Continued
Table 6.12 Parity-bit drop table
Table 6.13 Number of bits shifts
6 2 3 C i d
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 24/74
6.24
6.2.3 Continued
Table 6.14 Key-compression table
6 2 4 E l
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 25/74
6.25
Example 6.5
6.2.4 Examples
We choose a random plaintext block and a random key, and
determine what the ciphertext block would be (all inhexadecimal):
Table 6.15 Trace of data for Example 6.5
6 2 4 C ti d
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 26/74
6.26
Example 6.5
Table 6.15 Trace of data for Example 6.5 (Conintued
6.2.4 Continued Continued
6 2 4 C ti d
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 27/74
6.27
Example 6.6
6.2.4 Continued
Let us see how Bob, at the destination, can decipher the
ciphertext received from Alice using the same key. Table 6.16shows some interesting points.
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 28/74
6.28
6-3 DES ANALYSIS
Critics have used a strong magnifier to analyze DES.
Tests have been done to measure the strength of some
desired properties in a block cipher.
6.3.1 Properties
6.3.2 Design Criteria
6.3.3 DES Weaknesses
Topics discussed in this section:
6 3 1 P ti
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 29/74
6.29
Two desired properties of a block cipher are the
avalanche effect and the completeness .
6.3.1 Properties
Example 6.7
To check the avalanche effect in DES, let us encrypt twoplaintext blocks (with the same key) that differ only in one bit
and observe the differences in the number of bits in each
round.
6 3 1 C ti d
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 30/74
6.30
Example 6.7
6.3.1 Continued
Although the two plaintext blocks differ only in the rightmostbit, the ciphertext blocks differ in 29 bits. This means that
changing approximately 1.5 percent of the plaintext creates a
change of approximately 45 percent in the ciphertext.
Table 6.17 Number of bit differences for Example 6.7
Continued
6 3 1 C ti d
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 31/74
6.31
6.3.1 Continued
Completeness effect
Completeness effect means that each bit of the ciphertext
needs to depend on many bits on the plaintext.
6 3 2 Design Criteria
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 32/74
6.32
6.3.2 Design Criteria
S-Boxe
The design provides confusion and diffusion of bits fromeach round to the next.
P-Boxes
They provide diffusion of bits.
Number of Rounds
DES uses sixteen rounds of Feistel ciphers. the ciphertext
is thoroughly a random function of plaintext and ciphertext.
6 3 3 DES Weaknesses
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 33/74
6.33
During the last few years critics have found some
weaknesses in DES.
6.3.3 DES Weaknesses
Weaknesses in Cipher Design
1. Weaknesses in S-boxes
2. Weaknesses in P-boxes
3. Weaknesses in Key
6 3 3 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 34/74
6.34
Example 6.8
6.3.3 Continued
Let us try the first weak key in Table 6.18 to encrypt a block
two times. After two encryptionswith the same key the original plaintext block is created. Note
that we have used the encryption algorithm two times, not
one encryption followed by another decryption.
6 3 3 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 35/74
6.35
6.3.3 Continued
Figure 6.11 Double encryption and decryption with a weak key
6 3 3 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 36/74
6.36
6.3.3 Continued
6 3 3 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 37/74
6.37
6.3.3 Continued
6 3 3 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 38/74
6.38
6.3.3 Continued
Figure 6.12 A pair of semi-weak keys in encryption and decryption
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 42/74
6.42
6-4 Multiple DES
The major criticism of DES regards its key length.
Fortunately DES is not a group. This means that we
can use double or triple DES to increase the key size.
6.4.1 Double DES
6.4.4 Triple DES
Topics discussed in this section:
6 4 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 43/74
6.43
6-4 Continued
A substitution that maps every possible input to every
possible output is a group.
Figure 6.13 Composition of mapping
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 45/74
6.45
6.4.1 Continued
Figure 6.14 Meet-in-the-middle attack for double DES
6 4 1 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 46/74
6.46
6.4.1 Continued
Figure 6.15 Tables for meet-in-the-middle attack
6 4 2 Triple DES
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 47/74
6.47
6.4.2 Triple DES
Figure 6.16 Triple DES with two keys
6.4.2 Continuous
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 48/74
6.48
6.4.2 Continuous
Triple DES with Three Keys
The possibility of known-plaintext attacks on triple DESwith two keys has enticed some applications to use triple
DES with three keys. Triple DES with three keys is used
by many applications such as PGP (See Chapter 16).
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 49/74
8.49
Chapter 8
Encipherment UsingModern Symmetric-Key
Ciphers
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 51/74
8.51
8-1 Continued
Figure 8.1 Modes of operation
8.1.1 Electronic Codebook (ECB) Mode
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 52/74
8.52
The simplest mode of operation is called the electronic
codebook (ECB) mode.
8.1.1 Electronic Codebook (ECB) Mode
Figure 8.2 Electronic codebook (ECB) mode
8.1.1 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 53/74
8.53
8.1.1 Continued
It can be proved that each plaintext block at Alice’s site is exactly
recovered at Bob’s site. Because encryption and decryption are
inverses of each other,
Example 8.1
This mode is called electronic codebook because one can
precompile 2 K codebooks (one for each key) in which each
codebook has 2 n entries in two columns. Each entry can list the
plaintext and the corresponding ciphertext blocks. However, if K
and n are large, the codebook would be far too large to precompile
and maintain.
Example 8.2
8.1.1 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 54/74
8.54
C
Assume that Eve works in a company a few hours per month (hermonthly payment is very low). She knows that the company uses
several blocks of information for each employee in which the
seventh block is the amount of money to be deposited in the
employee’s account. Eve can intercept the ciphertext sent to the
bank at the end of the month, replace the block with the
information about her payment with a copy of the block with the
information about the payment of a full-time colleague. Each
month Eve can receive more money than she deserves.
Example 8.3
8.1.1 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 55/74
8.55
Error Propagation
A single bit error in transmission can create errors in several in the corresponding block. However, the error
does not have any effect on the other blocks.
8.1.2 Cipher Block Chaining (CBC) Mode
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 56/74
8.56
In CBC mode, each plaintext block is exclusive-ored with
the previous ciphertext block before being encrypted.
p g ( )
Figure 8.3 Cipher block chaining (CBC) mode
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 58/74
8.58
It can be proved that each plaintext block at Alice’s site is
recovered exactly at Bob’s site. Because encryption and decryptionare inverses of each other,
Example 8.4
Initialization Vector (IV)
The initialization vector (IV) should be known by the
sender and the receiver.
8.1.2 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 59/74
8.59
Error Propagation
In CBC mode, a single bit error in ciphertext block C j
during transmission may create error in most bits in
plaintext block P j during decryption.
8.1.3 Cipher Feedback (CFB) Mode
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 60/74
8.60
In some situations, we need to use DES or AES as secure
ciphers, but the plaintext or ciphertext block sizes are to
be smaller.
p ( )
Figure 8.4 Encryption in cipher feedback (CFB) mode
8.1.3 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 61/74
8.61
The relation between plaintext and ciphertext blocks is
shown below:
In CFB mode, encipherment and decipherment use
the encryption function of the underlying block
cipher.
Note
8.1.3 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 62/74
8.62
CFB as a Stream Cipher
Figure 8.5 Cipher feedback (CFB) mode as a stream cipher
18.1.4 Output Feedback (OFB) Mode
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 63/74
8.63
In this mode each bit in the ciphertext is independent of
the previous bit or bits. This avoids error propagation.
Figure 8.6 Encryption in output feedback (OFB) mode
8.1.4 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 64/74
8.64
OFB as a Stream Cipher
Figure 8.7 Output feedback (OFB) mode as a stream cipher
8.1.5 Counter (CTR) Mode
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 65/74
8.65
In the counter (CTR) mode, there is no feedback. The
pseudorandomness in the key stream is achieved using a counter.
Figure 8.8 Encryption in counter (CTR) mode
8.1.5 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 66/74
8.66
Figure 8.9 Counter (CTR) mode as a stream cipher
8.1.5 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 67/74
8.67
Comparison of Different Modes
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 68/74
8.68
8-2 USE OF STREAM CIPHERS
Although the five modes of operations enable the use of block ciphers for encipherment of messages or files
in large units and small units, sometimes pure stream
are needed for enciphering small units of data such as
characters or bits.
8.2.1 RC4
8.2.2 A5/1
Topics discussed in this section:
8.2.1 RC4
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 69/74
8.69
RC4 is a byte-oriented stream cipher in which a byte (8
bits) of a plaintext is exclusive-ored with a byte of key to produce a byte of a ciphertext.
State RC4 is based on the concept of a state.
8.2.1 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 70/74
8.70
Figure 8.10 The idea of RC4 stream cipher
8.2.2 A5/1
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 71/74
8.71
A5/1 (a member of the A5 family of ciphers) is used in the
Global System for Mobile Communication (GSM), a network for mobile telephone communication..
Figure 8.11 General outline of A5/1
8.2.2 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 72/74
8.72
Key Generator
A5/1 uses three LFSRs with 19, 22, and 23 bits.
Figure 8.12 Three LFSR’s in A5/1
8.2.2 Continued
7/31/2019 Week7 DES+Mode
http://slidepdf.com/reader/full/week7-desmode 73/74
8.73
At a point of time the clocking bits are 1, 0, and 1. Which LFSR is
clocked (shifted)?
Example 8.7
Solution
The result of Majority (1, 0, 1) = 1. LFSR1 and LAFS3 are shifted,
but LFSR2 is not.