Score:3

Confusion and diffusion misunderstanding

us flag

I am reading the book titled "Algebra for Cryptologists". The author defined the confusion and the diffusion as follows:

Confusion: Confusion is intended to make the relationship between the plaintext and/or the key on the one hand, and the ciphertext on the other, as complex as possible, or as stated by J.L. Massey: “The ciphertext statistics should depend on the plaintext statistics in a manner too complicated to be exploited by the cryptanalyst.” From this point of view a simple substitution cipher, which is essentially just a permutation $\pi$ of the plaintext alphabet {a,b,c, . . . , z}, is unsatisfactory: the frequency distribution of, say, English is inherited by the ciphertexts—the overwhelming frequency of the letter e in English is now reflected in the same frequency of $\pi (e)$ in the ciphertext. Diffusion: In order to avoid this kind of weakness, the second attribute of diffusion is required. Each symbol of the key and/or of the plaintext should affect as many ciphertext symbols as possible.

However, in the book titled "understanding cryptography",

Confusion is an encryption operation where the relationship between key and ciphertext is obscured. Diffusion is an encryption operation where the influence of one plaintext symbol is spread over many ciphertext symbols with the goal of hiding statistical properties of the plaintext.

Note that the first book made the relationship to be between the key/plaintext and the ciphertext in both definitions, not the same as the second book.

The question: Are these definitions not restrict, and could change from author to author? Which book is more accurate? Is the book "Algebra for Cryptologists" good to read as a math/crypto?

Score:4
cn flag

Both are not super clear, especially if you do not understand the math involved, though both have very similar descriptions. I would say the first book has a better description for confusion, but the second is better for diffusion, though it is the key that is being diffused into the plaintext to make the ciphertext, in a "confusing" way so that you cannot "undiffuse" either out of the ciphertext.

In fact, with a large enough "confusion" layer, you do not need a "diffusion" layer. Confusion refers to a non-linear operation, and diffusion a linear operation. Large non-linear operations are VERY computationally expensive, which is why a small non-linear operation is combined with linear operations to get the job done.

What the combination of linear and non-liner mixing does is make the relationship between the ciphertext and key, and between the ciphertext and plaintext, an extremely complex math problem to solve. If someone knows the plaintext and the ciphertext, you do not want them to find the key, and if they know the ciphertext only, you do not want them to find the key or the plaintext.

It helps to see how these these apply to a common cipher like AES. AES uses a 128-bit block, with an 8-bit non-linear sbox, and a linear matrix multiplication in a finite field operating on 32-bits of the block in 4 parallel paths.

AES Round Operations

In AES, the confusion comes from the s-box (Sub Byte layer), which is used in the round function as well as the key schedule. Diffusion comes from the matrix operation (Mix Column layer) combined with row shifting so that all input bits are fully mixed over the course of 2 rounds, in combination with how the round subkeys are generated in the key schedule.

With enough rounds, the work to solve the math problem becomes harder than brute forcing the key, and AES has those pretty much right at about the same level. Of course it is more complicated than that, but that is the cliff notes.

Image courtesy of wikpedia

user2357 avatar
us flag
Thank you......
user2357 avatar
us flag
You said "though it is the key that is being diffused into the plaintext to make the ciphertext, in a "confusing" way so that you cannot "undiffuse" either out of the ciphertext."; This means that the first book is also better in the definition of the diffusion, am I right?
Richie Frame avatar
cn flag
@user2357 They are both not great so choosing is not so easy, I am focusing specifically on "spread over many ciphertext symbols with the goal of hiding statistical properties" is better than "should affect as many ciphertext symbols as possible", but indeed the first references the key as well
user2357 avatar
us flag
I have edited the first book's definitions. Is it better now? I think It relate the statistical properties to diffusion indirectly, in unclear way.
Score:2
ng flag

I vote for the definitions of the first book, because

  • confusion and diffusion matter between anything secret adversaries may seek, and anything related they may have. Both plaintext and the key are in the first category.
  • Confusion and diffusion are not cryptographic operations. They are properties of such operations.
user2357 avatar
us flag
Thank you for your response
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.