In cryptography, an SPnetwork, or substitutionpermutation network (SPN), is a series of linked mathematical operations used in block cipher algorithms such as AES (Rijndael).
Such a network takes a block of the plaintext and the key as inputs, and applies several alternating "rounds" or "layers" of substitution boxes (Sboxes) and permutation boxes (Pboxes) to produce the ciphertext block. The Sboxes and Pboxes transform (sub)blocks of input bits into output bits. It is common for these transformations to be operations that are efficient to perform in hardware, such as exclusive or (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 Sboxes themselves depend on the key.)
Decryption is done by simply reversing the process (using the inverses of the Sboxes and Pboxes and applying the round keys in reversed order).
An Sbox substitutes a small block of bits (the input of the Sbox) by another block of bits (the output of the Sbox). This substitution should be onetoone, 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 Sboxes with 4 input and 4 output bits), which is different from Sboxes in general that could also change the length, as in DES (Data Encryption Standard), for example. An Sbox is usually not at all just a permutation of the bits. Rather, a good Sbox will have the property that changing one input bit will change about half of the output bits (or an avalanche effect). It will also have the property that each output bit will depend on every input bit.
A Pbox is a permutation of all the bits: it takes the outputs of all the Sboxes of one round, permutes the bits, and feeds them into the Sboxes of the next round. A good Pbox has the property that the output bits of any Sbox are distributed to as many Sbox inputs as possible.
At each round, the round key (obtained from the key with some simple operations, for instance, using Sboxes and Pboxes) is combined using some group operation, typically XOR.
A single typical Sbox or a single Pbox alone does not have much cryptographic strength: an Sbox could be thought of as a substitution cipher, while a Pbox could be thought of as a transposition cipher. However, a welldesigned SP network with several alternating rounds of S and Pboxes already satisfies Shannon's confusion and diffusion properties:
 The reason for diffusion is the following: If one changes one bit of the plaintext, then it is fed into an Sbox, whose output will change at several bits, then all these changes are distributed by the Pbox among several Sboxes, hence the outputs of all of these Sboxes 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 ith bit, then the probability that the jth 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 Sboxes (such as DES) 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, an SP network has more "inherent parallelism"^{[1]} and so — given a CPU with a large number of execution units — can be computed faster than a Feistel network. ^{[2]} CPUs with few execution units — such as most smart cards — cannot take advantage of this inherent parallelism.
References[edit  edit source]
 Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography. CRC Press, 2007.
 Douglas R. Stinson, Cryptography. Theory and Practice. Third edition. Chapman & Hall/CRC, 2006.
 ↑ "Principles and Performance of Cryptographic Algorithms" by Bart Preneel, Vincent Rijmen, and Antoon Bosselaers.
 ↑ "The Skein Hash Function Family" 2008 by Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker page 40.
See also[edit  edit source]

fr:Réseau de substitutionpermutation it:Rete a sostituzione e permutazione ja:SPN構造 no:Substitusjon/permutasjonchiffer simple:Substitutionpermutation network sv:Substitutionspermutationskrypto ru:SPсеть