MODULE-1
Chapter-2
TRADITIONAL BLOCK CIPHER
STREAM CIPHER & BLOCK CIPHER
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 autokeyed Vigenère cipher and the Vernam
cipher.
In the ideal case, a one-time pad version of the Vernam cipher would be used in which the
keystream (ki) is as long as the plaintext bit stream (pi).
If the cryptographic keystream is random, then this cipher is unbreakable by any means other
than acquiring the keystream.
However, the keystream must be provided to both users in advance via some independent
and secure channel. This introduces insurmountable logistical problems if the intended data
traffic is very large.
Accordingly, for practical reasons, the bit-stream generator must be implemented as an
algorithmic procedure, so that the cryptographic bit stream can be produced by both users.
In this approach the bit-stream generator is a key-controlled algorithm and must produce a bit
stream that is cryptographically strong.
That is, it must be computationally impractical to predict future portions of the bit stream based
on previous portions of the bit stream.
The two users need only share the generating key, and each can produce the keystream.
A block cipher is one in which a block of plaintext is treated as a whole and used
to produce a ciphertext block of equal length.
Typically, a block size of 64 or 128 bits is used.
As with a stream cipher, the two users share a symmetric encryption key
A block cipher encrypts a plaintext block of n bits into a ciphertext block of n bits.
There are 2ⁿ possible plaintext blocks, and encryption must be reversible
(nonsingular) so that each plaintext maps to a unique ciphertext (ensuring
decryption is possible).
Reversible mapping → One plaintext ↔ One ciphertext.
Irreversible mapping → Multiple plaintexts map to the same ciphertext →
decryption not possible.
For n = 2, the number of possible reversible transformations is 2^(2ⁿ) = 2^(4) = 16.
A general substitution cipher for n = 4 maps each of 16 plaintexts to one of 16
ciphertexts. This is called the ideal block cipher, offering maximum mappings.
Problem:
With small block sizes, the system becomes equivalent to classical substitution
ciphers.
These are vulnerable to statistical attacks.
Weakness arises from small block size, not from substitution itself.
Solution:
Use larger block sizes.
With large n, reversible substitutions make statistical attacks infeasible because
plaintext–ciphertext patterns are well hidden.
Difference between stream and
block cipher
Stream Cipher Block Cipher
Encrypts 1 bit or 1 byte at a time. Encrypts data in fixed-size blocks (e.g., 64 or 128
Uses a keystream (random or pseudo- bits).
random). Same key applied to each block.
Example: Vernam, RC4. Examples: AES, DES.
One-time pad (ideal) → perfectly secure, Requires padding if plaintext length ≠ block size.
but impractical (key distribution issue). More suited for file encryption, data at rest.
Algorithmic generator solves practicality Slower than stream ciphers for small data or real-
→ short key expands to long keystream. time use.
Fast, low memory, good for real-time Strong security when used with modes of operation
data (voice, video). (CBC, CTR, etc.).
Vulnerable if keystream is reused.
THE FEISTAL CIPHER
Feistel proposed [FEIS73] that we can approximate the ideal block cipher by utiliz-
ing the concept of a product cipher, which is the execution of two or more simple ciphers in sequence in
such a way that the final result or product is cryptographically stronger than any of the component
ciphers.
The essence of the approach is to develop a block cipher with a key length of k bits and a block length of n
bits, allowing a total of 2^k possible transformations, rather than the 2n! transformation available with the
ideal block cipher.
Feistel proposed the use of a cipher that alternates substitutions and permutations, where these
terms are defined as follows:
■ Substitution: Each plaintext element or group of elements is uniquely replaced by a
corresponding ciphertext element or group of elements.
■ Permutation: A sequence of plaintext elements is replaced by a permutation of that sequence.
That is, no elements are added or deleted or replaced in the sequence, rather the order in which the
elements appear in the sequence is changed.
The terms diffusion and confusion were introduced by Claude Shannon to capture
the two basic building blocks for any cryptographic system
1. Diffusion
Meaning: Spread the influence of a single plaintext bit over many ciphertext bits.
Goal: Hide statistical structure of the plaintext so that patterns (like frequency of letters) do
not show up in ciphertext.
How: Achieved through permutations, substitutions, and mixing operations in ciphers.
Example: In AES, the ShiftRows and MixColumns operations provide diffusion. Changing 1 bit
of plaintext alters many bits in the ciphertext.
Analogy: A drop of ink diffuses in water — spreads out everywhere, making it hard to trace the
origin.
2. Confusion
Meaning: Make the relationship between the key and the ciphertext as complex as possible.
Goal: Prevent attackers from guessing the key even if they analyze large amounts of
ciphertext.
How: Achieved mainly through substitution operations.
Example: In AES, the SubBytes (S-box) step introduces confusion by replacing input bits with
nonlinear mappings.
Analogy: Mixing a puzzle so much that the original arrangement (the key) is extremely hard to
deduce.
In diffusion, the statistical structure of the plaintext is dissipated
into long-range statistics of the ciphertext.
In a binary block cipher, diffusion can be achieved by repeatedly
performing some permutation on the data followed by applying a
function to that permutation;
On the other hand, confusion seeks to make the relationship
between the statistics of the ciphertext and the value of the
encryption key as complex as possible, again to thwart attempts to
discover the key. Thus, even if the attacker can get some handle
on the statistics of the ciphertext, the way in which the key was
used to produce that ciphertext is so complex as to make it
difficult to deduce the key.
This is achieved by the use of a complex substitution algorithm.
THE FEISTAL CIPHER STRUCTURE
Fistel Cipher Structure The left-hand side of Figure 3.3 depicts
the structure proposed by Feistel. The inputs to the encryption
algorithm are a plaintext block of Length 2w bits and a key K. The
plaintext block is divided into two halves, L0 and R0.
The two halves of the data pass through n rounds of processing
and then combine to produce the ciphertext block. Each round i
has as inputs Li- 1 and Ri- 1 derived from the previous round, as
well as a subkey Ki derived from the overall K. In general, the
subkeys Ki are different from K and from each other. In Figure 3.3,
16 rounds are used, although any number of rounds could be
implemented
All rounds have the same structure. A substitution is performed
on the left half of the data. This is done by applying a round
function F to the right half of the data and then taking the
exclusive-OR of the output of that function and the left half of
the data.
The round function has the same general structure for each
round but is parameterized by the round subkey Ki. Another way
to express this is to say that F is a function of right-half block of w
bits and a subkey of y bits, which produces an output value
THE FEISTAL DECRYPTION ALGORITHM
The process of decryption with a Feistel cipher is essentially the same as the encryption
process.
The rule is as follows:
Use the ciphertext as input to the algorithm, but use the subkeys Ki in reverse
order. That is, use Kn in the first round, Kn- 1 in the second round, and so on, until
K1 is used in the last round. This is a nice feature, because it means we need not
implement two different algorithms; one for encryption and one for decryption.
To see that the same algorithm with a reversed key order produces the correct result,
Figure 3.3 shows the encryption process going down the left-hand side and the
decryption process going up the right-hand side for a 16-round algorithm.
For clarity, we use the notation LEi and REi for data traveling through the encryption
algorithm and LDi and RDi for data traveling through the decryption algorithm. The
diagram indicates that, at every round, the intermediate value of the decryption process is
equal to the corresponding value of the encryption process with the two halves of the
value swapped.
After the last iteration of the encryption process, the two halves of the
output are swapped, so that the ciphertext is RE16 || LE16. The output of
that round
is the ciphertext. Now take that ciphertext and use it as input to the
same algorithm.
The input to the first round is RE16 || LE16, which is equal to the 32-bit
swap of the output of the sixteenth round of the encryption process
THE DATA ENCRYPTION STANDARD
The algorithm itself is referred to as the Data Encryption Algorithm (DEA).For
DEA, data are encrypted in 64-bit blocks using a 56-bit key. The algorithm
transforms 64-bit input in a series of steps into a 64-bit output. The same steps,
with the same key, are used to reverse the encryption.
DES ENCRYPTION
As with any encryption scheme, there are two inputs to the encryption function: the
plaintext to be encrypted and the key. In this case, the plaintext must be 64 bits in
length and the key is 56 bits in length.
Looking at the left-hand side of the figure, we can see that the processing of the
plaintext proceeds in three phases. First, the 64-bit plaintext passes through an
initial permutation (IP) that rearranges the bits to produce the permuted input.
This is followed by a phase consisting of sixteen rounds of the same function,
which
involves both permutation and substitution functions.
The output of the last (sixteenth) round consists of 64 bits that are a function of
the input plaintext and the
key.
The left and right halves of the output are swapped to produce the preoutput.
Finally, the preoutput is passed through a permutation [IP-1] that is the inverse of
the initial permutation function, to produce the 64-bit ciphertext.
With the exception of the initial and final permutations, DES has the exact
structure of a Feistel cipher, as shown in Figure 4.3.
The right-hand portion of Figure 4.5 shows the way in which the 56-bit key is
used. Initially, the key is passed through a permutation function.
Then, for each of the sixteen rounds, a subkey (Ki) is produced by the
combination of a left circular shift and a permutation. The permutation function
is the same for each round, but a different subkey is produced because of the
repeated shifts of the key bits.
THE AVALANCHE EFFECT
A desirable property of any encryption algorithm is that a small
change in either the plaintext or the key should produce a
significant change in the ciphertext.
In particular, a change in one bit of the plaintext or one bit of
the key should produce a change in many bits of the
ciphertext.
This is referred to as the avalanche effect.
If the change were small, this might provide a way to reduce
the size of the plaintext or key space to be searched.
USE OF 56-BIT KEY THE STRENGTH OF DES
With a key length of 56 bits, there are 256 possible keys, which is approximately
7.2 * 1016 keys. Thus, on the face of it, a brute-force attack appears impractical.
Assuming that, on average, half the key space has to be searched, a single
machine performing one DES encryption per microsecond would take more
than a thousand years to break the cipher.
NATURE OF DES ALGORITHM
Another concern is the possibility that cryptanalysis is possible by exploiting the
characteristics of the DES algorithm. The focus of concern has been on the eight
substitution tables, or S-boxes, that are used in each iteration
TIMING ATTACKS
a timing attack is one in which information about the key or the plaintext is obtained
by observing how long it takes a given implementation to perform decryptions on
various ciphertexts.
A timing attack exploits the fact that an encryption or decryption algorithm often
takes slightly different amounts of time on different inputs.
BLOCK CIPHER DESIGN PRINCIPLES
Three critical aspects of block cipher design: the number of rounds, design of the
function F, and key scheduling.
NUMBER OF ROUNDS
The greater the number of rounds, the more difficult it is to perform cryptanalysis,
even for a relatively weak F. In general, the criterion should be that the number of
rounds is chosen so that known cryptanalytic efforts require greater effort than a
simple brute-force key search attack.
If DES had 15 or fewer rounds, differential cryptanalysis would require less effort
than a brute-force key search.
DESIGN OF THE FUNCTION F
The heart of a Feistel block cipher is the function F, which provides the element of
confusion in a Feistel cipher. Thus, it must be difficult to “unscramble” the substitution
performed by F.
One obvious criterion is that F be nonlinear, as we discussed previously. The more
nonlinear F, the more difficult any type of cryptanalysis will be.
BLOCK CIPHER DESIGN PRINCIPLES
KEY SCHEDULING
With any Feistel block cipher, the key is used to generate one subkey for each
round.
In general, we would like to select subkeys to maximize the difficulty of deducing
individual subkeys and the difficulty of working back to the main key.
A more stringent version of this is the strict avalanche criterion (SAC) which states
that any output bit j of an S-box should change with probability 1/2 when any
single input bit i is inverted for all i, j.
Another criterion proposed is the bit independence criterion (BIC), which states
that output bits j and k should change independently when any single input bit i is
inverted for all i, j, and k.
The SAC and BIC criteria appear to strengthen the effectiveness of the confusion
function.
At minimum, the key schedule should guarantee key/ciphertext Strict Avalanche
Criterion and Bit Independence Criterion.
Thank You