Which compound algorithms would weaken cipher, not strengthen it?

Question

OK, in school, some of the lecturers always say "if you compound the crypto, it may make the cipher weaker".

So, which combinations of algorithms would do this? Why? Can anyone show the mathematical proof?

For example, would RSAk1(AESk2[AESk3[x]]) make the encrypted x weaker? Assuming all keys used are different and randomly generated using a SecureRandom function.

Answer 1

Moving my reply from the comments into a proper answer. The general case of double-encrypting is formally explained by Yehuda Lindell in this answer on crypto.SE. Summing up:

• Same Algorithm, same key: It may or may not be secure, depending on the properties of the cipher. It is definitely not always secure, but may be secure for practical cases.
• Same Algorithm, different keys: Secure, because otherwise people who do not know the key could break the encryption by encrypting with a different key, which would be... strange, and not very logical.
• Different Algorithms, different keys: Secure, for the same reason. Otherwise, sending PGP-encrypted eMails over a TLS connection would be unsafe, which would be ridiculous.
• Different Algorithms, same keys: Insecure. Never reuse keys for different encryption algorithms (even when not double-encrypting). For example: If you are using the same RSA keys to sign and encrypt, and the adversary can get you to sign a value for them, it can use you to decrypt data, because signature = encryption with the private key = decryption of data encrypted with the public key.

Summing things up: "Don't double encrypt" is a pretty general hint that definitely doesn't always apply, but it serves as a good baseline to avoid critical mistakes. The more nuanced version is "Don't reuse keys for different algorithms, and to be sure, don't double-encrypt with the same key and algorithm, either, it may hurt you".

Answer 2

It depends if the algorithm and keys are the same, different or one of them is same and the other one is different. On the other side, according to a study combinations of algorithms give better security assurances has been accepted by the designers of TLS and its predecessor SSL. Both TLS and SSL use various combinations of MD5 and SHA1 instead of relying only on a single hash function. The specification of TLS even explicitly states: “In order to make the PRF as secure as possible, it uses two hash algorithms in a way which should guarantee its security if either algorithm remains secure. (The TLS Protocol Version 1.0. Technical Report RFC 2246, T. Dierks, and C. Allen, 1999.)