Introduction to Block Ciphers

In simple words, block ciphers divides the message into fixed size length blocks (AES for example uses 128-bit blocks) and encrypts that. Opposed to that, a stream cipher encrypts a message bit by bit.

Stream Ciphers

In a stream cipher, we provide a key to the bit-stream generation algorithm to
produce a stream of pseudorandom numbers. We then XOR the output of the
bit-stream generator with our message to produce our ciphertext. Since XOR
is an involuntary operator, XORing the ciphertext stream with the generator
bit-stream gives us back the plaintext.

The heart of a stream cipher lies in its bit-stream generator algorithm. A
generator is cryptographically secure if given the output of the generator
without the key, we cannot predict the next bit of the output. That is, given
the first k bits of a random sequence, there is no polynomial-time algorithm that can predict the (k + 1)th bit with probability of success non-negligibly better than 50%

Block Ciphers

A block cipher takes a block of plaintext bits and generates a block of cipher-
text bits, generally of same size. The size of block is fixed in the given scheme.
The choice of block size does not directly affect to the strength of encryption
scheme. The strength of cipher depends up on the key length and its overall
construction.

Let us assume that we are working with block size of n. We have a message m
of size n and a key k of size |k| and we get a ciphertext c of size n.

There are a few desired properties of block ciphers:

1. Given k it is easy to encrypt and decrypt messages.
2. Given m, c is is very hard to compute k such that e(k,m) = c
3. The encryption algorithm is a trapdoor function. It means that it is easy
   to compute in one direction, but very difficult to compute in opposite
   direction without special information called the trapdoor. Here the key
   k is our trapdoor.
4. The decryption scheme should be deterministic. d(k, e(k, m)) = m

Structural Design of Block Ciphers

We take a look at a block ciphers from two viewpoints: their structural design
and as mathematical objects.

Concept of Confusion and Diffusion

This concept was first introduced by Claude Shannon in his Communication
Theory of Secrecy Systems 1949 landmark paper. To this date this principle is
used in designing block ciphers. There are many interpretations of this concept, one given by Massey below.

1. Confusion: The ciphertext statistics should depend on the plaintext
   statistics in a manner too complicated to be exploited by the cryptan-
   alyst.
2. Diffusion: Each digit of the plaintext and each digit of the secret key
   should influence many digits of the ciphertext.

A good block cipher provides a sufficient combination of confusion and diffusion.

How to get Confusion and Diffusion?

We can get confusion by substitution(S) using an S-Box or a lookup table.
The S-box should be non-linear to make the cipher resistant against Differen-
tial and Linear Cryptanalysis.

Similarly, we can get diffusion using permutation(P), which simply means
moving bits around. Since permutations can be represented by linear maps,
diffusion has linear component.

Block Ciphers use a combination of S and P. A class of Block Ciphers use
Substitution-Permutation Network (SPN) for their construction.

This is the SPN of a lightweight cipher called PRESENT.

This is the Substitution Box (S-Box) of PRESENT cipher. The S-Box design
is not chosen randomly and requires a lot of consideration and mathematics to make the cipher resistant to various attacks.

Round Functions

All the complicated SPN and other things can be abstracted away into a Round Function(F). The design of the F lies in the heart of the block cipher design.The F itself might be weak, but iterating it multiple times leads to a secure construction.

Block Cipher Design Techniques

There are mainly two ways to design a block cipher — using Feistel Networks
and SP-Networks.

Feistel Networks — DES

The Data Encryption Standard(DES), a predecessor to AES uses Feistel Net-
works. A Feistel network uses a round function, a function which takes two
inputs — a data block and a subkey — and returns one output of the same size
as the data block. In each round, the round function is run on half of the data
to be encrypted, and its output is XORed with the other half of the data. This
is repeated a fixed number of times, and the final output is the encrypted data.

An important advantage of Feistel networks compared to other cipher designs
such as SPN is that the entire operation is guaranteed to be invertible, even
if the round function is not itself invertible. The round function can be made
arbitrarily complicated, since it does not need to be designed to be invertible.

Substitution Permutation Networks — AES

An SPN simply uses a combination of Substitution and Permutation as described before for its construction.

Round Keys

If you have been reading this carefully, you might have noticed that for each
round, a different key is being added.

The KS means Key Scheduling/Expansion. Each round key is derived from
the user supplied master key. The Key Scheduling algorithm then expands this
key in order to be used as round keys. Some Key Scheduling algorithms are
computationally lightweight while others are very complicated.

Why bother using different round keys?

Let’s see what happens if we use the same key for all rounds.

This is called the Slide Attack. When the round keys are identical the relation
between the two plaintexts, P2 = R(P1 ), implies the relation C2 = R(C1 ).
In fact, this is independent of the number of rounds of the block cipher.

Invertiblity of Round Keys

Invertiblity means that given (n + 1)th round key, we can derive the nth round key. This implies that if an attacker gets a key Ki , he can recover back the main key K. This property is generally exploited by Side Channel Attacks. Also a fun fact to note that AES Key Schedule algorithm is invertible.

Miscellaneous

How do we deal with arbitrarily large amount of data?

We simply divide the data into blocks of size n, in case the size is not divisible
by n, we use padding to make the data size in a multiple of n.

Mode of Operation

There are various ways for a block cipher to use the block to encrypt futher
data. Some of the common ways for a block cipher to operate are:

1. Electronic Code Book(ECB)
2. Cipher Block Chaining (CBC)
3. Output Feedback Mode (OFM)
4. Cipher Feedback Mode(CFB)
5. Counter Mode (CTR)

Weakness of ECB

In ECB mode the encrypted block is arranged in the same order as the plaintext blocks. The encryption scheme does not involve using other blocks in order to encrypt new blocks. In simple words, each block is encrypted independently in ECB mode.

This has some serious implications in the fact that it actually leaks informa-
tion. A famous example demonstrating the weakness of ECB mode is the Linux Tux.

The second image is encrypted using the AES-ECB . As you can see we can deduce that the unencrypted image actually contained a Linux Tux.

The third image is encrypted using AES-CBC. As you can see the third image looks like random noise and we cannot deduce any information from the
image.

Block Ciphers as Mathematical Objects

Like any other cipher (from Shannon’s theory), a block cipher maps a plain text and keys to a cipher text. Mathematically,

Fixing a key K ∈ K defines the permutation as follows:

Leading to the set definitions of encryption functions:

The plaintext and cipher text (in an n-bit block cipher) consists of 2^n possible unique blocks. This means that (2^n)! permutations are possible from P to C. We can approximate using Sterling Approximation

However, the key space K consists of 2^k keys where k is the size of each key.
And this is the actual number of permutations provided by the block cipher.
As we can observe, the cipher provides only a fraction of the total number of
available permutations.

A randomly chosen key is expected to select a permutation seemingly at random from among all 2^((n−1)2^n) possibilities. So that permutations from related keys should not be related to each other.

Image Credits: All the images used in this story comes from CS553 Cryptography course by Dr. Dhiman Saha at Indian Institute of Technology Bhilai.

Also thanks to my buddy Satvik for contributing to Mathematical aspect of Block Ciphers