[n3k5]

I gave an intuition for how it can happen that combining algorithms (in a bad way) results in weaker encryption — without claiming that it must always happen.

If we move the goalposts to where the combined algorithm receives a much larger key than any of the individual parts we're comparing to in terms of crackability, then the likely failure mode isn't ‘weaker’ any more, but ‘stronger, though maybe not as much stronger as was intended’.

The history of triple DES provides a nice practical example: ‘double DES’ isn't a thing because encrypting already-DES-encrypted data with DES again, with a completely separate key (thus effectively doubling the size of the key), does almost nothing to improve security.

[LeCow]

To support your point. I've used these weaknesses to break crypto algorithms in the past.

A typical example is the crapto-1 Mifare Classic algorithm used to encrypt NFC cards. The way they read from the shift register and combine the bits was dumb and it's complexity weakened the algorithm.

Another I've seen is using two sequential keys XORd against one another to produce and "encryption" key. Turns out reading from low entropic systems very quickly yields a similar enough key that when XORd, partially removes the first one.

[beagle3]

Can you give an example (or at least a sketch) of how, e.g. AES-128 on top of, or below, DES, is weaker than either?

The claims of "weakened by combining" are often aired, but all examples I've found so far are basically summarized as "remaining within a group structure" (as in your rubik's cube example whose god number is 20) - which might not be stronger than each individual, but is unlikely to be weaker either -- and algorithm combinations usually DON'T remain within a group structure (e.g. DES is not a group, so 3DES is strictly stronger than DES, even if it might not be 3-times strong in bits)

[kortilla]

Yes, the problem is that you are confusing key re-use with layering algorithms. Key re-use is bad, layering algorithms is not.

Without key re-use, there is no way adding another algorithm can weaken an existing encryption.