Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Substitution–permutation network
open-in-new
<h2 id="components">Components</h2> <p>An <a href="/facts/S-box/9xKgnLCF">S-box</a> 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 <a href="/facts/Bijective/j4gTuTmW">one-to-one</a>, 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 <a href="/facts/Data_Encryption_Standard/STfBjTGb">Data Encryption Standard</a> (DES), for example. An S-box is usually not simply a <a href="/facts/Permutation/JSw9ukmv">permutation</a> of the bits. Rather, in a good S-box each output bit will be affected by every input bit. More precisely, in a good S-box each output bit will be changed with 50% probability by every input bit. Since each output bit changes with the 50% probability, about half of the output bits will actually change with an input bit change (cf. <a href="/facts/Strict_avalanche_criterion/hpYX5zu5">Strict avalanche criterion</a>).<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> </p><p>A <a href="/facts/Permutation_box/QochB9Th">P-box</a> is a <a href="/facts/Permutation/JSw9ukmv">permutation</a> 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. </p><p>At each round, the <a href="/facts/Round_key/H2klHRyU">round key</a> (obtained from the <a href="/facts/Key_(cryptography)/5W5PAmT4">key</a> with some simple operations, for instance, using S-boxes and P-boxes) is combined using some group operation, typically <a href="/facts/XOR/FHyr7hGQ">XOR</a>. </p> <h2 id="properties">Properties</h2> <p>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 <a href="/facts/Substitution_cipher/PCTy2EJL">substitution cipher</a>, while a P-box could be thought of as a <a href="/facts/Transposition_cipher/mmch3Mgu">transposition cipher</a>. However, a well-designed SP network with several alternating rounds of S- and P-boxes already satisfies Shannon's <a href="/facts/Confusion_and_diffusion/PKqvzyKY">confusion and diffusion</a> properties: </p> <ul><li>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 <a href="/facts/Pseudorandom/kfs1wfhY">pseudorandom</a> manner. In particular, for a randomly chosen input block, if one flips the <i>i</i>-th bit, then the probability that the <i>j</i>-th output bit will change is approximately a half, for any <i>i</i> and <i>j</i>, which is the <a href="/facts/Strict_avalanche_criterion/hpYX5zu5">strict avalanche criterion</a>. Vice versa, if one changes one bit of the ciphertext, then attempts to decrypt it, the result is a message completely different from the original plaintext—SP ciphers are not easily <a href="/facts/Malleability_(cryptography)/91uHXJIr">malleable</a>.</li> <li>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 <a href="/facts/Diffuse/KbAxroBa">diffuses</a> over all the bits, changing the ciphertext in a very complex manner.</li> <li>If an attacker somehow obtains one plaintext corresponding to one ciphertext—a <a href="/facts/Known-plaintext_attack/MF3CweFd">known-plaintext attack</a>, or worse, a <a href="/facts/Chosen_plaintext/uTJ0XCAN">chosen plaintext</a> or <a href="/facts/Chosen-ciphertext_attack/l9fL7fYR">chosen-ciphertext attack</a>—the confusion and diffusion make it difficult for the attacker to recover the key.</li></ul> <h2 id="performance">Performance</h2> <p>Although a <a href="/facts/Feistel_network/CPtzaEET">Feistel network</a> that uses S-boxes (such as <a href="/facts/Data_Encryption_Standard/STfBjTGb">DES</a>) 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 <a href="/facts/Confusion_and_diffusion/PKqvzyKY">confusion and diffusion</a>, an SP network has more "inherent parallelism"<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> and so — given a CPU with many <a href="/facts/Execution_unit/uvg54JcX">execution units</a> — can be computed faster than a Feistel network.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> CPUs with few execution units — such as most <a href="/facts/Smart_card/K7b9lowS">smart cards</a> — cannot take advantage of this inherent parallelism. Also SP ciphers require S-boxes to be invertible (to perform decryption); Feistel inner functions have no such restriction and can be constructed as <a href="/facts/One-way_function/rGtcumDW">one-way functions</a>. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Feistel_network/CPtzaEET">Feistel network</a></li> <li><a href="/facts/Product_cipher/qHTBoCnh">Product cipher</a></li> <li><a href="/facts/Square_(cipher)/mQRozt3V">Square (cipher)</a></li> <li><a href="/facts/International_Data_Encryption_Algorithm/HuRBKLQY">International Data Encryption Algorithm</a></li></ul> <h2 id="further-reading">Further reading</h2> <ul><li>Katz, Jonathan; Lindell, Yehuda (2007). <a href="https://archive.org/details/Introduction_to_Modern_Cryptography"><i>Introduction to Modern Cryptography</i></a>. CRC Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781584885511.</li> <li>Stinson, Douglas R. (2006). <i>Cryptography. Theory and Practice</i> (Third ed.). Chapman & Hall/CRC. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 1584885084.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Webster, A. F.; Tavares, Stafford E. (1985). "On the design of S-boxes". Advances in Cryptology – Crypto '85. Lecture Notes in Computer Science. Vol. 218. New York, NY: Springer-Verlag New York, Inc. pp. 523–534. ISBN 0-387-16463-4. <a href="0-387-16463-4" target="_blank">0-387-16463-4</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>"Principles and Performance of Cryptographic Algorithms" by Bart Preneel, Vincent Rijmen, and Antoon Bosselaers. <a href="http://www.ddj.com/184410756" target="_blank">http://www.ddj.com/184410756</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>"The Skein Hash Function Family" Archived 2009-01-15 at the Wayback Machine 2008 by Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker page 40. <a href="http://www.schneier.com/skein1.1.pdf" target="_blank">http://www.schneier.com/skein1.1.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>