Substitution-permutation network - AbsoluteAstronomy.com

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, an SP-network, or substitution-permutation network (SPN), is a series of linked mathematical operations used in block cipher

Block cipher

In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...

algorithms such as AES (Rijndael)

Advanced Encryption Standard

Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...

.
Other ciphers that use SPNs are 3-Way

3-Way

In cryptography, 3-Way is a block cipher designed in 1994 by Joan Daemen, who also designed Rijndael, the winner of NIST's Advanced Encryption Standard contest....

, SAFER

SAFER

In cryptography, SAFER is the name of a family of block ciphers designed primarily by James Massey on behalf of Cylink Corporation. The early SAFER K and SAFER SK designs share the same encryption function, but differ in the number of rounds and the key schedule...

, SHARK

SHARK

In cryptography, SHARK is a block cipher identified as one of the predecessors of Rijndael .SHARK has a 64-bit block size and a 128-bit key size. It is a six round SP-network which alternates a key mixing stage with linear and non-linear transformation layers...

, and Square

Square (cipher)

In cryptography, Square is a block cipher invented by Joan Daemen and Vincent Rijmen. The design, published in 1997, is a forerunner to the Rijndael algorithm, which has been adopted as the Advanced Encryption Standard...

.

Such a network takes a block of the plaintext

Plaintext

In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....

and the key

Key (cryptography)

In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...

as inputs, and applies several alternating "rounds" or "layers" of substitution boxes (S-boxes)

Substitution box

In cryptography, an S-Box is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext — Shannon's property of confusion...

and permutation boxes (P-boxes)

Permutation box

In cryptography, a permutation box is a method of bit-shuffling used to permute or transpose bits across S-boxes inputs, retaining diffusion while transposing....

to produce the ciphertext

Ciphertext

In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...

block. The S-boxes and P-boxes transform of input bit

Bit

A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...

s into output bits. It is common for these transformations to be operations that are efficient to perform in hardware, such as exclusive or

Exclusive disjunction

The logical operation exclusive disjunction, also called exclusive or , is a type of logical disjunction on two operands that results in a value of true if exactly one of the operands has a value of true...

(XOR) and bitwise rotation. The key is introduced in each round, usually in the form of "round keys" derived from it. (In some designs, the S-boxes themselves depend on the key.)

Decryption is done by simply reversing the process (using the inverses of the S-boxes and P-boxes and applying the round keys in reversed order).

An S-box substitutes a small block of bits (the input of the S-box) by another block of bits (the output of the S-box). This substitution should be one-to-one, to ensure invertibility (hence decryption). In particular, the length of the output should be the same as the length of the input (the picture on the right has S-boxes with 4 input and 4 output bits), which is different from S-boxes in general that could also change the length, as in DES (Data Encryption Standard)

Data Encryption Standard

The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...

, for example. An S-box is usually not simply a permutation

Permutation

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

of the bits. Rather, a good S-box will have the property that changing one input bit will change about half of the output bits (or an avalanche effect

Avalanche effect

In cryptography, the avalanche effect refers to a desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions. The avalanche effect is evident if, when an input is changed slightly the output changes significantly...

). It will also have the property that each output bit will depend on every input bit.

A P-box is a permutation

Permutation

of all the bits: it takes the outputs of all the S-boxes of one round, permutes the bits, and feeds them into the S-boxes of the next round. A good P-box has the property that the output bits of any S-box are distributed to as many S-box inputs as possible.

At each round, the round key (obtained from the key

Key (cryptography)

with some simple operations, for instance, using S-boxes and P-boxes) is combined using some group operation, typically XOR.

A single typical S-box or a single P-box alone does not have much cryptographic strength: an S-box could be thought of as a substitution cipher

Substitution cipher

In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the "units" may be single letters , pairs of letters, triplets of letters, mixtures of the above, and so forth...

, while a P-box could be thought of as a transposition cipher

Transposition cipher

In cryptography, a transposition cipher is a method of encryption by which the positions held by units of plaintext are shifted according to a regular system, so that the ciphertext constitutes a permutation of the plaintext. That is, the order of the units is changed...

. However, a well-designed SP network with several alternating rounds of S- and P-boxes already satisfies Shannon's confusion and diffusion
Confusion and diffusion
In cryptography, confusion and diffusion are two properties of the operation of a secure cipher which were identified by Claude Shannon in his paper Communication Theory of Secrecy Systems, published in 1949....

properties:

The reason for diffusion is the following: If one changes one bit of the plaintext, then it is fed into an S-box, whose output will change at several bits, then all these changes are distributed by the P-box among several S-boxes, hence the outputs of all of these S-boxes are again changed at several bits, and so on. Doing several rounds, each bit changes several times back and forth, therefore, by the end, the ciphertext has changed completely, in a pseudorandom manner. In particular, for a randomly chosen input block, if one flips the i-th bit, then the probability that the j-th output bit will change is approximately a half, for any i and j, which is the Strict Avalanche Criterion.

The reason for confusion is exactly the same as for diffusion: changing one bit of the key changes several of the round keys, and every change in every round key diffuses over all the bits, changing the ciphertext in a very complex manner. Vice versa, changing one bit in the ciphertext will change the key completely.

Although a Feistel network that uses S-boxes (such as DES

Data Encryption Standard

) is quite similar to SP networks, there are some differences that make either this or that more applicable in certain situations. For a given amount of confusion and diffusion

Confusion and diffusion

In cryptography, confusion and diffusion are two properties of the operation of a secure cipher which were identified by Claude Shannon in his paper Communication Theory of Secrecy Systems, published in 1949....

, an SP network has more "inherent parallelism"
and so — given a CPU with a large number of execution unit

Execution unit

In computer engineering, an execution unit is a part of a CPU that performs the operations and calculations called for by the Branch Unit, which receives data from the CPU...

s — can be computed faster than a Feistel network.

CPUs with few execution units — such as most smart card

Smart card

A smart card, chip card, or integrated circuit card , is any pocket-sized card with embedded integrated circuits. A smart card or microprocessor cards contain volatile memory and microprocessor components. The card is made of plastic, generally polyvinyl chloride, but sometimes acrylonitrile...

s — cannot take advantage of this inherent parallelism.

See also