Security importance of Key Schedule in Block Cipher

Question

For example block cipher AES-128, Key size is 128bit and it is used to make a 10 round key which is total 320bit.

Question 1. If i use another Key schedule algorithm in AES, then security decreased or remain same? In other words, if the key schedule algorithm of AES has some relationship with AES encryption itself, then it will be decreased, or it will be same if the new key schedule algorithm is safe enough.

Question 2. Why we expand key? brute force will take O(2^128) time regardless of the key schedule is strong or not. what is the advantage of making key expend? I was curious about this when I was learned about 3DES. Which developed because the former DES has weak key length 56bit so vulnerable to brute force attack, i was wondering why doesn't they just remove key schedule process and use the whole round key as a key.

Answer 1

If i use another Key schedule algorithm in AES, then security decreased or remain same?

This really requires a concrete proposal for an alternative key schedule in order to conclude whether or not it would constitute an improvement or a weakness.

The AES key schedule is not exactly ideal, but the rest of the design seems to be strong enough such that this does not really matter in practice. So the practical security would probably not be modified. The key schedule is almost surely the weakest part of the AES algorithm; The fact that it is secure as-is implies it probably would not make a gigantic difference to modify the key schedule.

I bet if we tried, we could come up with some kind of pathological example that would lead to a weakness, but I can't think of one offhand.

Question 2. Why we expand key? brute force will take O(2^128) time regardless of the key schedule is strong or not. what is the advantage of making key expend?

This is a very good question that I have wondered about myself. I do not think I have ever seen explicit justification in a cipher proposal for why round keys are derived and applied exactly as they are - as in: "By deriving our keys this way and applying them at this specific interval, these attack(s) are prevented"

One thing that it accomplishes is that it makes each application of the round act differently. Symmetry of various kinds can be used in an attack against the algorithm.

I have seen a few papers that were specifically about the importance and design of key a schedule. Basically, they advocate ensuring full diffusion of the key and ensuring that, given one portion of a round key, it should be difficult to derive any other portions of the key.

So, hypothetically, if you used a fully diffusing, unpredictable, one way function as your key schedule, then recovery of one round key would not assist in recovery of other round keys.

Interestingly, I have found justification for NOT using a key schedule: The cipher LED utilizes no key schedule, and is resistant even to related key attacks because of it. It relies on the round constants to simulate independent round keys.

I was curious about this when I was learned about 3DES. Which developed because the former DES has weak key length 56bit so vulnerable to brute force attack, i was wondering why doesn't they just remove key schedule process and use the whole round key as a key.

Since the DES key is only 56 bits, just using it directly would not be an improvement. Also, the DES key schedule pretty much does just use the key directly: It does pull from different bits over the course of different rounds, but it's really just re-ordering the bits of the key, and not really deriving a new/different one. Also note that 3DES utilizes more master key material then regular DES.

Answer 2

A complementary answer to @Ella Rose's nice answer.

Let's say you are the designer. What exactly would you do without a key schedule? You must use the key bits in some way. Otherwise your block cipher is worthless.

Do you accept the formalism of iterated multi round ciphers, where the same round structure is applied repetedly? They strike a balance between speed and efficiency. If not, you'll have a very slow cipher.

Will you apply the same key bits (say all of them) again and again? This would make the rounds after the first a deterministic functions of the first round output, with no entropy left. Bad idea.

So you'll apply either different subsets of the key bits at each round (a la DES) or use a key schedule of some sort. This goes back to Shannon's paper during WWII (declassified later as "the theory of secrecy systems" or a very similar title).

Finally, using Orthogonal Arrays, a combinatorial object, one can obtain Perfect Local Randomizers, due to Maurer and Massey which converts a uniformly random $n-$ bit strong to a much longer $k$ bit string so that any $e$ bit subset of the output string are independent, uniformly random and independent of the input string. An ideal key schedule, if you will. MDS codes play a role here as well. The original paper is here