11
$\begingroup$

A FAQ for an open source project makes the claim:

Indeed, an elliptic curve key of length n provides $n/2$ bits of security.

I have two questions:

  1. What is the practical difference between "bits of entropy" and "bits of security"?
  2. How does one estimate the number of bits of security (or entropy) for an elliptic curve private key of length $n$?
$\endgroup$
  • $\begingroup$ that FAQ is confusing, I do not think the statement is technically accurate $\endgroup$ – Richie Frame Jul 8 '15 at 0:46
  • $\begingroup$ The FAQ IS confusing but the statement is accurate. $\endgroup$ – Gerald Davis Jul 8 '15 at 3:41
  • $\begingroup$ @GeraldDavis not the elliptic curve part, rather the seed entropy part that was not quoted here $\endgroup$ – Richie Frame Jul 8 '15 at 4:39
7
$\begingroup$

Bits of entropy

The assumption for all cryptographic operations is that a random key of n bits has n bits of entropy. If it doesn't (due to PRNG defect or implementation error) then the key will be weaker than expected but the underlying assumption of all cryptographic primitives is that an n bit key has n bits of entropy. This is the same for all types of cryptographic systems. It is also why in cases where the key is derived from a password while it may be impossible to brute force the key it is possible to brute force the significantly weaker password.

Bit strength

An ECC key has a bit strength equal to half the key length. To understand why we need to take a step back and look at what makes ECC strong. By strong we mean that it is computationally difficult to derive the private key from the public key. Why is that difficult? Well the short version is that to go from public key to private key would require solving a discrete logarithm and no efficient solution is known. This is a mathematical assumption on which ECC is based.

So why is the bit strength equal to half the key length? It is because all of the fastest solutions for solving a discrete logarithm problem are on the order of $O(2^{n/2})$. So for a 256 bit key we are talking about $2^{128}$ operations which is the same as an exhaustive search on a 128 bit symmetric key thus it is 128 bit strength.

Key length does not equal bit strength

The ratio between key length and bit strength will vary by algorithm. For unbroken symmetric algorithms there is no solution short of an exhaustive search of possible keys to find the proper key thus a 128 bit AES key has 128 bit strength. However for asymmetric encryption there are faster solutions and as a result it takes a larger key to achieve a similar level of security but that ratio will depend on the algorithm used and the fastest known solution.

$$\begin{array} {r r r} AES\ 128\ bit\ key & = 2^{128}\ operations & = 128\ bit\ security \\ ECC\ 256\ bit\ key & = 2^{128}\ operations & = 128\ bit\ security \\ RSA\ 2,048\ bit\ key & = 2^{128}\ operations & = 128\ bit\ security \\ \end{array}$$

$$\begin{array} {r r r} AES\ 256\ bit\ key & = 2^{256}\ operations & = 256\ bit\ security \\ ECC\ 512\ bit\ key & = 2^{256}\ operations & = 256\ bit\ security \\ RSA\ 15,360\ bit\ key & = 2^{256}\ operations & = 256\ bit\ security \\ \end{array}$$

Now if tomorrow someone found a faster solution to solve the discrete logarithm problem, let say $O(2^{n/4})$ then a 512 bit ECC key would no longer be 256 bit security it would be 128 bit security. I think that is unlikely but I use it as an example to illustrate why keys of different algorithms have different lengths for the same level of security.

$\endgroup$
  • $\begingroup$ It isn't true in general that an $n$-bit key even can have $n$ bits of entropy. Counterexample: RSA. $\endgroup$ – otus Jul 8 '15 at 4:10
  • 1
    $\begingroup$ @otus An $n$-bit key can have AT MOST $n$ bits of entropy. $\endgroup$ – SAI Peregrinus Jul 8 '15 at 5:36
  • 3
    $\begingroup$ Actually, given the public key, the secret key has ZERO bits of entropy. Likewise, given a few ciphertexts a symmetric key has ZERO entropy. They do have (assumed) COMPUTATIONAL ENTROPY. $\endgroup$ – Yehuda Lindell Jul 8 '15 at 6:54
  • $\begingroup$ Do the ciphertexts necessarily peg the symmetric key at zero entropy? I'd imagine that you could pigeonhole it to get two separate keys to generate a valid MAC and decode ciphertext into two different plaintexts. $\endgroup$ – Nick T Apr 22 at 19:55

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.