Unit II Symmetric Key Ciphers

SDES
BLOCK CIPHER PRINCIPLES
DES
DIFFERENTIAL AND LINEAR CRYPTANALYSIS
BLOCK CIPHER DESIGN PRINCIPLES
BLOCK CIPHER MODE OF OPERATION
AES
RC4
KEY DISTRIBUTION
SDES(Simplified DES)
 What is Simplified DES
• Developed 1996 as a teaching tool
– Santa Clara University
• Prof. Edward Schaefer
– Takes an 8-bit block plaintext, a 10 –bit key and
produces an 8-bit block of ciphertext
– Decryption takes the 8-bit block of ciphertext,
the same 10-bit key and produces the original
8-bit block of plaintext
 S-DES Scheme
Encryption
Decryption
P10
8-bit plaintext 8-bit plaintext

SHIFT
IP IP - 1
P8
K1 K1
fk fk

SHIFT
SW SW

K2 P8 K2
fk fk

IP - 1 IP

8-bit ciphertext 8-bit ciphertext

 Five Functions to Encrypt
• IP – an initial permutation

• fk - a complex, 2-input function

• SW – a simple permutation that swaps the two nybles

• fk - a complex, 2-input function; again

• IP – inverse permutation of the initial permutation

 IP

4
Encryption Detail
E/P
8 K1
4
4 4

S0 S1
2 2
P4 4
SW

E/P
K2

S0 S1

P4

I P -1
Initial Permutation (IP)‫‏‬
Move the bits of the original character around a little…

k1 k2 k3 k4 k5 k6 k7 k8

k2 k6 k3 k1 k4 k8 k5 k7
 Expansion/Permutation (E/P)‫‏‬
Expand 4 bits into 8 and permutate them…

k1 k2 k3 k4

k4 k1 k2 k3 k2 k3 k4 k1
 Key Generation
10

P10
5 5

LS-1 LS-1
5 5

P8
8
K1

LS-2 LS-2
5 5
P8
8
K2
P10 Permutation

k1 k2 k3 k4 k5 k6 k7 k8 k9 k10

k3 k5 k2 k7 k4 k10 k1 k9 k8 k6
P8 Permutation
Permutate 10 into 8

k1 k2 k3 k4 k5 k6 k7 k8 k9 k10

k6 k3 k7 k4 k8 k5 k10 k9
 LS-1
Left circular shift 1 each 5 bit group

k3 k 5 k 2 k 7 k 4 k10 k1 k9 k8 k6

k5 k 2 k 7 k 4 k 3 k1 k9 k8 k6 k10
 LS-2
Left circular shift 2 each 5 bit group

k3 k 5 k 2 k 7 k 4 k10 k1 k9 k8 k6

k2 k7 k4 k3 k5 k9 k8 k6 k10 k1
 Substitution Boxes

S0 S1

1 0 3 2 0 1 2 3
3 2 1 0 2 0 1 3
0 2 1 3 3 0 1 0
3 1 3 2 2 1 0 3
Block Cipher Principles
 Stream Ciphers And Block Ciphers

Stream Cipher:
It is one that encrypts a digital data stream one
bit or one byte at a time.
Eg: Vignere Cipher and the Vernam Cipher

Block Cipher:
It is one in which a block of plaintext is treated
as a whole and used to produce a ciphertext
block of equal length.
Typically block size will be 64 or 128 bits
Stream Cipher
BLOCK CIPHER
BLOCK CIPHER PRINCIPLES
Motivation for the Feistel Cipher Structure:
n-bit block cipher takes n-bit plaintext and
produces n-bit ciphertext
2ⁿ possible different plaintext blocks
Encryption must be reversible(decryption
possible)
Each plaintext block must produce unique
ciphertext block
Total transformation is 2ⁿ!
 Feistel cipher - introduction
• Claude Shannon introduced idea of substitution-permutation

(S-P) networks in 1949

• form basis of modern block ciphers

• S-P nets are based on the two primitive cryptographic

operations seen before:

– substitution(S-box)

– permutation(P-box)

 Provide confusion & diffusion of message & key

 Confusion and Diffusion

• Cipher needs to completely obscure statistical properties of

original message a one-time pad does this
• more practically Shannon suggested combining S & P
elements to obtain:
– Diffusion– dissipates statistical structure of plaintext
over bulk of ciphertext
– Confusion– makes relationship between ciphertext and
key as complex as possible
 Feistel Cipher Structure
• Horst Feistel devised the Feistel cipher
• Based on concept of invertible product cipher
partitions input block into two halves
• Process through multiple rounds which perform a
substitution on left data half based on round
function of right half & subkey
• Then have permutation swapping halves
implements Shannon’s S-P net concept
 Feistel Cipher Design Elements
Design Elements Description
Block size increasing size improves security, but slows
cipher
Key size increasing size improves security, makes
exhaustive key searching harder, but may slow
cipher
Number of rounds increasing number improves security, but slows
cipher
Subkey generation greater complexity can make analysis harder, but
algorithm slows cipher
Round function greater complexity can make analysis harder, but
slows cipher
Fast software more recent concern for practical use
en/decryption
Ease of analysis for easier validation & testing of strength
Feistel Decryption Algorithm
• First, consider the encryption process. We see
that
LE16 = RE15
RE16 = LE15 x F(RE15, K16)

• On the decryption side,

LD1 = RD0 = LE16 = RE15
RD1 = LD0 x F(RD0, K16)
= RE16 x F(RE15, K16)
= [LE15 x F(RE15, K16)] x F(RE15, K16)
• The XOR has the following properties:
[A x B] x C = A x [B x C]
DxD=0
Ex0=E
• Thus, we have LD1 = RE15 and RD1 = LE15. Therefore, the
output of the first round of the decryption process is
LE15||RE15, which is the 32-bit swap of the input to the
sixteenth round of the encryption.
• This correspondence holds all the way through the 16
iterations, as is easily shown. We can cast this process in
general terms. For the ith iteration of the encryption
algorithm,
LEi = REi-1
REi =LEi-1 x F(REi-1, Ki)
• Rearranging terms,
REi-1 = LEi
LEi-1 = REi x F(REi-1, Ki2 = REi x F(LEi, Ki)
 DES
(Data Encryption Standard)
 Introduction

• The most widely used block cipher in world

• It was adopted in 1977 by NBS (now NIST)
– as FIPS PUB 46

• It encrypts 64-bit data using 56-bit key

• It has widespread use
• It has been considerable controversy over its security
DES Encryption Overview
 Encryption (cont.)

64-bit plaintext (X)

Initial Permutation (IP)

64-bit key (K)

Key i
Round (i) Key Generation (KeyGen)

32-bit Switch (SW)

Inversion of Initial Permutation (IP-1)

64-bit ciphertext (Y)
 DETAILS OF SINGLE ROUND

As in any classic Feistel cipher, the overall processing

at each round can be summarized in the following formulas:

Li = Ri-1
Ri = Li-1 x F(Ri-1, Ki)
 Initial Permutation
To see that these two permutation functions where Mi is a binary digit. Then the
are indeed the inverse of each other, consider permutation X = IP(M) is as follows:
the following 64-bit input M:
After initial permutation next step it
goes to round 1. the below diagram
shows the each round
Expansion permutation
 goes to permuted choice 2 (ie) key
generation. the below diagram shows the
key generation
Permuted choice 1
After pc 1 next step goes to left shift
Left shift
Next step pc2
Permutated choice 2
After initial permutation next step it
goes to round 1. the below diagram
shows the each round
 Encryption (Round) (cont.)
F

S-box

[1]
 ENCRYPTION (ROUND) (CONT.)
 S-box
ENCRYPTION (ROUND) (CONT.)
 Separate plaintext as L0R0
 L0: left half 32 bits of plaintext
 R0: right half 32 bits of plaintext

F
 Expansion/permutation: E( )
 Substitution/choice: S-box( )

 Permutation: P( )

Ri  Li 1 ~ P ( S _ box ( E ( Ri 1 ) ~ Keyi ))
Li  Ri 1
 Key Generation (cont.)
• Original Key: Key0
• Permuted Choice One: PC_1( )
• Permuted Choice Two: PC_2( )
• Schedule of Left Shift: SLS( )

(C0 , D0 )  PC _ 1( Key 0 )
(Ci , Di )  SLS (Ci 1 , Di 1 )
Keyi  PC _ 2( SLS (Ci 1 , Di 1 ))
 Decryption
• The same algorithm as
encryption.
• Reversed the order of key
(Key16, Key15, … Key1).
• For example:
– IP undoes IP-1 step of
encryption.
– 1st round with SK16 undoes
16th encrypt round.

[1]
 Strength of DES

• Criticism
– Reduction in key size of 72 bits
• Too short to withstand with brute-force attack
– S-boxes were classified.
• Weak points enable NSA to decipher without key.
• 56-bit keys have 256 = 7.2 x 1016 values
– Brute force search looks hard.
– A machine performing one DES encryption per
microsecond would take more than a thousand year to
break the cipher.
 Strength of DES (cont.)

• Avalanche effect in DES

– If a small change in
either the plaintext or
the key, the ciphertext
should change markedly.
• DES exhibits a strong
avalanche effect.
Differential And Linear Cryptanalysis
 Differential cryptanalysis

• One of the most significant recent advances in

cryptanalysis.
• Know by NSA in 70's cf DES design
• Murphy ,Biham & Shamir published in 90's
• Powerful method to analyse most current block
ciphers with varying degrees of success.
 Differential cryptanalysis attack
• Differential cryptanalysis attack is complex.
• Consider the original plaintext block m to consist of two
halves m0,m1.
• Each round of DES maps the right-hand input into left-
hand output and sets the right-hand output to a function
of left-hand input and subkey for this round.
• If we label each new block mi(2<=i<=17),then the
intermediate message halves are related as follows:

• i=1,2,…....,16
Differential cryptanalysis attack(cont)

• In differential cryptanalysis ,we start with two

messages ,m and m' ,with a known XOR
difference and consider the difference
between the intermediate message
halves: .Then we
have
 Linear cryptanalysis
• A more recent development
• This attack is based on finding linear approximation to
describe the transformations performed in DES.
• It is also a statistical method.
• Must be iterated over rounds,with
decreasing probabilities.
• Gives linear equation for key bits.
 Linear cryptanalysis(cont)
• For a cipher with n-bit plaintext and ciphertext blocks and
an m-bit key ,let the plaintext block be labeled
P[1],…......P[n],ciphertext blocks C[1],…..C[n] and the
key K[1],…....K[m].Then define
Differential
propagation through
three round
charactertistic DES
Block Cipher Design Principles

DES DESIGN CRITERIA

NUMBER OF ROUNDS
DESIGN OF FUNCTION F
KEY SCHEDULE ALGORITHM
 DES Design Criteria
• 7 criteria for S-Boxes provided for:
• No Output bit of any S-Box
• Each row of S-Box should include all 16 possible output bit
combinations.
• If 2 i/p to an S-Box differ in exactly one bit, then o/p differ in at
least 2 bits.
• If 2 i/p to an S-Box differ in 2 middle bit exactly, then o/p differ in
at least 2 bits.
• If 2 i/p to an S-Box differ in first 2 bits and are identical in their
last 2 bits, then 2 o/p must not same.
• For any nonzero 6 bit difference b/w i/p, no more than 8 of the
32 pairs of i/p exhibiting that difference may result in the same
o/p difference
• This is a criterion similar to the previous one, but for the case of
3 S-Boxes
• 3 criteria for Permutation P provided for:
• Increased diffusion
• Middle bits
NUMBER OF ROUNDS

• More is better, make exhaustive search the best

attack opinion.
• The criterion should be that the no. of rounds is
chosen so that known cryptanalytic efforts
require greater effort than a simple brute – force
search attack.
• This criterion is attractive, because it makes it ea
sy
to judge the strength of an algorithm and to
compare different algorithms
DESIGN OF FUNCTION F

• Design criteria for F

• strict avalanche criterion (SAC)
• bit independence criterion (BIC)
• provides “confusion”, is nonlinear, avalanche
• issues of how S-boxes are selected
• S-box Design
• Random
• Random with testing
• Human-made
• Math-made
KEY SCHEDULE ALGORITHM

• complex subkey creation, key avalanche

Block Cipher Mode Of Operations
 Introduction
 block ciphers encrypt fixed size blocks
 e.g., DES encrypts 64-bit blocks
 need some way to en/decrypt arbitrary amounts of data in
practice
 NIST SP 800-38A defines 5 modes
 have block and stream modes
 to cover a wide variety of applications
 can be used with any block cipher
TYPES:
• Electronic Codebook Book (ECB)
• Cipher Block Chaining (CBC)
• Cipher FeedBack (CFB)
• Output FeedBack (OFB)
• Counter (CTR)
Electronic Codebook Book (ECB)
 Cipher Block Chaining (CBC)
 message is broken into blocks
 linked together in encryption operation
 each previous cipher block is chained with current
plaintext block, hence name
 use Initial Vector (IV) to start process
Ci = EK(Pi XOR Ci-1)
C-1 = IV
 IV prevents same P from making same C
 uses: bulk data encryption, authentication
 Cipher FeedBack (CFB)
 message is treated as a stream of bits
 added to the output of the block cipher
 result is feed back for next stage (hence name)
 standard allows any number of bits (1,8, 64 or 128 etc) to
be feed back
 denoted CFB-1, CFB-8, CFB-64, CFB-128, etc.

 most efficient to use all bits in block (64 or 128)

Ci = Pi XOR EK(Ci-1)
C-1 = IV
 uses: stream data encryption, authentication
 Output FeedBack (OFB)
 message is treated as a stream of bits
 output of cipher is added to message
 output is then feed back (hence name)
Oi = EK(Oi-1)
Ci = Pi XOR Oi
O-1 = IV
 feedback is independent of message
 can be computed in advance
 uses: stream encryption on noisy channels
Why noisy channels?
 Counter (CTR)
 a “new” mode, though proposed early on
 similar to OFB but encrypts counter value rather than
any feedback value
Oi = EK(i)
Ci = Pi XOR Oi
 must have a different key & counter value for every
plaintext block (never reused)
 again, OTP issue

 uses: high-speed network encryptions

Double des
&
Triple des
 Double des
• ENCRYPTION: C=E K2[ E K1 [P] ]

P=D K1[ D K2 [C] ]

• DECRYPTION:
TRIPLE DES
MEET IN THE MIDDLE ATTACK
TRIPLE DES WITH 2 KEYS
TRIPLE DES WITH 3 KEYS
 AES
(Advanced Encryption Standard)
 AES Origins

 clear a replacement for DES was needed

 have theoretical attacks that can break it
 have demonstrated exhaustive key search attacks
 can use Triple-DES – but slow, has small blocks
 US NIST issued call for ciphers in 1997
 15 candidates accepted in Jun 98
 5 were shortlisted in Aug-99
 Rijndael was selected as the AES in Oct-2000
 issued as FIPS PUB 197 standard in Nov-2001
 The AES Cipher - Rijndael

 designed by Rijmen-Daemen in Belgium

 has 128/192/256 bit keys, 128 bit data
 an iterative rather than Feistel cipher
 processes data as block of 4 columns of 4 bytes
 operates on entire data block in every round
 designed to have:
 resistance against known attacks
 speed and code compactness on many CPUs
 design simplicity
AES Encryption Process
 AES Structure
 Block size-128 bit plain text / 4 words / 16 bytes
 No. of rounds – 10 rounds
 Key size – 128 bit / 4 words / 16 bytes
 No. of subkeys – 44 subkeys
 Each subkey size – 32 bit / 1 word / 4 bytes
 Each round – 4 subkeys / 128 bit / 4 words / 16 bytes
 Before applying round function - 4 subkeys / 128 bit / 4 words /
16 bytes
 Substitute Bytes

 a simple substitution of each byte

 uses one table of 16x16 bytes containing a
permutation of all 256 8-bit values
 each byte of state is replaced by byte indexed by row
(left 4-bits) & column (right 4-bits)
 eg. byte {95} is replaced by byte in row 9 column 5
 which has value {2A}
 S-box constructed using defined transformation of
values in GF(28)
 designed to be resistant to all known attacks
Substitute Bytes
Substitute Bytes Example
 Shift Rows
 a circular byte shift in each each
 1st row is unchanged
 2nd row does 1 byte circular shift to left
 3rd row does 2 byte circular shift to left
 4th row does 3 byte circular shift to left
 decrypt inverts using shifts to right
 since state is processed by columns, this step
permutes bytes between the columns
Shift Rows
 Mix Columns
 each column is processed separately
 each byte is replaced by a value dependent on
all 4 bytes in the column
 effectively a matrix multiplication in GF(28)
using prime poly m(x) =x8+x4+x3+x+1
Mix Columns
Mix Columns Example
 Add Round Key
 XOR state with 128-bits of the round key
 again processed by column (though effectively
a series of byte operations)
 inverse for decryption identical
 since XOR own inverse, with reversed keys
 designed to be as simple as possible
 a form of Vernam cipher on expanded key
 requires other stages for complexity / security
Add Round Key
AES Round
 AES Key Expansion
 takes 128-bit (16-byte) key and expands into
array of 44/52/60 32-bit words
 start by copying key into first 4 words
 then loop creating words that depend on
values in previous & 4 places back
 in 3 of 4 cases just XOR these together
 1st word in 4 has rotate + S-box + XOR round
constant on previous, before XOR 4th back
AES Key Expansion
AES Example
Avalanche
 AES Decryption
 AES decryption is not identical to encryption
since steps done in reverse
 but can define an equivalent inverse cipher
with steps as for encryption
 but using inverses of each step
 with a different key schedule
 works since result is unchanged when
 swap byte substitution & shift rows
 swap mix columns & add (tweaked) round key
RC4
 RC4

Developed by RSA Labs, RC4 is a symmetric, byte-oriented

stream cipher with a variable length key size, in which a
byte (8 bits) of a plaintext is exclusive-ored with a byte of
key to produce a byte of a ciphertext.
KEY
RC4 HAS two main parts: ksa
KSA (Key Scheduling Algorithm)
PRGA (Pseudo Random Generation Algorithm) PRGA

K
State
P + C
RC4 is based on the concept of a state.

8.110
 Figure 8.10 The idea of RC4 stream cipher

KSA

PRGA

8.111
 RC4 Key Schedule KSA

Starts with an array S of numbers: 0..255

􀁺 Use key to truly shuffle S
􀁺 S forms internal state of the cipher
􀁺 Given a key k of length L bytes

Scrambling Pseudocode :
for i = 0 to 255 do
S[i] = i
j=0
for i = 0 to 255 do
j = (j + S[i] + k[i ]) (mod 256)
swap (S[i], S[j])
8.112
 RC4 PRGA and Encryption

Encryption involves XORing data bytes with output of the

PRGA

􀁺 The PRGA initializes i and j to 0 and then loops over 4 basic

operations: increase j, increase j using s[i], swap and output
s[i]+s[j]

􀁺 PRGA Pseudocode is:

i=j=0
for each message byte Mi
i = (i + 1) (mod 256)
j = (j + S[i]) (mod 256)
swap(S[i], S[j])
t = (S[i] + S[j]) (mod 256) ; Ki = S[t]
Encryption : Ci = Mi XOR S[t]

8.113
 RC4 Encryption Example

Lets consider the stream cipher RC4, but instead

of the full 256 bytes, we will use 8 x 3-bits.
That is, the state vector S is 8 x 3-bits.
We will operate on 3-bits of plaintext at a time
since S can take the values 0 to 7, which can be
represented as 3 bits.
Assume we use a 4 x 3-bit key of K = [1 2 3 6].
And a plaintext P = [1 2 2 2]

8.114
 RC4 PRGA and Encryption
The first step is to generate the stream.
Initialise the state vector S and temporary vector T. S is initialised so
the S[i] = i, and T is initialised so it is the key K (repeated as
necessary).
S = [0 1 2 3 4 5 6 7]
T = [1 2 3 6 1 2 3 6]
Now perform the initial permutation on S.
j = 0;
for i = 0 to 7 do
j = (j + S[i] + T[i]) mod 8
Swap(S[i],S[j]);
end
For i = 0:
j = (0 + 0 + 1) mod 8 = 1
Swap(S[0],S[1]);
S = [1 0 2 3 4 5 6 7]

8.115
 RC4 PRGA and Encryption

For i = 1:
j=3
Swap(S[1],S[3])
S = [1 3 2 0 4 5 6 7];

For i = 2:
j=0
Swap(S[2],S[0]);
S = [2 3 1 0 4 5 6 7];

For i = 3:
j = 6;
Swap(S[3],S[6])
S = [2 3 1 6 4 5 0 7];

8.116
 RC4 PRGA and Encryption
For i = 4:
j=3
Swap(S[4],S[3])
S = [2 3 1 4 6 5 0 7];
For i = 5:
j=2
Swap(S[5],S[2]);
S = [2 3 5 4 6 1 0 7];
For i = 6:
j = 5;
Swap(S[6],S[4])
S = [2 3 5 4 0 1 6 7];
For i = 7:
j = 2;
Swap(S[7],S[2])
S = [2 3 7 4 0 1 6 5];
Hence, our initial permutation of S = [2 3 7 4 0 1 6 5];

8.117
 RC4 PRGA and Encryption
Now we generate 3-bits at a time, k, that we XOR with each 3-bits of
plaintext to produce the ciphertext. The 3-bits k is generated by:
i, j = 0;
while (true) {
i = (i + 1) mod 8;
j = (j + S[i]) mod 8;
Swap (S[i], S[j]);
t = (S[i] + S[j]) mod 8;
k = S[t]; }

The first iteration:

S = [2 3 7 4 0 1 6 5]
i = (0 + 1) mod 8 = 1
j = (0 + S[1]) mod 8 = 3
Swap(S[1],S[3])
S = [2 4 7 3 0 1 6 5]
t = (S[1] + S[3]) mod 8 = 7
k = S[7] = 5
Remember, P = [1 2 2 2]
8.118
 RC4 PRGA and Encryption

Remember, P = [1 2 2 2]
So our first 3-bits of ciphertext is obtained by: k XOR P
5 XOR 1 = 101 XOR 001 = 100 = 4

The second iteration:

S = [2 4 7 3 0 1 6 5]
i = (1 + 1 ) mod 8 = 2
j = (2 + S[2]) mod 8 = 1
Swap(S[2],S[1])
S = [2 7 4 3 0 1 6 5]
t = (S[2] + S[1]) mod 8 = 3
k = S[3] = 3
Second 3-bits of ciphertext are:
3 XOR 2 = 011 XOR 010 = 001 = 1
8.119
 RC4 PRGA and Encryption
After 4 iterations:
To encrypt the plaintext stream P = [1 2 2 2] with key
K = [1 2 3 6] using our simplified RC4 stream cipher we
get C = [4 1 2 0].
(or in binary: P = 001010010010, K = 001010011110
and C = 100001010000)
Simplified

8.120
Key Distribution
 KEY DISTRIBUTION

A key distribution center is a form of symmetric

encryption that allows the access of two or more
systems in a network by generating a unique ticket
type key for establishing a secure connection over
which data is shared and transferred.
1 A can select a key and physically deliver it to B.
2 A third party can select the key and physically deliver
it to
AandB
3 if A and B have previously and recently used a key
one party can transmit the new key to the other ,
encrypted the old key.
4 if A and B each has an encrypted connection to a
third party C, C can deliver a key on the encrypted link
to A and B.
If N hosts [N(N-1)]/2
A KEY DISTRIBUTION SCENARIO