Key strength checking for ECDSA keys

[jsha]

In https://github.com/letsencrypt/boulder/pull/156 I only implemented RSA strength checking so far.

[geforceGTX480]

jsha, is this 256-bit ECDSA keys ? :)

[jsha]

Yes, we'll probably require a minimum of 256 bits for ECDSA keys. I believe there may be other strength checking requirements, similar to RSA keys. This ticket is to research what checks we need, then implement them. Interested?

[rolandshoemaker]

After skimming through a few papers I've put together a few notes on possible checks, I'll leave them here with links to the papers for anyone interested. I got somewhat (very) confused at some points with various different namings of the public parameters and some of the finite field maths so there is no guarantee any of this is correct... (hence links to papers for confirmation/clarification)

possible ECDSA curve param checks
---------------------------------

* PublicKey.Curve.Params().BitSize >= 256
* PublicKey.Curve.Params().BitSize <= ???

* PublicKey.Curve.Params().N > 2^160 [1][3][5]
* PublicKey.Curve.Params().N > (4 * sqrt(PublicKey.Curve.Params().P)) [3][5] (?)
* PublicKey.Curve.Params().N is prime [3]

* PublicKey.Curve.Params().P > 3 && PublicKey.Curve.Params().P is prime && (PublicKey.Curve.Params().P % 2) == 1 
    OR
  !(PublicKey.Curve.Params().P is not prime && (PublicKey.Curve.Params().P % 2 == 0)) [2][3][4][5] (?)
* (PublicKey.Curve.Params().P^PublicKey.Curve.Params().B - 1) % PublicKey.Curve.Params().N != 0 [4] (?)

1: http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa.pdf
2: http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa-cert.pdf
3: http://grouper.ieee.org/groups/1363/WorkingGroup/presentations/ecdsa_pkc03.pdf
4: https://en.wikipedia.org/wiki/Elliptic_curve_cryptography (... don't judge me)
5: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.3190&rep=rep1&type=pdf

[geforceGTX480]

Yes, this fascinating. I will do the research on what checks we need and get back to you.

Thank you,

Thulani

Sent from my trusted minion, AES-256 Nexus Phone On Jun 17, 2015 12:55 PM, "Jacob Hoffman-Andrews" notifications@github.com wrote:

Yes, we'll probably require a minimum of 256 bits for ECDSA keys. I believe there may be other strength checking requirements, similar to RSA keys. This ticket is to research what checks we need, then implement them. Interested?

— Reply to this email directly or view it on GitHub https://github.com/letsencrypt/boulder/issues/158#issuecomment-112892187 .

[SkateScout]

Hi, is there no one here that can do the checks in GO ?

https://github.com/letsencrypt/boulder/blob/master/core/good_key.go GoodKeyECDSA

key.X big.Int := xQ key.Y big.Int := yQ key.Params().P big.Int key.Params().N big.Int key.Params().B big.Int key.Params().Gx big.Int key.Params().Gy big.Int key.Params().BitSize int key.Params().Name string (P224, P256, P383, P521)

http://csrc.nist.gov/groups/ST/toolkit/documents/SP800-56Arev1_3-8-07.pdf https://www.nsa.gov/ia/_files/ecdsa.pdf A.3

5.6.2.5 ECC Full Public Key Validation Routine ECC full public key validation refers to the process of checking all the arithmetic properties of a candidate ECC public key to ensure that it has the unique correct representation in the correct
(additive) subgroup (and therefore is also in the correct EC group) specified by the associated
ECC domain parameters. ECC full public key validation does not require knowledge of the
associated private key and so may be done at any time by anyone. This method may be used for a static ECC public key,
or an ephemeral ECC public key, when assurance of the validity of the key is obtained by method 1 or method 2 of Sections 5.6.2.1, 5.6.2.2, and 5.6.2.3.

Input:

1. (q, FR, a, b {, SEED } , G, n, h): A valid set of ECC domain parameters, and
2. Q =( xQ , yQ ): A candidate ECC public key.

Process:

1. Verify that Q is not the point at infinity O. This can be done by inspection if the point is entered in the standard affine representation. (Partial check of the public key for an invalid range in the EC group.) O = A + -A = A + -1 * A = A + A if (A + A == A) then A is the point at infinity., this mean unusable for secure signatures.

TODO translate to GO : IF( ((-1 * [key.X , key.Y]) + [key.X , key.Y])==[key.X , key.Y] THEN [key.X , key.Y] is the infinite point and there is an error

1. Verify that xQ and yQ are integers in the interval [0, p -1] in the case that q is an odd prime p , or that xQ and yQ are bit strings of length m bits in the case that q = 2^m . (Ensures that each coordinate of the public key has the unique correct representation of an element in the underlying field.) TODO: if(p==2^m) xQ und yQ must be bitstring of len m else xQ und yQ must between 0 and p-1
2. If q is an odd prime p , verify that yQ^2 = xQ^3 + a * xQ + b (mod p).
   If q = 2^m , verify that yQ^2 + xQyQ = xQ^3 + a \ xQ^2 + b in the finite field of size 2^m . (Ensures that the public key is on the correct elliptic curve.)