A block cipher with independent keys for each round

I want to modify a standard block cipher in the following way. I replace each round key by a key picked at random. Is this block cipher as secure as the original one ?

Thank you.

EDIT

Some missing information related to the question, according to comment by OP to one of the answers:

My question is related to the key-schedule of AES, I wonder if we can replace it by something more stringent and be sure that the security will not be not worst than the original one.

-
One of my experiments involves using Keccak (c=1024) as the key schedule, with the squeeze truncated to the block size (128-bits for AES), and a new squeeze for each round key. This should maintain nonlinearity of round keys, and allow a more appropriately sized cipher key length. Key changes are substantially more expensive. – Richie Frame Nov 4 '13 at 3:56
I would consider the practical problem with such a large key algorithm to be "where to get independent bits as key material". As the keying material is likely not going to be independent, related key attack may be concern. – user4982 Jan 31 '14 at 17:40

John Kelsey, Bruce Schneier and David Wagner proposed paper "Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES" and they presented new attacks on key schedules of the block ciphers. About "A 768-bit DES variant uses independent round subkeys" they said:

A 768-bit DES variant uses independent round subkeys [Ber83]. This variant will be much weaker in some situations: there is a very simple related-key attack needing just 15 related keys and 60 chosen plaintexts. Obtain the encryptions $E(k, p)$ and $E(k' , p)$, where k is obtained from k by flipping some bits in the last round subkey; this can be thought of as a differential $1R$ attack with a characteristic of probability 1. The last round subkey can be recovered with four chosen plaintexts, and then we can peel off the last round and repeat the attack on 15-round DES. This attack can also be optimized for the case when related key queries are very expensive to achieve a complexity of one related key and $2^{16}$ or so chosen plaintexts. For nearly any product block cipher, if it’s possible to flip bits in a cipher’s expanded key, it’s possible to mount an XOR differential attack on the last round of the cipher. This may be useful in attacking some systems that leave expanded keys vulnerable to change.

So if the algorithm is DES the answer is: NO.

Charles Bouillaguet, Patrick Derbez, Orr Dunkelman, Nathan Keller and Pierre-Alain Fouque proposed "Low Data Complexity Attacks on AES". They said:

We present several attacks on up to four rounds of AES requiring up to ten chosen plaintexts. Most of the attacks are based on the meet-in-the-middle approach. Some of the attacks exploit heavily the AES key schedule, while others apply even if the subkeys in AES are replaced by independent subkeys. The attacks are summarized in Table 1.

The attacks are applicable to up to 7-rounds of Rijndael. Since the minimal number of rounds in the Rijndael parameter settings proposed for AES is 10, these attacks does not endanger the security of the cipher.

By now there isn't any attacks against full-rounds of Rijndael key schedule or full-rounds of Rijndael with independent subkeys.

So if the algorithm is AES the answer is: By now YES
But the answer is depending on future researches. And in general the answer is depending on the algorithm.

-
Actually, the attack that Kelsey et al proposes for DES with independent subkeys can easily be applied to AES with independent subkeys. Hence, if we consider related key attacks, the answer for AES would be No as well. – poncho Nov 2 '13 at 10:34
In the related key scenario, allowing independent round keys always offers a lot more variables to modify, but the attacker could also just use the "valid" combinations, which agree with the usual key schedule. The attack with independent round keys therefore is stronger than the common related key attack (probably even strictly stronger). And therefore "security is weaker". – tylo Sep 7 '15 at 11:22

This question can be answered in several way depending on the exact meaning you intend for more secure.

First answer: No, it is not more secure in general. The most you can expect is "at least as secure" not "more secure". A typical example of this behavior is Even-Mansour encryption where using twice the same key is as secure as using two independent random keys (see http://eprint.iacr.org/2011/541.pdf‎).

Second answer: Yes, it is at least as secure, because the goal of the key schedule is usually to derive random looking round keys from the cipher key.

Third answer: No, it is not as secure, because it is more vulnerable to related key attacks. Or more precisely, related round-keys attacks become ordinary related key attacks which weakens the security level.

Fourth answer: No, it is not secure, because it is very unlikely that the modified cipher attain the expected security bound for a cipher with such a long key. [For example, using this idea with AES gives a 1000+-bit key and I would be surprised to hear that you attain the $2^{1000}$ security level.] This is one of the reasons for which Triple-DES with 2 keys is usually prefered to Triple-DES with 3 keys.

So it would be useful to specify more precisely why you would like to do this and what is the definition of security you are considering in your context.

-
In your fourth answer, you want to says "not more secure?". I'm not looking for a $2^{1000}$ security level. I wonder if this modified AES (with fixed random round keys) is better able to achieve the security that the original AES should fulfil (attain). – Dingo13 Jul 5 '13 at 21:33
No. I want to say not secure. Because many theoretical cryptographers consider that something that does not require close to exhaustive key search is broken. I just wanted to emphazise that you need to define the security notion you have in mind more precisely. – minar Jul 5 '13 at 21:44
I don't have a specific security notion in mind. I just wonder if we had to choose between an AES with a key schedule and an AES with independent round keys, which one should be preferable ? From the point of view of security, not key material length... In other words which one seems to be the most vulnerable... – Dingo13 Jul 5 '13 at 21:52
Then consider that I don't want more security than AES should give me... But I want to lessen the power of well known attacks. – Dingo13 Jul 5 '13 at 22:00
What kind of attacks ? If you only consider crypto attacks on the block cipher in the standard model and isolated from its context, your proposal is normally fine. However, you are weakening the security against related-key attacks and probably easy the work of an adversary that tries to attack a combination of key-exchange + block cipher. So if your goal is just to increase security, it is preferable not to do that. – minar Jul 6 '13 at 7:33

No, it's less secure because:

• you're not using the algorithm in the way the author(s) designed it
• it hasn't been subjected to scrutiny by trained cryptographers

If you don't know the above already, you certainly don't have enough experience in cryptography to tinker with the inner-workings of algorithms/modes. Stick with the standard algorithm/mode, it's a much safer bet.

-
However the key is longer in the proposed modified scheme. Besides, if we consider the original scheme, the round keys are related from the master key, intuitively should this not imply a lower security ? – Dingo13 Jul 5 '13 at 17:39
"No, it's less secure because: - you're not using the algorithm in the way the author(s) designed it -it hasn't been subjected to scrutiny by trained cryptographers" Authors have designed a system with related (derivable) round keys by a desire of short key length ? Not ? – Dingo13 Jul 5 '13 at 17:44
The key being longer does not inherently discount the possibility of having introduced a weakness by changing the algorithm. Besides — if you're dealing with a modern cipher of at least 128 bits, key length is hardly a concern. At 256 bits, it would likely never be brute-forced before the heat death of the universe. So what problem are you trying to solve, exactly? – Stephen Touset Jul 5 '13 at 18:48
Concrete example: There are better attacks on AES-256/192 than AES-128 because the key schedule is weaker. – pg1989 Jul 5 '13 at 20:18
@pg1989 Which only apply if you use AES with non random keys. Related key attacks are only relevant if you want to use AES in unusual ways, for example by building a hash function from it. – CodesInChaos Jul 5 '13 at 20:28

This is at least as secure as the original cipher.

The only case I can think of where it would be less secure is if the security of the cipher relied on some special relation between the round keys, but I don't know of any ciphers that have this requirement. Most ciphers derive their round keys from the encryption key in a linear way.

One example of a cipher that does something similar to this is Blowfish. It uses the encryption function as a pesudo-random function to generate the round keys.

-
Thank you. This was what I think but what about key-related attacks ? – Dingo13 Jul 5 '13 at 18:38
I would argue that in a cipher where key size is equal to output block size, no security is gained. Assuming the cipher is capable of generating all (or even most) bit sequences of its block size, encryption as described would be effectively no different than encryption with some key of the standardized length. – Stephen Touset Jul 5 '13 at 18:50
In the random case, there is no relation between the round keys. This makes the cipher more difficult to attack. For example in AES, the key schedule is invertible, so if you have one round key, you have them all. This is not the case with random round keys. – user7487 Jul 5 '13 at 18:58
@Stephen Touset. I've not well understood what you are saying. You say that I can introduce a weakness by replacing round keys by independent random keys ? – Dingo13 Jul 5 '13 at 19:45
In the comment above, I'm saying that if there is a 256-bit key and 256-bit block size, randomizing the subkeys must produce output identical to the output of some key using the cipher as originally described. – Stephen Touset Jul 6 '13 at 5:44

If a cipher has independent round keys, then it is trivially susceptible to a meet-in-the-middle attack. Independence of the rounds means you can brute force the first half of the rounds and second half of the rounds separately. A cipher with independent round keys totaling $n$ bits can be brute forced in $2^{n/2}$ time. So, from the point of view considering key length alone, this is not a very good cipher.

However, it is likely that $n/2$ is much greater than the key length of the thing you started with. And it seems very plausible that the cipher could actually achieve security in the neighborhood of $2^{n/2}$ (as opposed to $2^{n/2}$ just being the obvious upper bound). Heuristically at least, the key schedule is supposed to derive many "independent-looking" keys from a single key. So the cipher may have been designed and analyzed based on the heuristic that is now the reality.

So I don't think it's a big stretch to consider such a cipher to be secure with $n/2$ bits of security, though it's not the most aesthetically pleasing way to get $n/2$ bits of security.

-
"So, from the point of view considering keylength alone, this is not a very good cipher." I'm agree with you that it's totally useless to desire such a long key. Meet-in-the middle-attack is not feasible (not interesting) with such a long key. In fact I don't want $n/2$ bits of security (with $n=10 \times 128$), my question is just about the relative security. I wonder if we can have the same security than the standard AES by having independent keys by round, that's all. – Dingo13 Jul 13 '13 at 14:32

A good block cipher makes each bit of the ciphertext depend on every bit of the key and every bit of the plaintext. By making the key longer and only parts of it involved in each round you break that property for algorithms designed to achieve it. It is therefore less secure.

-
You speak about the security that we should have corresponding to the bitlength of the key. I don't want security equal to the bitlength of the key, I wonder if for a security of 128 bits, having one key by round is as secure than the original AES. – Dingo13 Jul 13 '13 at 14:22
You don't interpret correctly my question. – Dingo13 Jul 13 '13 at 14:23
Answered as asked, but after the edit, I recommend the answer from ir01. – Árni St. Sigurðsson Jul 14 '13 at 14:34

If each round key is of the same size of the block to be encrypted and all round keys are truly randomly generated independent from each other, then we have OTP. This is similar to using a truly randomly generated key of the same size of the plaintext to be encrypted. Each bit of this key is used only one-time to encrypt one plaintext bit.

-
AES key is already at least as long as the block, but that does not make it equivalent to OTP (among other things because it's typically used to encrypt many blocks). Why would independent round keys to that? – otus Aug 4 '15 at 6:12