4
$\begingroup$

I am aware of at least , , and variations of 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?

$\endgroup$
  • 5
    $\begingroup$ You can't compute in parallel things that depend on the output of each other. $\endgroup$ – mikeazo Sep 30 '14 at 23:25
  • $\begingroup$ @mikeazo : You can; it just takes a number of processors proportional to the number of potential outputs that don't get ruled out. $\endgroup$ – user991 Oct 1 '14 at 0:06
  • $\begingroup$ @RickyDemer what does this mean ? "don't get ruled out" $\endgroup$ – sashank Oct 1 '14 at 1:32
  • 3
    $\begingroup$ @RickyDemer I think that for crypto, that first comment misses a smiley :) The potential number of outputs would be a bit high. $\endgroup$ – Maarten Bodewes Oct 1 '14 at 7:56
  • 2
    $\begingroup$ Please note that encryption usually takes a limited number of bytes. Now it seems you are using a smart order of encryption primitives (largest block size last, EC(IES) first), but it is something that already makes the encryption scheme more complex. $\endgroup$ – Maarten Bodewes Oct 1 '14 at 7:59
6
$\begingroup$

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:

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But that is under the rsa assumption, right? You might not have to factor anything or even solve any NP hard problem. $\endgroup$ – Einar Oct 1 '14 at 13:23
  • $\begingroup$ @Einar, yes, but recall that any result contradicting this assumption would definitely be a breakthrough. $\endgroup$ – mczraf Oct 1 '14 at 13:36
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ OP already tagged the question with the multiple-encryption tag… so pointing OP to “superencipherment” (which is a synonym of “multiple-encryption”) doesn’t really make sense. The rest of your answer reads more like a comment than an answer. Maybe you could edit it to make it a bit more valuable? $\endgroup$ – e-sushi Oct 1 '14 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.