Why are we not using multiple ciphers per message?

Question

I am aware of at least rsa, elgamal-encryption, and variations of elliptic-curves relying on different problems and that those problems are considered hard.

However, if someone figures out a way to break this security, it's hard to imagine the consequences. Or what if some intelligent service published certain elliptic curves, where they knew some shortcuts to in the decrypting process?

My question is: why don't we combine these systems to avoid such crypto-catastrophy?

Consider: $C = EncryptWithRSA(EncryptWithEG(EncryptWithECC(M)))$

This could possibly be computed in parallel, so we with today's quad-core mobiles. I don't remember ever waiting for an SSL connection to come anyway, so guess I would hardly notice a threefold delay. Why are we not doing this?

Answer 1

I don't know about computing things in parallel, so I will ignore that part of the question.

First, please note that the encryption algorithm is rarely the the weak point of the security. It is far more likely that

• you will have problems with the implementation,
• some spyware installed on your computer,
• a weak password (If you use qwerty as your password, it doesn't matter how awesome your algorithm is).

That is, you have to remember that security is about much more than choosing a nice algorithm.

Second, the security of, for example, AES has been studied and it is secure. There are no known practical attacks that breaks AES (assuming strong password of course). So using another algorithm doesn't really do a whole lot more.

That said, you can of course do it. But again, if you really want to do it, you have to do it right. I am sure that in your studies of cryptography you have come across the idea that you should not "roll your own crypto". And in some sense, combining two algorithms, you risk violating that principle. If you, for example, had an implementation of AES that as output produces a file that always starts with, say, 10 bytes identifying the file as having been encrypted by AES (your implementation?), then (since you can assume that your attacker knows your method of encryption) an attacker know has part of the plaintext for the second encryption. (This is not necessarily a problem!) This doesn't give it all away, but you have now given an attacker some information that he might be able to use. Another problem is if you accidentally pick two algorithms where one undoes part of the other.

The point is, that there is a good chance that you will make a mistake in doing the actual implementation of the combination of the two algorithms.

But, if you get all this right, then sure, it would be perfectly fine to encrypt as you suggest. In fact, some might already be doing things like this.

To finish let me quote a blog article:

... It's entirely possible to combine encryption schemes in secure ways (many of which are not cascade constructions), but the amount of extra security you'll get is subject to some debate.

Other interesting things:

• http://eprint.iacr.org/2002/135.pdf
• https://security.stackexchange.com/questions/32247/will-double-encryption-increase-the-security-of-cipher-vs-bruteforce
• How secure is AES-256?

Answer 2

They rely on problems not so different as you might think.

They are based either in the factoring problem or in the discrete logarithm problem, which have a deep connection between each other. Once you have an algorithm that can efficiently solve one, you most likely would be able to adapt it to reproduce an answer for the other in polynomial time.

Thus your strategy to apply several layers of encryption becomes useless.

A good way to analyze the close connection between these two problems is Shor's quantum algorithm, which is able to break both of them in polynomial time… in a quantum world.

Answer 3

Basically you are talking about “superencipherment”. This has a long history in cyptography, but it eats up space like crazy. Your observation of PK cyptography being vulnerable is true. Solving 'Prime' would bring the house down.