JustinT
Trusted SF Member
Joined: 17 Apr 2003
Posts: 1233
Location: Charlotte, NC, US / Uberlāndia, MG, Brazil
|
 Posted: Sun Sep 05, 2004 9:35 pm Post subject: Confusion and diffusion. |
 |
|
The largest portion of modern, conventional symmetric algorithms in use are block ciphers, so let's focus on that, first. Predominantly, as previously mentioned, they are based on the surrounding theory of Feistel networks and Substitution-Permutation Networks, iterated and/or product; along with them come many variations, such as unbalanced Feistel networks or modified Substitution-Permutation Networks, for example. Generally, these are the two most commonly encountered structures, so there is quite a wealth of published cryptanalysis to support them.
Just to give you an idea of house-hold name algorithms based on these structures - DES is a Feistel network and AES is a Substitution-Permutation Network. In a Feistel network, we generally have a "round function" that is iterated for n rounds; in a Substitution-Permutation Network, we generally have layers of routines that perform substitutions and permutations, in a round transformation, obviously, iterated for n rounds. There are similarities in both structures. As aforementioned, there are several variations of either of these, so the exact approach may differ, while still arriving at the same purpose. As for formulas that demonstrate the mathematical constructions of these design strategies, refer to the NIST's FIPS publications for DES [FIPS 46-3], a Feistel network, and AES [FIPS 197], a Substitution-Permutation Network.
Claude E. Shannon, roughly fifty-five years ago, conceptualized two basic principles in his published works on communication theory of secrecy systems [Bell Systems Technical Journal, v. 28, n. 4, 1949, pp. 656-715]; these two principles, confusion and diffusion, are the integral, foundational properties of most block ciphers. Very primitively, confusion makes an attempt to obfuscate the relationship between plaintext, a key, and ciphertext, while diffusion makes an attempt to disseminate plaintext redundancy over the ciphertext; they are both very literal terms.
Respectively, they both aim towards obfuscating the redundancy of plaintext, that would otherwise statistically aid in linear or differential cryptanalysis. The most trivial way to go about achieving confusion is through substitution, which we commonly see in components such as the nonlinear S-boxes of block ciphers, which are often the primary source of security for the algorithm; the most trivial way to go about achieving diffusion is through permutation, which we commonly see in components such as the linear expansion or straight permutation routines of block ciphers.
Stream ciphers usually rely on confusion alone, but with the introduction of a feedback routine, for instance, diffusion can also be added; they can also be constructed similarly to block ciphers, and block ciphers can also be used in a stream cipher fashion, so the taxonomy can be very confusing at times. Because many cryptographic primitives have variable usage (i.e., block ciphers built from stream cipher or hash function components, and vice versa), it's difficult to strictly class them as one type or another, so keep that in mind when researching this.
So, to briefly conclude, confusion and diffusion are the two general principles behind the design of conventional block ciphers. Pay close attention to the design criteria of S-boxes, since it must be rather strategic in its quest to thwart both linear and differential cryptanalysis. There are numerous design strategies, but most stem from the two networks mentioned here (Feistel and Substitution-Permutation), based on the above two principles.
_________________
"Strict Avalanche Criterion n. Restrictive clause in ski-insurance policy."
|
|
I hope I have a great time.
Any formulas to illustrate ??
