Module 3: Block Cipher Principles – Stream Ciphers and Block

Ciphers, Feistel Cipher, Feistel Decryption algorithm,

The Data encryption standard, DES Decryption - Avalanche

effect,

E
EG
The AES Cipher, substitute bytes transformation, Shift row
transformation, Mix Column Transformation

LL
CO
G
IN
ER
NE
GI

Bushara A R
EN

AP, ECE
KMEA ENGG COLLEGE
EA
KM
Stream Ciphers and Block Ciphers

★ A stream cipher is one that encrypts a digital data

stream one bit or one byte at a time.
★ Examples of classical stream ciphers are the auto keyed

E
Vigenère cipher and the Vernam cipher.

EG
★ A block cipher is one in which a block of plaintext is

LL
treated as a whole and used to produce a ciphertext block of
equal length.

CO
★ Typically, a block size of 64 or 128 bits is used.

G
IN
ER
NE
GI

Block Cipher Schemes

EN

There are a vast number of block ciphers schemes that are in use. Many of them are
publically known. Most popular and prominent block ciphers are listed below.
EA

Digital Encryption Standard (DES) − The popular block cipher of the 1990s. It is now
considered as a ‘broken’ block cipher, due primarily to its small key size.
KM

Advanced Encryption Standard (AES) − It is a relatively new block cipher based on the
encryption algorithm Rijndael that won the AES design competition.
Feistel Cipher

E
EG
➢ Feistel Cipher is not a specific scheme of block cipher.
➢ It is a design model from which many different block

LL
ciphers are derived.

CO
➢ DES is just one example of a Feistel Cipher.
➢ A cryptographic system based on Feistel cipher structure
uses the same algorithm for both encryption and decryption.

G
IN
ER

Encryption Process
NE

The encryption process uses the Feistel structure consisting of

multiple rounds of processing of the plaintext, each round
GI

consisting of a “substitution” step followed by a “permutation”

EN

step.
EA
KM
Feistel Structure is shown in the following illustration −

E
EG
LL
CO
G
IN
ER
NE
GI
EN
EA

❖ The input block to each round is divided into two halves

that can be denoted as L and R for the left half and the right
KM

half.
❖ In each round, the right half of the block, R, goes through
unchanged. But the left half, L, goes through an operation that
depends on R and the encryption key.

E
❖ First, we apply an encrypting function ‘f’ that takes two

EG
inputs − the key K and R. The function produces the output

LL
f(R,K). Then, we XOR the output of the mathematical function
with L.

CO
❖ In real implementation of the Feistel Cipher, such as DES,

G
instead of using the whole encryption key during each round,
IN
a round-dependent key (a subkey) is derived from the
ER

encryption key. This means that each round uses a different

NE

key, although all these subkeys are related to the original key.
❖ The permutation step at the end of each round swaps the
GI

modified L and unmodified R. Therefore, the L for the next

EN

round would be R of the current round. And R for the next

EA

round will be the output L of the current round.

Above substitution and permutation steps form a ‘round’.
KM

❖
The number of rounds are specified by the algorithm design.
❖ Once the last round is completed then the two sub blocks,
‘R’ and ‘L’ are concatenated in this order to form the ciphertext
block.

E
Decryption Process

EG
LL
★ The process of decryption in Feistel cipher is almost

CO
similar. Instead of starting with a block of plaintext, the
ciphertext block is fed into the start of the Feistel structure

G
and then the process thereafter is exactly the same as
IN
described in the given illustration.
ER

★ The process is said to be almost similar and not exactly

NE

the same. In the case of decryption, the only difference is that

GI

the subkeys used in encryption are used in the reverse order.

EN

★ The final swapping of ‘L’ and ‘R’ in the last step of the
Feistel Cipher is essential. If these are not swapped then the
EA

resulting ciphertext could not be decrypted using the same

KM

algorithm.
 Data Encryption Standard (DES Encryption &
Decryption)

★ The algorithm is designed to encipher and decipher blocks

E
of data consisting of 64 bits under control of a 64-bit key

EG
★ A block to be enciphered is subjected to an initial
permutation IP and then to a complex key-dependent

LL
computation and finally to a permutation which is the inverse
of the initial permutation IP-1.

CO
G
IN
ER
NE
GI
EN
EA
KM
★ First, the 64-bit plaintext passes through an initial
permutation(IP) that rearranges the bits to produce the
permuted output.

E
★ This is followed by a phase consisting of 16 rounds of the

EG
same function, which involves both permutation and
substitution function.

LL
★ The output of the last round consists of 64 bits that are
a function of the input plain text and the key.

CO
★ The left and right halves of the output are swapped to
produce the pre output.

G
IN
★ Finally, the pre output is passed through a permutation
that is inverse of the initial permutation function,to produce
ER

the 64-bit cipher text.

NE

★ The right hand portion of the figure shows the way in

which the 56- bit key is used.
GI

★ Initially, the key is passed through a permutation

EN

function.
★ Then for each of the 16 rounds, a subkey (Ki) is produced
EA

by the combination of a left circular shift and a permutation.

The permutation function is the same for each round, but
KM

different subkeys are produced because of the repeated shifts

of the key bits.
 INITIAL PERMUTATION
★ Initial permutation and its inverse are defined as,

E
EG
LL
CO
G
IN
ER

❖The input to the table contains a permutation of 64 bits

numbered from 1 to 64.
NE

❖ The IP replaces the first bit of the original plain text block
GI

with the 58th bit of the original plain text block.

❖ The second bit with the 50th bit of the original plain text
EN

block and so on.

EA

• The permutation X = IP (M)

• The inverse permutation
KM

Y = IP-1(X) = IP-1(IP(M))
 Details of Single Round

E
EG
LL
CO
G
IN
ER
NE

• Fig. Shows the internal structure of a single round.

GI

•Each of the 16 rounds consists of,

EN

key transformation
EA

Expansion Permutation
S- box substitution
KM

P- box permutation
XOR and Swap
[Link] transformation:
•The initial 64-bit key is transformed into a 56- bit key by
discarding every 8th bit of the initial key.
• From this 56 key, a different 48-bit sub key is generated
during each round using the process called key
transformation.

E
•For this, the 56 key is divided into two halves,

EG
each of 28 bits.
These halves are circularly shifted left by one or two

LL
positions, depending on the round.
Eg:

CO
If the round number is 1,2,9 or 16, the shift is
done by only position.

G
For the other rounds, the circular shift is done by two
positions.
IN
ER

(c) Schedule of Left Shifts

───────────────────────────────
NE

Round number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Bits rotated 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
GI

After the shift,bit number 14 moves into the first position, bit
number 17 moves into the second position and so on.
EN

The table contains only 48 positions. Bit number 18 is

discarded, like other 7 to reduce the 56 bit key to a 48 bit key.
EA

Since the key transformation process involves permutation as

KM

well as selection of a 48 bit sub set of the original 56 bit key,

it is called as compression permutation
Permuted Choice Two (PC-2)

14 17 11 24 1 5 3 28
15 6 21 10 23 19 12 4
26 8 16 7 27 20 13 2
41 52 31 37 47 55 30 40
 51 45 33 48 44 49 39 56
34 53 46 42 50 36 29 32

2. Expansion Permutation
After initial permutation,we had two 32 bit plain text areas,
Left Plain Text and Right Plain Text.

E
EG
During Expansion permutation, the RPT is expanded from 32
bits to 48 bits, the bits are permuted as well.

LL
1. The 32 bit RPT is divided into 8 blocks, with each block

CO
consisting of 4 bits.
2. Each 4 bit block of the previous step is expanded to a

G
corresponding 6 bit block.
IN
ER

1 2 3 4 5 6 7 8 . . 29 30 31 32
NE

32 1 2 3 4 5 4 5 6 7 8 9 . 28 29 30 31 32 1
GI
EN

Expansion Permutation (E)

EA

32 1 2 3 4 5
4 5 6 7 8 9
KM

8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
3. S- box substitution
It is a process that accepts the 48 bit input from the XOR
operation involving the compressed key and expanded RPT and

E
produces a 32 bit output using the substitution technique.

EG
The substitution is performed by eight substitution boxes (s
boxes).

LL
Each of the eight S boxes has 6 bit input and a 4 bit output.

CO
The 48 bit input block is divided into 8 sub blocks and each
such sub block is given to an S box.

G
IN
ER
NE
GI
EN
EA
KM
•Every S box contains 4 rows (numbered from 0 to 3) and 16
columns(numbered from 0 to 16).
•We have 8 tables, one for each S- box.
•At the intersection of every row and column, a 4 bit number

E
is present.

EG
•S-box
•The first and last bits of the

LL
input to box Si to select a row

CO
•The middle 4 bits select a column.
•ex : in S1, input＝110011,
the row is 11,

G
the column is 1001
IN
=> output：0110
ER
NE
GI
EN
EA
KM
 E
EG
LL
CO
G
IN
ER
NE
GI

•
EN

P- box permutation
The output of the S- box consists of 32 bits.
EA

These 32 bits are permuted using a P- box.

KM

A 16 in the first block indicates that the bit at the

position 16 of the original input moves to bit at position 1 in
the output.
XOR and SWAP
● The left half portion of the initial 64 bit plain text block is
 XORed with the output produced by P- box permutation.
● The result of this XOR operation becomes the new right half.
● The old right half becomes the new left half, in a process of
swapping.

E
EG
Final Permutation

LL
●At the end of the 16 rounds, the final permutation is
performed.

CO
● This is simple transposition, the 40th input bit takes the
position of the 1st output bit and so on.
G
IN
DES Decryption
ER

● The same algorithm used for encryption in DES also works

for decryption.
NE

●The values of the various tables and the operations as well as

the sequence are carefully chosen so that the algorithm is
GI

reversible.
EN

●The only difference between the encryption and decryption

process is the reversal of key portions.
EA

●If the original key K was divided into K1, K2....K16 for the 16
encryption rounds, then for decryption, the key should be used
KM

as K16, K15...K1.

❖
 Avalanche effect
DES Analysis
The DES satisfies both the desired properties of block
cipher. These two properties make cipher very strong.

E
❖Avalanche effect − A small change in plaintext

EG
results in a very great change in the ciphertext.
❖Completeness − Each bit of ciphertext depends on

LL
many bits of plaintext.

CO
❖Avalanche effect
❖A small change in plaintext results in a very great
change in the ciphertext.
G
❖it quantifies the effect on the cipher-text with
IN
respect to the small change made in plain text or
ER

the key
Eg : Plain Text : 0000 0000 0000 0000
NE

Cipher Text: 34A2 05DC A34B C32A

GI

Plain Text : 0000 0000 0000 0001

EN

Cipher Text: 64A9 98DC B24C 892C

★ If a cryptographic algorithm does not exhibit the

EA

avalanche effect, then a cryptanalyst can analyze

the ciphertext and make predictions about the
KM

plaintext.
★ The avalanche effect is significant to prevent
cryptanalysts from making predictions about the
input partially or entirely.
AES (Advanced Encryption Standard)
AES Cipher, substitute bytes transformation, Shift row
transformation, Mix Column Transformation

E
EG
★ AES is a symmetric block cipher
★ designed by Rijmen-Daemen in Belgium

LL
★ has 128/192/256 bit keys, 128 bit data
★an iterative rather than feistel cipher

CO
★ treats data in 4 groups of 4 bytes
★ operates an entire block in every round

G
IN
ER
NE
GI
EN
EA
KM

Fig:Data structures in the AES algorithm

 E
EG
LL
CO
G
IN
ER
NE
GI

AddRoundKey
EN

The four stages are as follows:

1. Substitute bytes
EA

2. Shift rows
3. Mix Columns
KM

4. Add Round Key

 AddRoundKey
•Each round uses four different words
from the expanded key array.

E
•Each column in the state matrix is XORed

EG
with a different word.

LL
•The heart of encryption. All other
functions’ properties are permanent and

CO
known to all.

G
IN
ER
NE
GI
EN
EA

InvAddRoundKey
KM

•Key is used in reverse order

 Substitution Byte (Subbyte)
★ It is a bytewise lookup process that returns a
4-byte word in which each byte is the result of
applying the Rijndael S-box.

E
★ Simple substitution of each byte using one table

EG
of 16x16 bytes containing a permutation of all 256
8-bit values

LL
★ each byte of state is replaced by byte in row (left

CO
4-bits) & column (right 4-bits)
★ eg. byte {95} is replaced by row 9 col 5 byte
which is the value {2A}
G
IN
ER
NE
GI
EN
EA
KM
KM
EA
EN
GI
NE
ER
IN
SubBytes Table

G
CO
LL
EG
E
KM
EA
EN
GI
NE
ER
IN
G
InvSubBytes Table

CO
LL
EG
E
 Shift Rows
•a circular byte shift in each row
–1st row is unchanged

E
–2nd row does 1 byte circular shift to left

EG
–3rd row does 2 byte circular shift to left

LL
–4th row does 3 byte circular shift to left

CO
•decrypt does shifts to right

G
•since state is processed by columns, this
IN
step permutes bytes between the
ER

columns
NE
GI
EN
EA
KM
 E
EG
LL
Mix Columns
❖ This stage (known as MixColumn) is basically

CO
a substitution but it makes use of arithmetic
of GF(2^8).
❖ Each column is operated on individually. Each
G
byte of a column is mapped into a new value
IN
that is a function of all four bytes in the
column.
ER

❖ The transformation can be determined by

the following matrix multiplication on state
NE
GI
EN
EA
KM
KM
EA
EN
GI
NE
ER
IN
G
CO
LL
EG
E
 E
EG
LL
CO
G
IN
ER

AES Encryption Round

AES Decryption
NE

★ AES decryption is not identical to

GI

encryption since steps done in reverse

EN

★ but can define an equivalent inverse cipher

with steps as for encryption
EA

–but using inverses of each step

–with a different key schedule
KM

•works since result is unchanged when

–swap byte substitution & shift rows
–swap mix columns & add (tweaked) round key