MODERN BLOCK CIPHER

Udit Mishra
Allenhouse Institute of Technology
 Outline
• Introduction
• Definition
• Substitution or transposition
• Full size key ciphers
• Partial size key ciphers
• Components of modern block cipher
– P-boxes
• Straight P-box
• Compression P-box
• Expansion P-box
– S-boxes
• Linear & nonlinear S-boxes

Modern Block Cipher | Udit Mishra 2

 Introduction
• The traditional symmetric key ciphers are character-oriented
ciphers.
• With the advent of the computer, we need bit-oriented
ciphers.
• Reason: because the information to be encrypted is not just
text; it can be numbers, graphics, audio & video data.
• It is convenient to convert these types of data into a stream
of bits, to encrypt the stream, and then to send the encrypted
stream.
• When text is treated at bit level, each character is replaced
by 8 (or 16) bits, which means that number of symbols
becomes 8 (or 16) times larger.

Modern Block Cipher | Udit Mishra 3

 Definition
• A symmetric key modern block cipher encrypts an n-bit
block of plaintext or decrypts an n-bit block of ciphertext.
• The encryption or decryption algorithm uses a k-bit key.
• The decryption algorithm must be inverse of the encryption
algorithm & both operations must use the same secret key
so that Bob can retrieve the message sent by Alice.

n-bit plaintext n-bit plaintext

Encryption k-bit key Decryption

n-bit ciphertext n-bit ciphertext

Modern Block Cipher | Udit Mishra 4

 Definition (Conti…)
• If message has fewer than n-bits, padding must
be added to make it an n-bit block.
• If the message has more than n-bits, it should
be divided into n-bits blocks and the
appropriate padding must be added to the last
block if necessary.
• The common values for n are 64,128,256, or
512 bits.

Modern Block Cipher | Udit Mishra 5

 Substitution or Transposition
• If the cipher is designed as a substitution
cipher, a 1-bit or 0-bit in the plaintext can be
replaced by either a 0 or a 1.
plaintext: 0110 1001 1001 0110
ciphertext: 0100 0111 1011 0111
• Hence, plaintext and ciphertext can have
different numbers of 1’s.

Modern Block Cipher | Udit Mishra 6

Substitution or Transposition (conti…)
• If the cipher is designed as a transposition
cipher, the bits are only reordered (transposed).
plaintext: 0110 1001 1001 0110
ciphertext: 1101 0101 0100 0011
• Hence, there is the same number of 1’s in the
plaintext and in the ciphertext.
• In either case, the no. of n-bits possible
plaintexts or ciphertexts is 2^n.

Modern Block Cipher | Udit Mishra 7

 Exercise
• Suppose that we have a block cipher where
n=64. If there are 10 1’s in the ciphertext, how
many trial & error tests does Eve need to do to
recover the plaintext from the intercepted
ciphertext in each of the following case?
– The cipher is designed as a substitution cipher.
– The cipher is designed as a transposition cipher.

Modern Block Cipher | Udit Mishra 8

 Exercise Conclusion
• To be resistant to exhaustive-search attack, a
modern block cipher needs to be designed as
substitution cipher.

Modern Block Cipher | Udit Mishra 9

 Full Size Key Ciphers
• Transposition Ciphers:
– Involves rearrangement of bits, without changing
value.
– Consider an n bit cipher, how many such
rearrangements are possible: n!
– How many key bits are necessary: ceil[log (n!)] 2

Modern Block Cipher | Udit Mishra 10

 Full Size Key Ciphers (Conti…)
• Substitution Ciphers:
– It does not transpose bits, but substitutes values
– Can we model this as a permutation?
– Yes. The n bit inputs and outputs can be
represented as 2^n bit sequences, with one 1 and
the rest 0’s.
– This can be thus modeled as a transposition.
– Thus it is a permutation of 2n values, thus needs
ceil[log (2^n!)] bits.
2

Modern Block Cipher | Udit Mishra 11

 Exercise
• Consider a 3-bit block ciphers. How many bits
are needed for the full-size key?
– Transposition cipher:
• ceil(log26)=3 bits.
– Substitution cipher:
• There are 8!=40,320 possible substitutions
• Thus there are ceil(log2(40,320))=16 bits

Modern Block Cipher | Udit Mishra 12

 Partial Size Key Ciphers
• Actual ciphers cannot use full size keys, as the
size is large.
– Consider DES, with 64 bit block cipher.
• Size of full key= ceil(log2 (2^64!))≈270
• Much large compared to 56 bits which are actually used.
• A partial size key cipher is a group under the
composition operation if it is a subgroup of the
corresponding full size key cipher.

Modern Block Cipher | Udit Mishra 13

 Keyless Ciphers
• Practically useless by itself.
• Are used as components of keyed ciphers.
• Types of keyless ciphers:
– Keyless transposition cipher
– Keyless substitution cipher
– -----------------------------------------------------

Modern Block Cipher | Udit Mishra 14

 Components of a Modern Block
Cipher
• A modern block cipher is made of a
combination of:
– Transposition units(P-boxes)
– Substitution units (S-boxes)
– Some other units

Modern Block Cipher | Udit Mishra 15

 P-Box (Permutation Box)
• A P-box parallels the traditional transposition
cipher for characters.
• It transposes bits.
• There are 3 types:
– Straight P-box
– Compression P-box
– Expansion P-box

Modern Block Cipher | Udit Mishra 16

P-Box(Conti…)

Modern Block Cipher | Udit Mishra 17

 P-Box(Conti…)
• Although a P-box can use a key to define one of
the n! mappings, P-boxes are normally keyless,
which means that the mapping is predetermined.
• There are 2 cases:
– If the P-box is implemented in h/w, it is prewired.
– If it is implemented in s/w, a permutation table shows
the rule of mapping.
• In second case, entries in the table are the inputs
& the positions of the entries are the outputs.
Modern Block Cipher | Udit Mishra 18
 Example of a permutation table for a straight P-box

58 50 42 34 26 18 10 02 60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06 64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01 59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05 63 55 47 39 31 23 15 07

Modern Block Cipher | Udit Mishra 19

 Compression P-Boxes
• A P-box with n inputs & m outputs (where m<n)
• Some of the inputs are blocked & do not reach the
output.
• A permutation table for a compression P-box has
m entries, but the content of each entry is from 1
to n with some missing values.
• These are used when we need to permute bits &
the same time decrease the no. of bits for the next
stage.
Modern Block Cipher | Udit Mishra 20
 Example of a 32x24 permutation table

• Table shows an example of a permutation table

for a 32x24 compression P-box.
• Here, note that input 7,8,9,15,16,23,24, & 25
are blocked.
01 02 03 21 22 26 27 28 29 13 14 17
18 19 20 04 05 06 10 11 12 30 31 32

Modern Block Cipher | Udit Mishra 21

 Expansion P-Boxes
• A P-box with n inputs & m outputs (where m>n).
• Some of the inputs are connected to more than
one inputs.
• A permutation table for an expansion P-box has m
entries, but m-n of the entries are repeated.
• These are used when we need to permute bits &
the same time increase the no. of bits for the next
stage.

Modern Block Cipher | Udit Mishra 22

 Example of a 12x16 permutation table
• Table shows an example of a permutation table
for a 12x16 expansion P-box.
• Here, note that for each of the input 1,3,9, &
12 is mapped to two outputs.

01 09 10 11 12 01 02 03 03 04 05 06 07 08 09 12

Modern Block Cipher | Udit Mishra 23

 S-Box (Substitution Box)
• An S-box can have a different numbers of
inputs & outputs.
• The input to an S-box could be an n-bit word,
but the output can be a m-bit word.
• Where m & n are not necessarily the same.
• Modern block ciphers normally use keyless S-
boxes, where the mapping from the inputs to
the outputs are predetermined.

Modern Block Cipher | Udit Mishra 24

 Linear & Nonlinear S-Boxes
• In an S-box with n inputs & m outputs, let inputs be x1,x2,y3,………,xn &
the outputs be y1,y2,y3,………,yn.
• The relationship b/w the inputs & the outputs can be represented as a set of
equations:
y1 = f1(x1,x2,x3,…….,xn)
y2 = f1(x1,x2,x3,…….,xn)
.
.
ym = f1(x1,x2,x3,…….,xn)
In the linear S-box, this can be represented as:
y1 = a1,1x1 ExOR a1,2x2 ExOR ……… ExOR a1,nxn
y2 = a2,1x1 ExOR a2,2x2 ExOR ……… ExOR a2,nxn
.
.
y1 = am,1x1 ExOR am,2x2 ExOR ……… ExOR am,nxn
In a nonlinear S-box we cannot have the above relations for every output.

Modern Block Cipher | Udit Mishra 25

Modern Block Cipher | Udit Mishra 26