17crypto_L06
Feistal Ciphers and DES
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
1
Feistel Ciphers
� A family of single key, block substitution ciphers.
� Feistel was in charge of the IBM Lucifer project (1973),
and provided the theoretical underpinning for many of the
first block ciphers.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
2
first block ciphers.
�His work was based on Shannon (1945)
� He proposed 64-bit or 128-bit block sizes.
Feistel Cipher Keys
� The key is the mapping between input and output blocks.
� If all possible mappings are possible then the keys would
be 1021 bits long for a block size of 64.
�Stirling’s approximation of 64!.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
3
�Stirling’s approximation of 64!.
� There are thus a lot of possible keys.
� The actual size of the key space was reduced, with a key
length of 128 bits.
Product Ciphers
� Feistel used a product cipher.
�Several small transformations are applied one after the
other.
� He alternated substitutions and permutations.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
4
� He alternated substitutions and permutations.
� The resulting large transformation is likely to be much
harder to break than each of the individual transformations.
� Each substitution used a sub-key, which is generated from
the main or master key.
Feistel Structure
� The initial data block is split into two halves, the left (L)
and right (R) halves.
�So that actual operations involve just one half of each
data block, and so fewer bits.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
5
data block, and so fewer bits.
�This speeds up data processing. Blocks can be larger
than the computer word length, which was 32 bits in
that era.
� There are a number of rounds, each making a substitution
followed by swapping the two halves.
Feistal Rounds
Initial Permutation
for i = 1 to n (number of rounds)
{
Li = Li-1 ⊕ F(Ri-1, Ki)i i-1 i-1 i
Ri = Ri-1
Swap (Li, Ri)
}
Reverse the Initial Permutation
� F is any function, there are several different Feistel algorithms. Ki is
a sub key, ⊕ is exclusive or.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
6
Decryption
� Decryption follows the same steps, but with the sub keys
used in the reverse order.
� Thus the same algorithm and key is used for encryption
and decryption.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
7
� To prove this works, all we need do is show that two
applications of each substitution step, with the same key,
cancel each other.
� Clearly two permutation steps, swapping left and right
halves, cancel each other.
Proof: Two Substitutions Cancel
� Let us represent the substitution process as
(L0, R0) � (L1, R1)
� Then a further application can be written as
(L , R ) � (L , R )
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
8
(L1, R1) � (L2, R2)
� All we need do is show that L2=L0 and R2=R0
Proof (2)
� Applying the Feistel function gives
L1 = L0 ⊕ F(R0, K); R1 = R0
L2 = L1 ⊕ F(R1, K); R2 = R1
� Clearly R = R .
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
9
� Clearly R2 = R0.
� L2 = L1 ⊕ F(R1, K)
= L0 ⊕ F(R0, K) ⊕ F(R0, K)
= L0 ⊕ 0, since a ⊕ a = 0
= L0, since a ⊕ 0 = a
Criteria for the Design of F
� No output bit is close to a linear function of a subset of the
input bits.
� If they were it would be vulnerable to a chosen plain text
attack (linear cryptanalysis).
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
10
�Choose several plain text messages whose bits form a
linear combination.
�Solve the linear equations.
� There is no bias towards some bit positions.
� If two different inputs (key or data) differ by 1 bit, the
output must differ by at least two bits.
�Confusion and diffusion.
DES
� DES stands for Data Encryption Standard.
� It is now an older algorithm but still widely used.
� It is a Feistel block cipher, working with 64 bit data blocks
and 56 bit keys.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
11
and 56 bit keys.
S-DES
� We can understand how it works by studying a toy system
S-DES developed by Edward Schaefer of the University of
Santa Clara.
� S-DES encrypts 8 bit blocks of data using a 10 bit key.� S-DES encrypts 8 bit blocks of data using a 10 bit key.
� Sample data
Data = 01101011
Key = 1011000110
� There are two substitution rounds, each with its own sub-
key.
� Left and right halves are swapped between them.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
12
The Initial Permutation
� The initial permutation operates on the 8-bit data blocks.
� If the data bits are numbered 0..7 then the initial
permutation is 15203746.
� Data is now 00111110
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
13
� Data is now 00111110
� The inverse permutation applied at the end of the process
is 30246175.
Sub Key Generation
� Two 8 bit sub keys are generated from the 10 bit master key.
1. The bits of the original key are permuted as 2416390875
01100 01110
2. The left 5 bits and the right 5 bits are both rotated left 1 bit.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
14
11000 11100
3. The first 8 bit sub key is formed from the following bits: 52637498
K1 = 1010 1000
4. The left and right 5 bits from step 2 are both rotated left 2 bits
00011 10011
5. The second 8 bit sub key is formed from the same bits as step 3.
K2 = 1001 1111
The Function F has 5 steps
1. Expansion of 4 data bits (right half of block) to 8 bits as 30121230
01111101
2. These 8 bits are xored with the 8 bits of the key.
10101000 (key)
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
15
11010101
3. The resulting 8 bits (numbered 01234567) are treated as 4 separate 2
bit numbers called row1, col1, row2, col2. Row and column indices
row1 = bits-03, col1 = bits-12, row2 = bits-47, col2 = bits-56.
(11, 10) : (01, 10)
In decimal, row1 = 3, col1 = 2, row2 = 1, col2 = 2.
The S-Boxes
4. (row1,col1) and (row2,col2) form the row and column indices of two
4×4 tables called S-boxes.
�Each S-box produces 2 bits of output.
�An S-box is a matrix, indexed by the row and column.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
16
�See next slide for details of the S-boxes.
�S1(3, 2) = 00, S2(1, 2) = 01
�So output = 0001
5. The resulting 4 bit number, the output from the 2 s-boxes undergoes
another permutation 1320, producing the output from F.
0100
Details of the S-Boxes
� Here are the two S-boxes, containing 2 bit numbers
� The output two bits are written as an integer in the
following 2 tables.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
17
S1 S2
1 0 3 2 0 1 2 3
3 2 1 0 2 0 1 3
0 2 1 3 3 0 1 2
3 1 0 2 2 1 0 3
Relationship with DES
� DES has the same structure as S-DES, but with more steps.
� There are 16 FK steps, each with a 48 bit sub key generated from the
56 bit actual key.
� The function F operates on 32 bit halves of the data.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
18
�The data is expanded to 48 bits and xored with the sub key.
�These 48 bits are split into 8 chunks, each 6 bits long.
�Each 6 bit chunk is treated as row (2 bits) and column (4 bits)
�They each index an S-box.
� Internally it has 8 S-Boxes, each 4 x 16.
�Each S-Box produces a 4 bit number.
Results from Applying 16 steps in DES
� The following table lists the number of bits that have
changed after each round of DES with
�two very similar plain text blocks (diffusion).
�two very similar keys (confusion).
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
19
�two very similar keys (confusion).
� Clearly diffusion and confusion is quite effective.
� Permutations on their own do not effect confusion or
diffusion.
�A 1 bit change in the origin only changes one bit in the
destination.
16 steps: Number of Different Bits
Round Confusion Diffusion
1 6 2
2 21 14
3 35 28
4 39 32
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
20
4 39 32
10 44 38
11 32 31
12 30 33
13 30 28
14 29 34
15 29 34
16 34 35
Design of the S-Boxes
� The design principles were published in 1992, answering questions
that NSA had introduced a trap door.
� The design made DES resistant to differential cryptanalysis, which
NSA had known about but kept secret.
� Other Feistel ciphers were vulnerable to differential analysis.� Other Feistel ciphers were vulnerable to differential analysis.
� Differential Cryptanalysis uses two very similar chosen plaintext
messages to uncover details of the encryption algorithm.
� Linear cryptanalysis is a similar attack that relies on two similar known
plaintext messages. DES is also resistant to it.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
21
Double DES
� Double DES uses two different keys to encrypt twice.
�C = EK2(EK1(P))
� It is vulnerable to a known plaintext (assume P and C are
known) meet in the middle attack.
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
22
known) meet in the middle attack.
� Construct a lookup table of all intermediate results
X = EK1(P) for all possible keys K1.
� Decrypt C for all possible keys K2: Y = DK2(C).
� The key we want is when X = Y.
� Look up each value of Y in the table of X’s.
� This takes about twice the effort needed to break the
standard single key DES.
Three Key Triple DES
� Three Key Triple DES
�C = EK3 ( DK2(EK1(P)))
�No known weaknesses.
�Decryption with the second key is used so that if the
Crpto & SecDev 2017 © Ron Poet:
Lecture 5
23
�Decryption with the second key is used so that if the
same key is used three times then this is equivalent to
single DES.
� There are 3 options:
�K1, K2, K3 are all different – 168 bit key
�K1 = K3, K2 different – 112 bit key avoiding meet in the middle.
�K1 = K2 = K3 – 56 bit key, equivalent to single DES.