2

It's been a while and I'm still trying to figure out if my understanding of ECC crypto is correct.

Basically from what I understood a purely asymmetric encryption is never used. Usually the asymmetric encryption is used to share a common symmetric key, and then use that to share information. This is faster and more flexible than a pure asymmetric encryption..

For the following examples, let's say Alice wants to send Bob a message, and both of them already know the public key of the other.

Now, with RSA the procedure is roughly:

  1. Alice generates a random key (for instance, a 128-bit key)
  2. Alice encrypts the key with Bob's public key
  3. Alice sends the encrypted key to Bob
  4. Bob decrypts the key with his private key
  5. Alice sends the data encrypted with the key generated in point 1; Bob can decrypt it with the key decrypted in point 4

When switching to ECC, however, there is not a real encryption proceedure, but just a key exchange through the Diffie-Hellman protocol. With ECDH if I understood correctly the procedure is

  1. Alice calculates the shared secret
  2. Alice sends the data encrypted with the key calculated in point 1
  3. Bob calculates the shared secret too, and decrypts the message

Now, the second method strongly reminds me of this other question: How secure is static key encryption?

Does the fact that ECDH re-uses the same key (while with RSA key exchange you generate a random one every time) make it less "secure"*? If so, in which cases?

  • I used the word "secure" on purpose, to indicate a very generic threat; if there are some threat models to which this is vulnerable please indicate it

I just discovered (when writing this question) that there exist a variation of the ECDH which uses ephemeral keys (ECDHE), but I could not understand whether this is similar to RSA key exchange or not. If this protocol is used to change arbitrary keys using ECC, please provide some resources from which learn how they work, or libraries that implement it.

Additional info: if this can narrow down the scope of the question, I'm more interested in embedded systems rather than servers, so my reference point are libraries such as micro-ecc

2

Your understanding is broadly correct, but in security and especially in cryptography, “broadly correct” often doesn't cut it.

There is a standard for encryption using elliptic curve cryptography to encrypt data, called ECIES (Elliptic Curve Integrated Encryption Scheme). (IES can be used with other key agreement methods, but only elliptic curves give it practical advantages over RSA — faster decryption, smaller keys.) The procedure is as follows.

  1. Alice obtains Bob's public key on the selected elliptic curve.
  2. Alice generates a random key pair on the selected curve.
  3. Alice calculates the shared secret for Bob's key .
  4. Alice passes the shared secret as input to a key derivation function (KDF).
  5. Alice uses the output of the KDF as a key for symmetric authenticated encryption.
  6. Alice sends the resulting authenticated ciphertext and her public key generated at step 2 to Bob.

The KDF step is important because a shared secret generated with ECDH is not uniformly pseudorandom. An attacker may be able to get partial information about it by simple mathematical observations (for example, the shared secret is a number between 1 and N where N is not a power of 2, so the highest bit is biased towards 0), by conducting key agreements with Alice using a series of intelligently-crafted keys, or by observing side channels from the ECDH computation. Partial information about the key can allow a related-key attack on the symmetric cipher. Passing the shared secret to a KDF “scrambles” any mathematical relations in the output.

In RSA-based hybrid encryption, the same symmetric key is never generated twice because it's generated at random. In ECIES, the same symmetric key is never generated twice because it's derived from an elliptic curve key that is generated at random.

The calculation of the shared secret is exactly the ECDH calculation. It's sometimes known as “ephemeral (elliptic curve) Diffie-Hellman” because the private key is single-use. Ephemeral and non-ephemeral Diffie-Hellman are the same algorithm, what “ephemeral” means is that the key is used only once.

From a cryptographic point of view, the output of the KDF can be used to encrypt more than one message. (But always with the same algorithm. Using the same key for two different algorithms, e.g. for both AES-GCM and AES-CCM, or for both AES-GCM and Camellia-GCM, could be anything from a subtle weakness that reduces the security by a bit and a half, to a catastrophic weakness that makes it easy to recover the encrypted message.) After all, if you have a symmetric key, it doesn't matter how you got it. Whether you'd want to do that is an operational matter: how much of a risk is there that Alice or Bob will accidentally leak the symmetric key? How much of a risk is there that Alice will generate the IV incorrectly for the symmetric encryption step? If you aren't worried about these risks then you can treat the symmetric key generated from the shared secret like you'd treat any other shared key, minus the problems of distributing this shared key.

Alice can perform the shared secret generation with the same inputs more than once if she wants: she'll get the same output each time, so that won't provide extra information to an attacker. The danger if Alice reuses the ECDH key is that this creates more risk that the key will leak, either from storage or through side channels.

It's even safe for Alice to use the same key pair to communicate with more than one party.

Just because everything is safe in principle doesn't mean it's a good idea. The more you leave a key lying around, the more risk there is that a partial compromise will reveal this key.

A common reason to reuse the ECDH key is to put it in a high-security piece of hardware that will perform operations with the key but not reveal the key itself: smartcard, secure element, HSM. However, this is useful for Bob, not for Alice. Bob needs to somehow send his public key to Alice in a way that Alice will trust, and after that he needs to hold on to the key. On the other hand, there is no strong advantage for Alice to reuse her ECDH encryption key, since she'll send the public key as part of the message.

A valid reason to reuse the key is if you have stringent constraints on message length. It lets you save about 65 bytes (size of an uncompressed point representation on a 256-bit curve) can be useful.

Performance, on the other hand, is not a strong reason. Generating an EC key is extremely fast: it's just a uniform bit string of the right length (this is unlike RSA where key generation is very expensive). You need to add the time it takes to calculate of the public key, and that's basically the same calculation as the ECDH calculation. So setting up ECIES-like encryption with a stored key instead of generating the key only divides the time of the asymmetric-cryptography part of the computation by two.

Finally, note that even if you reuse the EC key, you can still derive as many symmetric keys as you want. The KDF step takes an optional extra input which can be public. This extra input is variously called a salt, a label, an info string or various other names. You only ever get the same KDF output if both the secret input and the salt are the same.

  • Thank you for this very long reply. I totally agree on the very first part, and that's the reason why I asked the question... So, if I understood correctly, the ECIES (also called ECDHE) is like the "classic" ECDH, with the difference that the sender (Alice) has a very short-lived key, so it is necessary to generate it often (ideally for every message). Is this (basic) understanding correct? – frarugi87 Jan 14 at 14:12
  • @frarugi87 Not quite. ECDH is one step of ECIES, not another name for ECIES. ECDHE is not a well-defined term, but the most useful way to define it would be for the following protocol: 1) generate a fresh key pair; 2) perform ECDH with this key and the peer's public key; 3) erase the private key. – Gilles Jan 16 at 21:29
  • perfect, thank you for your explanation, it was very clear :) – frarugi87 Jan 17 at 7:53

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.