As was pointed out in Martin Bonner's comment I cannot prove this, but it seems intuitively impossible.
An encryption function is supposed to obscure the plaintext to the point where no information can be obtained about it. If the underlying encryption algorithm can even be determined, that goal has not been achieved.
Is this correct? Can double-encrypting (with either the same or separate algorithms) weaken security?
Can double-encrypting (with either the same or separate algorithms) weaken security?
If you do not assume that the algorithms and keys are independent, then it certainly can.
The example of ROT13 from the other answer illustrates the point even if it is not real encryption. Similarly, a synchronous stream cipher applied twice with the same key will undo itself. Something like that could be possible with other kinds of ciphers, e.g. you could have block cipher such that $E_k = D_{k'}$ if you choose the keys wrong, or you could define AES' where the encrypt and decrypt directions are switched. A combination of these would be secure with independent keys but not necessarily otherwise.
If you assume keys are independent, the result can still be weaker compared to the stronger of the two algorithms. For example, assume you have CBC encryption that is vulnerable to a padding oracle attack. Even if you add a secure stream cipher on top, the padding oracle attack still exists. With some of those assumptions you can say that the combination is no weaker than the first cipher (pdf).
The answers and comments here are good, but I think that it's worth tidying it all up a bit. The question is broad, and this is exactly expressed in the answers. There are multiple questions here. Before I begin, I note that when we talk about the keys not being "independent", we need to define what we mean. I am only going to relate to the keys being the same. If you let the keys be related (e.g., one is the inverse of the other), then it's easy to come up with counter-examples showing nothing is secure. However, in reality we are interested in the same key versus independent keys. We will start with these three questions:
What attacks are we considering as well? If we only consider eavesdropping then it's different to the case that we consider chosen-plaintext attacks. We also need to ask whether we are considering the case that both algorithms are secure or not. (Of course, if they are both secure, then why bother double encrypting. So we'll consider the case that it's only guaranteed that one is secure later.)
Let's start by answering the above three questions:
A more interesting/important question is whether double encryption is secure when one of the schemes may be insecure. In general, constructing a scheme that is secure from a number of schemes where only some of them are secure has many advantages. The first construction of HMAC used a combination of SHA1 and MD5 for this reason. Formally, we call such constructions robust combiners. Regarding double encryption, this is the cascade research here.
Sure, if we're not limiting the cipher. One simple example is double ROT13, which is somewhat weaker than single ROT13.
I would say that the answer is yes, if the first and second encryption algorithms are the same algorithm but with different keys.
Most probably in the above case, a third encryption key would do a single decrypt of the result. If the algorithms are disjoint (like aes and twofish) and each uses a different key, I would say no, it is more robust. I would do a AES encryption followed by a Twofish encryption, along with cypher block chaining between the first and the second. (if using CBC make it three algorithms, then drop the CBC).
