2
$\begingroup$

I'm wondering whether encrypting data with two different 256-bit ECC keys will result in a more secure encryption (minimum 384 bit equivalent) or will result in data that's effectively encrypted with a different (unknown) 256-bit key (or weaker). The keys will be different, but will be based on the same curve.

Another acceptable option would be to do something like encrypt / decrypt / encrypt with 3 different keys (like Triple-DES, but with ECC), again based on the same curve.

I'll be using a hardware crypto chip that can do ECC encryption with 256-bit keys (uses "NIST standard P256 prime curve"), but I'd like to be able to have something a bit more secure, and I don't want to have to switch to software encryption (speed and memory limitations in an embedded device).

The purpose of this is to encrypt keys for general distribution, so the cyphertext will be public, with access for an extended period of time (several years).

I'm a programmer, not a mathematician, so please phrase answers accordingly.

$\endgroup$
  • 2
    $\begingroup$ This is not the time of DES anymore, a single encryption is literally good enough. $\endgroup$ – fkraiem May 28 '16 at 5:24
  • $\begingroup$ The answer whether double encryption is more secure really depends on the details of how you combine the encryption algorithms. Having said that, there are certainly ways to properly do double-encryption (which all require a bit (to a large amount of) more bandwidth / storage) $\endgroup$ – SEJPM May 28 '16 at 18:33
  • $\begingroup$ why use two of the same thing? if they can break one, why not the other? if they have enough time/smarts/boxes to break one, surely a mere doubling would not make or break their abilities... $\endgroup$ – dandavis May 28 '16 at 20:15
  • $\begingroup$ fkraiem: The projected lifespan of this product will be about 10 years. I expect 256-bit ECC to be crackable by then. This is why I'm looking for a stronger key length. $\endgroup$ – Peter May 29 '16 at 15:20
  • $\begingroup$ @SEJPM: The details are what I'm looking for. If anyone knows how to do this, and can publish the data, I'd be very interested. Bandwidth and storage aren't a major problem, as this is being done in a hardware crypto chip (currently looking at the Atmel ATECC508A - atmel.com/devices/ATECC508A.aspx). $\endgroup$ – Peter May 29 '16 at 15:33
2
$\begingroup$

TL;DR: If you separate the keys then you're fine.

In my answer I'll outline an encryption algorithm using two ECC keys and achieving (nearly) squared security and the general result for how to properly use two keys in group-based cryptography.

First note that a private key $a_1$ is a random integer used to multiply a base point on elliptic curves like $P=a_1\times Q$. Now observe that adding a second key $a_2$ to the mix yields $P'=(a_2\cdot a_1) \times Q$ which is equivalent to some $P'=k'\times Q$ and thus not stronger than simple discrete logarithm.

Now if you were to calculate two different public keys, security of these keys will actually multiply: $P_1=a_1\times Q, P_2=a_2\times Q$ requires you to break both instances of the elliptic curve discrete logarithm problem (ECDLP). The best speed-up for your keys only would be $\sqrt2$ which is absolutely negligible if we are talking about numbers like $2^{128}$.

On a side note it may be noted that this idea is obviously true, because you've just created two ordinary, unrelated public ECC keys (on the same key) of which you can find many, many more samples on the internet (all with the same type of mathematical relation). Also note that this independence doesn't hold for finite field discrete logarithms as the Logjam attack has demonstrated impressively.

So in (first section) conclusion one could say: If you don't relate your public keys (and you use multpiles) you're fine.


Now, how can we use this actually for proper encryption. There are multiple ways to do this:

  • Do a standard KEM/DEM encryption and use ECDH twice for the KEM part
  • Do an ordinary ECC encryption (ECIES?) and just apply it twice with different private keys to the message.

The first approach should only be preferred if you don't already have a (working, tested and known-safe) implementation of ECIES (or some other ECC based encryption) at hand. If you dou have such an implementation, by all means use it and apply it twice (with different private ECC keys) and you're done.

If you don't have such an implementation, you have to go for ECIES. I'll leave the details to Wikipedia, but in a nutshell, ECIES works with two functions to encrypt data: $\operatorname{Encaps()}$ and $\operatorname{Encrypt()}$. Encaps will provide you with a session key which you can use to bulk-encrypt the data as well as with some data that allows $\operatorname{Decaps()}$ to recover the session key (given the private key). In ECIES, Encaps basically is ECDH: You put in the public key, it chooses a random exponent and will output you the exponent multiplied with the basepoint ($P_s=k\times Q$) and the hashed ECDH result ($s=H(x(k\times P))=H(x((k\cdot a)\times Q))$) which you then can plug-into the bulk encryption. Now what you do, is you use Encaps twice (with two different public keys obviously) and the securely combine the keys together (e.g. using HKDF).

Now the bulk encryption should also be at a comparable security level ($\approx$ 256-bit) and if it is, then you should be safe until general quantum computing is able to break ECC.

$\endgroup$
  • $\begingroup$ As we're only encrypting one or two 256-bit keys, there's no bulk encryption, only key encryption. I need to dig through this answer a bit, but it feels like what I'm looking for. $\endgroup$ – Peter May 29 '16 at 21:33

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.