2
$\begingroup$

Is there an easy to understand and intuitive "one fits all" definition for the concept of diffusion that is applicable to both modern binary cryptosystems as well as classical ciphers?

For a bit of background:

I am currently in the process of writing some teaching materials for high school students (~16 year olds) about cryptography. While talking about more modern approaches like (binary) SP-networks I wanted to include the concept of diffusion (and confusion). While the high level aim of diffusion is clear (needing large portions of the ciphertext for cryptanalysis), I struggle to find a good (intuitive) definition for the concept that would be suitable for students of that level and age. Also, I would like to assess some classical ciphers (i.e. non-block ciphers) we have looked at previously as to whether or not they implement diffusion as per this definition. The more I read up on the topic and the more resources I reference, the more confused I get personally...

Many resources describe diffusion as Changing one symbol in the plain text should affect many positions of the ciphertext.

Now, for SP-Networks, this definition can easily be applied and it is easily explainable why SP-Networks achieve diffusion. For some classical ciphers, though, I struggle to apply this definition. In some cases, I think something closer to Shannon's definition in his original paper, i.e. something like the statistics/characteristics of a message being dissipated over large portions of the ciphertext would be more applicable. Let me give you some examples:

  • Transposition ciphers (e.g. Scytale): Many resources say that transposition ciphers offer a good amount of diffusion. However, changing one letter in the plain text affects exactly one letter in the ciphertext. Unless we think of changing one letter as leaving out one letter, or some 'hack' like first encoding a letter in morse code and then applying the transposition, in which case the ciphertext may indeed change a lot. Wouldn't the second definition be more applicable here? The characteristic of the plain text (e.g. double letters or word boundaries) get torn apart and spread out over large portions of the cipher text.

  • Vigenère: Exchanging one symbol in the plain text for another affects exactly one position in the cipher text, which speaks for bad diffusion. Some characteristics (like double letters) are changed, but not really spread out, so am I right in concluding that diffusion (by both definitions) is not really achieved here? However, if we leave out one character in the plain text, the ciphertext changes from that position onward...

  • Enigma: I struggle to find resources where the Enigma cryptosystem is examined for diffusion, and if I find some, no reason is given. Changing one symbol in the plain text again affects only one symbol in the ciphertext. Leaving out a symbol on the other hand changes the ciphertext from that position onward... Again, characteristics (statistics) are not really spread out, even if slightly changed (e.g double letters or common short words). In my understanding (which might very well be wrong), I would see the enigma as a cryptosystem with rather high confusion, but diffusion is not really achieved. Would I be correct in saying so?

PS: I am aware that Shannon, in his original paper, defines the term as a concept. Most resources however treat it as a property, speaking of good/bad/high levels of diffusion. For the level of my teaching and my students, I think this is more intuitive.

$\endgroup$

2 Answers 2

1
$\begingroup$

Many resources describe diffusion as Changing one symbol in the plain text should affect many positions of the ciphertext.

That's a proper definition of a particular kind of diffusion: plaintext-to-ciphertext diffusion, which is the one considered by Shannon. But it turns out that this kind of diffusion is far from essential for encryption. Thus it's not a good idea to use that definition, which is bound to cause confusion :-)

Diffusion is a property of a function: that a small change (e.g. one bit) at the input of the function most often causes a large change at it's output (e.g. about half of the output bits).

A constant function has no diffusion. Identity has small diffusion: changing an input bit always changes that one output bit. Same for any of the $4!=16$ distinct permutations of four bits. However, a random among the $(2^4)!=16777216$ permutations of the 16 four-bit values will typically have more diffusion: changing one input bit may change 1, 2, 3 or 4 output bits (depending on other input bits and the particular permutation).

For functions with several inputs and/or outputs, we often need to distinguish diffusion from some input(s) to some output(s). For example, encryption can be viewed as a function of key, Initialisation Vector#, and plaintext, with output the ciphertext. Thus we have:

  1. key-to-ciphertext diffusion
  2. IV-to-ciphertext diffusion
  3. plaintext-to-ciphertext diffusion

The first two kinds of diffusion matter in encryption. The third kind is far from essential, and correspondingly minimal in many encryption systems old (Enigma, where one plaintext symbol diffuses to a single ciphertext symbol) and new (stream ciphers, AES-CTR, ChaCha, where one plaintext bit diffuses to a single ciphertext bit).

A block cipher is a fundamental element of some modern encryption systems. It is expected to have excellent key-to-ciphertext-block and plaintext-block-to-ciphertext-block diffusion. A block cipher with several symbols per plaintext block (e.g. 8 bytes for DES, 16 bytes for AES) used to build encryption per ECB mode closely matches Shannon's view of (plaintext to ciphertext) diffusion:

In the method of diffusion the statistical structure of (the message) M which leads to its redundancy is “dissipated” into long range statistics - i.e. into statistical structure involving long combinations of letters in the cryptogram. The effect here is that the enemy must intercept a tremendous amount of material to tie down this structure, since the structure is evident only in blocks of very small individual probability.

Diffusion is important for the internal construction and outer characteristics of cryptographic primitives, not limited to encryption: a hash is expected to have message-to-hash diffusion, a Message Authentication Code is expected to have key-to-tag and message-to-tag diffusion.


The Scytale or any fixed transposition cipher has poor plaintext-to-ciphertext diffusion: changing one input symbol changes a single output symbol. Further, slightly changing the input symbol changes the output symbol correspondingly, thus slightly.


# An Initialisation Vector (IV) is a per-message nonce, not necessarily secret, and typically public in modern cryptosystems. It's often present under other names in older cryptosystems: Buchstabenkenngruppe and Spruchschlüssel (message key) in Enigma.

$\endgroup$
-1
$\begingroup$

Is there an easy to understand and intuitive "one fits all" definition for the concept of diffusion that is applicable to both modern binary cryptosystems as well as classical ciphers?

Diffusion in cryptography: An small change in the input, results significant change in the output.

In modern binary cryptosystems, diffusion ensures that each bit of the plaintext affects many bits of the ciphertext, enhancing security by spreading the influence of each input bit.
Like AES, excel in diffusion by dispersing the influence of each plaintext bit throughout the entire ciphertext, making it highly resistant to cryptanalysis.

In classical ciphers, diffusion occurs when altering a single character in the plaintext causes multiple changes ciphertext.
Like the Caesar cipher, diffusion is limited as small changes in plaintext result in predictable changes in the ciphertext.


Therefore, a concise definition of diffusion applicable to both modern and classical systems is the fundamental concept of spreading input changes across the output to achieve robust encryption.
$\endgroup$
1
  • 1
    $\begingroup$ First sentence is OK, but plaintext-to-ciphertext diffusion is not in general a functional requirement of encryption old or new. For example there's next to no plaintext-to-ciphertext diffusion in Enigma, AES-CTR, Chacha... What matters for encryption is key-to-ciphertext and IV-to-ciphertext diffusion. Also diffusion matters in block ciphers, which are building blocks for encryption. $\endgroup$
    – fgrieu
    Feb 28 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.