Score:0

What is the need of substitution and permutation networks in AES?

ec flag

I have tried to answer this question for quite some time now. But a complete intuitive understanding still eludes me.

Consider an alternate construction for a block cipher without any substitution and permutation network. This block cipher just XORs the message blocks with different keys which are derived from a master key(similar to ECB mode but with different keys for each message block). If the key expander which generates multiple keys from a single master key is cryptographically secure then the resulting block cipher should also be cryptographically secure. I am pretty sure my reasoning is incorrect but I am unable to pin point the error.

Any intuitive explanations on why this construction is not good and why we need substitution and permutation networks in AES are welcome.

fgrieu avatar
ng flag
Hint: consider your alternate construction's encryption function for a fixed secret key. What's $E(A\oplus B)$ (where $\oplus$ is [bitwise exclusive-OR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)) w.r.t. $E(A)$ and $E(B)$? Would that property be expected from a random permutation? How does it harm security?
Abhisek Dash avatar
ec flag
Can you please elaborate what A and B represent?
fgrieu avatar
ng flag
In my comment above, $A$ and $B$ are arbitrary inputs of the block cipher under consideration (otherwise said: arbitrary blocks of plaintext). If that was AES-192, $A$ and $B$ would be arbitrary 128-bit bitstrings.
Abhisek Dash avatar
ec flag
Are you suggesting to encrypt both A and B with the same same key? If I reuse the key this will cause a two time pad issue. So the substitution permutation network prevents this by obfuscating the input-output relationship. Is that correct?
fgrieu avatar
ng flag
Yes, I suggest to examine the consequence of encrypting both $A$ and $B$ with the same same key. That's part of the intended use of a block cipher: it's should remain safe even if the same key is used with many different blocks. And indeed key reuse would be unsafe with the construction considered in the question, for reasons related to what happens when a pad is reused in the One Time pad.
Score:0
vn flag

This block cipher just XORs the message blocks [...]

The fact that you talk about "message blocks" here suggests that you're working from one of those awful beginner (mis)definitions of "block cipher" that say that it's a cipher that encrypts a variable-length message one block at a time. Lots of introductory explanations say that, but that's just not how the term is used by actual cryptographers, so I find that (supposedly) beginner friendly "definition" just wrong and confusing.

A block cipher in theoretical cryptography is an algorithm that's intended as a real-life implementation of a pseudorandom permutation family—a secret-keyed algorithm that implements a function that scrambles fixed-length blocks of data in a fashion that cannot in practice be distinguished from a randomly chosen permutation of its domain. This answer on this site goes on at quite a bit of length about it.

What you mean precisely by "block cipher" here is critical because if you're going with the "cipher that encrypts variable-length messages one block at a time" thing that I criticize, then your proposal here:

This block cipher just XORs the message blocks with different keys which are derived from a master key

...is actually a sound way of constructing a secure variable-length cipher from a block cipher (in the proper sense). The widely used CTR mode of operation in fact works along these lines—you generate the key stream (what you call the "different keys which are derived from the master key") by applying the block cipher to a message block counter.

There is a huge gap in your proposal, however, because you don't say how to derive the sub-keys from the master key, other than to assume it is "cryptographically secure"—what does it mean for it to be secure in this application, and how do you achieve it? Actually, this is a great segue into your mention of substitution/permutation networks, because that's the "special sauce" that AES is using to satisfy that requirement, that you can't achieve at all if all you have at your disposal is a master key and XOR.


So, to restate and summarize:

  1. In spite that a ton of beginner materials out there say that a "block cipher" is an algorithm that encrypts a variable-length message one block at a time, that's not the actual technical definition in cryptography.
  2. Your idea of encrypting a variable-length message by splitting it into blocks and XORing each independently with keys generated with a "key expander" is, at its heart, sound and very common.
  3. However, you gloss over how your key expander would work, and that is precisely where techniques like substitution/permutation networks (or alternatives like Feistel networks) fit in. It's one of the things makes AES suitable to use as your "key expander" for this application.
Abhisek Dash avatar
ec flag
Thank you for your detailed answer. I guess all I am asking is if the keys generated by my "key expander" are indistinguishable from random then do I still need a substitution permutation network within my block cipher? Or can my block cipher can just XOR message blocks with keys generated by the key expander (a bit like a stream cipher)? I suspect that if my message needs to be padded then this construction may leak values of the key but for simplicity assume that there is no need to pad. I realize cryptography is complex and there will be many corner cases that I have to account for.
Abhisek Dash avatar
ec flag
I got your explanation now. Will continue to explore further.
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.