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.
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.
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.
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.
No, it's less secure because:
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.
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.
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.
Short answer:Yes, as long as you don't misuse it, it will be just as secure as the original block cipher. Much like a live grenade if you aren't careful it will explode in your face.
DISCLAMER: It's good to be curious about cryptographic primitives but this stuff will blow up in your face unexpectedly. I've written code vulnerable to hash length extension attacks. Don't use custom stuff in production.
The goal of a block cipher's key schedule is to produce somewhat random round keys. This is a balance between performance when frequent re-keying is required (EX:webserver with 1000 clients) and mitigating against programmer stupidity(more later), AES has a very simple key schedule and especially 192 and 256 bit variants are showing strain.
AES128 can be turned into AES(128*10) by getting rid of the key schedule and feeding in round keys directly. Doing so is extremely dangerous but only if you misuse the resulting block cipher (much like you can misuse AES itself by using it in ECB mode). The danger here comes from related key attacks. If the attacker can flip key bits individually (which in this case translate directly to round key bits) they can find the key easily. This is like reusing a nonce in ECDSA. But this is only possible if you give them related keys. Like if you put a message number counter in the key. That's not some far-fetched rare thing. Remember WEP? The utterly broken standard for WIFI network security. It called for putting a message counter in the RC4 key. LAter on someone found a related key attack. Thanks to its key schedule, unmodified AES can cope with that. AES(128*10) will, metaphorically, explode.
AES(128*10) round keys must be generated using a strong pseudorandom function (like KACCAK as you were doing before). AES itself though, is such a function so if code size is a concern don't hesitate to use normal AES in CTR mode to generate round keys for your custom AES1280. The result will be no less secure than the original.
One more disclaimer: AES is tricky to implement securely. Start with an existing, known safe implementation like the one in openssl.
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.
