Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Origin of SPN
3.
Substitution-Permutation Network(SPN)
4.
Components of SPN
5.
Properties of SPN
6.
Operations in SPN
6.1.
Addition of Round Key
6.2.
Substitution of Bits
6.3.
Permutation of Bits
6.4.
Example
7.
Frequently Asked Questions
7.1.
What is an Avalanche Effect in Cryptography?
7.2.
What is SPN Structure?
7.3.
How do substitution and permutation processes help in encryption?
8.
Conclusion
Last Updated: Mar 27, 2024

Substitution-Permutation Networks(SPN) in Cryptography

Author Nidhi Kumari
2 upvotes

Introduction

The study of secure communication methods, such as encryption that keep message contents private to the sender and receiver is known as cryptography. An algorithm and security key is used to encrypt data in blocks to create ciphertext using a block cipher. An iterative block cipher is usually built using Substitution-Permutation Networks (SPN).

 In this article, we will discuss Substitution-Permutation Networks(SPN) in Cryptography.

Substitution-Permutation Networks(SPN) in Cryptography

Origin of SPN

The simplest type of encryption, known as symmetric key encryption, requires both parties—such as the sender and receiver to know the same secret key. The ciphertext is decoded using the secret key, which is also used to encrypt the plaintext. The system is insecure if a third party (a potential attacker) finds the secret key.

For secure symmetric key encryption, a robust, difficult-to-crack algorithm is required. Two fundamental operations—substitution and permutation—are the foundation of symmetric key ciphers.

  • Substitution: Swapping of one element in plaintext with another.
     
  • Permutation: Rearranging the text elements.
     
  • Product System: Multiple layers of substitutions and permutations are used in product systems, such as the Feistel network and the Substitution Permutation Network (SPN).

Substitution-Permutation Network(SPN)

SPN is used to generate iterative Block ciphers, which means the block ciphers use rounds of a repeated series of mathematical operations. An Alternative layer of substitution(S-box)  and Permutation(P-box) is applied to each layer in the SPN. 

S-boxes and P-boxes convert input blocks into output blocks. Each round uses a new round key, XORed, to produce the ciphertext in the final round.

Components of SPN

The S-boxes and P-boxes are the two main components of an SP Network. S-boxes are non-linear transformations of a small number of input bits that produce confusion, and P-boxes merely rearrange the input bits to produce diffusion.

An S-box substitutes one small input block of bits with another small block (the output). For invertibility, this substitution should be one-to-one. In contrast to S-boxes generally, the length of the output should precisely match the length of the input (i.e., S-boxes with four inputs will have four output bits). Additionally, every output bit will be dependent on every input bit.

S box

P-box is a permutation of every bit; it takes the outputs from every S-box in a round, permutes the bits, and then feeds them into the S-boxes in the following round. The output bits of any S-box are distributed across as many S-box inputs as possible in a good P-box.

P box

Properties of SPN

A series of substitutions followed by a permutation has high "mixing" properties even though it is weak on its own: Substitutions increase confusion, and Permutation glues them together and spreads (diffuses) the local confusion to the more distant subblocks utilised in Cryptography. The decryption is done by simply reversing the S-box and P-box operations.

Confusion: A local, "random" change in the output should follow a slight change in the input.

Diffusion: The overall output should be affected by local changes.

If one bit of the plaintext is changed, it is fed into an S-box, whose output will change at multiple bits. Then all these changes are distributed by the P-box among multiple S-boxes, resulting in the outputs of all these S-boxes being changed at multiple bits once more, and so on. Each bit is altered repeatedly for several rounds, so the ciphertext has changed entirely by the end. 

The uncertainty and diffusion make it difficult for attackers to recover the key if they get one pair of plaintext and ciphertext(a known-plaintext attack).

Operations in SPN

The conversion of plaintext into ciphertext in SPN consists of three primary operations in each round:

  • Addition of Round Key.
     
  • Substitution.
     
  • Permutation.
Components of SP Network

Addition of Round Key

An SP network has a round key for each round. One secret key first transmitted to the network is expanded to produce round keys, which are then recovered. The text is XORed with the relevant round key at the beginning of each round to ensure that only a person with the round keys may decrypt the ciphertext.

Substitution of Bits

The text is then swapped among the individual text bits. Block cyphers use SP networks. Therefore, the text is organised into blocks. The rules established by predefined S-boxes are used to replace the block text bytes.

Permutation of Bits

The permutation step comes last. In this step, the block text's components are mixed. In AES, all rows except the first are shifted by one, which illustrates such mixing.

Example

Let’s understand the operations in SP Network with the help of a simple example. Consider a plain text:

codingninjasisbestplatform

Using a permutation that separates the message into 6-letter blocks, we will encipher it.

coding ninjas isbest platfo rm

The last block must be padded because the plaintext message's letter counts are not divisible by 6. The final block in this example is padded with Xs. 

The padding must be selected to allow the recipient to distinguish the message apart from the padding while deciphering it.

coding ninjas isbest platfo rmXXXX

The letters of the blocks are then rearranged using the following permutation:

Selected Permutation

The letter in the top-left corner of the block, in position 1, moves to position 4, Similarly

  • The letter in position 2, moves to position 6.
     
  • The letter in position 3, moves to position 5.
     
  • The letter in position 4, moves to position 2.
     
  • The letter in position 5, moves to position 3.
     
  • The letter in position 6, moves to position 1.
     

The result of applying the permutation on the first block is:

coding -> gincdo

The result of applying the permutation on all the blocks is:

Plain text: coding ninjas isbest platfo rmXXXX

Cipher text: gincdo sjanni tesibs otfpal XXXrXm

By using the permutation's inverse, the message is decoded.

Frequently Asked Questions

What is an Avalanche Effect in Cryptography?

The mathematical function(Substitution in SPN) employed in cryptography has a unique effect known as the "avalanche effect." The avalanche effect states that if one bit in the input block is changed, it will change about half of the bits in the Output block.

What is SPN Structure?

To defend vital information from attackers, Shannon cipher invented the idea of confusion and Diffusion, which is directly realised by the Substitution-Permutation Network (SPN) structure. Confusion is a local, "random" change in the output that should follow a slight change in the input. The overall output should be affected by local changes, known as Diffusion.

How do substitution and permutation processes help in encryption?

Substitution and permutation are two methods that are commonly applied to create ciphertext. In substitution, letters, integers, or symbols are used in place of plaintext letters or strings of characters. The plaintext message letters are used in permutation but in a different order.

Conclusion

We discussed the Origin of Substitution-Permutation Networks(SPN) in Cryptography. Further, we covered the Properties, Components and some operations of Substitution-Permutation Networks(SPN) in Cryptography.

We hope this blog has helped you. We recommend you visit our articles on different topics of Cryptography, such as

🔥 What is Cryptography?

🔥 Cryptographic System.

🔥 Cryptosystem.

If you liked our article, do upvote our article and help other ninjas grow.  You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more!

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!!

Happy Reading!!

Live masterclass