+++++++++++++++++++++++++++++++++++++++++++++++++ Q: Why should ECDSA for DNSSEC be implemented? A: The major benefit that comes with ECDSA (in comparison to RSA signatures) is the much smaller size of keys and signatures for same or better cryptographical strenght. This largely impacts DNS zone sizes and response sizes, and hence network and server load and potential protocol complications. See the Introduction of [RFC6605] for more information. NIST is a driving force for ECC that puts pressure on the market far beyond its proper bailiwick, U.S. government related use. NIST has only approved RSA signatures until 2015 and calls for the support of ECDSA "(or similar)" by September 2015 for all DNS software components to be considered for U.S. federal use. In a recent message to the DNSOP list, I have provided related quotes from [SP800-81] -- see item (A.4) in the message archived at http://www.IETF.ORG/mail-archive/web/dnsop/current/msg09551.html In the excerpts from NIST SP 800-81r1, page 9-4: "[...] The migration path for USG DNSSEC operation will be to ECDSA (or similar) from RSA/SHA-1 and RSA/SHA-256 before Septhember 30th, 2015. ... and from the same document, on page 9-6: "The use of RSA in DNSSEC is approved until the year 2015. By this time, it is expected that Elliptic Curve Cryptigraphy will be specified in the DNSSEC. USG DNSSEC administrations should plan to migrate to the use of ECDSA (or similar) when it becomes available in DNSSEC components." ... one can see that there are strong market forces at work. The commercial pressure to qualify for USG (U.S. Government) use of networking components and software will likely lead to widespread support soon. There's nothing like "(or similar)" in view currently as an alternative. +++++++++++++++++++++++++++++++++++++++++++++++++ Q: Why are there two algorithm numbers, with fixed key size each, assigned for ECDSA use with DNSSEC? A: For digital signatures RSA and DSA, the underlying arithmetics are based on modulo computations relative to very large prime numbers that are chosen at random during private key generation. Therefore, implementations must ba able to handle general mod-p arithmetics and cannot be optimized for special cases. Restrictions on key sizes are imposed by using balanced hash algorithms before signing and the related standards covering these combinations. Therefore, the 'classical' DNSSEC algorithm numbers assigned cover a span of key sizes, and the key size must be specified with the keys. Unlike this, the arithmetics employed on elliptical curves make sophisticated use of all field operations (including division) and therefore can afford using a prime number base of only modest size. The prime is only one of the EC domain parameters to be chosen carefully, and the choice of these is better not left to the key generation procedure. On the other hand, if the parameters are predetermined, one can benefit from code optimization specifically crafted for the prime number characteristic of these fields. The recommended EC domain parameter sets are specifically vetted by the cryptographic community to make sure that known potential attack vectors on the problem to invert the presumed one-way function, exponentiation in a finite group, on which ECC is based (discrete logarithm problem over the respective groups). For instance, for the P-256 EC group, the underlying field has characteristic p = 2^(256)-2^(224)+2^(192)+2^(96)-1 (cf. RFC 5114 or SECG 2); so one can easily see that reduction mod p (needed to implement mod-p multiplication) can be implemented in uint32 arithmetics by using only a few word shift operations and several addition/subtraction operations (basic application of the distributive law). Therefore, efficient implementations of ECC are necessarily specific per EC group. RFC 6605 has standardized a single, commonly favored EC group for each of the two cryptographic "strength" levels 128 and 192, and matched these EC groups with the SHA-2 family hash algorithm of corresponding strength (which is roughly half the width of the hash output, due to the birthday paradoxon). So we have two new DNSSEC algorithms with fixed key (and signature) size in RFC 6605 and in the IANA registry: Algo Number 13 Description ECDSA on Curve P-256 with SHA-256 Mnemonic ECDSAP256SHA256 and Algo Number 14 Description ECDSA on Curve P-384 with SHA-384 Mnemonic ECDSAP384SHA384 Note that the cryptographic community believes that the former corresponds to crypto-strenght 128 and is roughly equivalent to RSA/DSA with 3kbit keys and SHA-256, whereas the latter has crypto-strenght 192, which is roughly equivalent to RSA/DSA with 7.5kbit keys and SHA-384. +++++++++++++++++++++++++++++++++++++++++++++++++ Q: For RSA/DSA, the code has to deal with variable-size numbers and padding. For ECDSA that seems to be different. Are those integers *always* 32 or 48 octets? I.e., there is never a need for padding? A: Yes, and Yes. Where RSA needs computations on really huge numbers, which deserve some careful memory management, the computations needed to perform practicable Elliptic Curve crypto stuff are all modulo a prime number of modest size -- these primes are just below 2^256 or 2^384, respectively, for the two EC groups in current focus, dubbed P-256 and P-384 (definitions of the group parameters including these prime numbers are reproduced e.g. in RFC 5114, Sect. 2.6/2.7). This bit size -- corresponding to 32/48 octets -- is much more managable, so the code can be written to operate on more or less statically defined "super-long" integer variables of a _fixed_ size in the same way as classical uint32 or uint64 data types actually operate modulo 2^32 or 2^64. You traditionally never bother about leading (most significant) zero bits when performing computations with uint32 / uint64 data, and so you don't for the arithmetics over finite fields of modest prime order that represent the coordinate spaces for the Elliptic Curves of interest. For highly optimised code, the best optimisations are quite specific to the underlying finite field of the EC group; that's why efficient implementations of the arithmetics better be per-group, and therefore each EC group is treated as a specific algorithm for DNSSEC purposes. +++++++++++++++++++++++++++++++++++++++++++++++++ Q: Why are private keys and public keys so different in ECC, and why do we need only so much shorter keys and signatures in comparison to RSA and DSA? A: RSA and DSA mostly operate with "simple" (yet very large) integer numbers. With DSA or classical Diffie-Hellman, the private key is the exponent x for the public key y=g^x, with a pre-defined base g, which all are integers (modulo some base). For RSA, things are similar, but a bit more complicated. For ECC, the groups are usually written additively, so what is exponentiation above looks like multiplication with an integer; but the integer multiplication in ECC means repeated addition of the same group element, but group element are points on an Elliptic Curve, which are mostly represented in affine coordinates -- like a point (x,y) in common, planary geometry --; however, here both coordinates are elements of a finite field, not real numbers. For our purposes, the field is of order p, which is a prime number of moderate size. The generator G of the group thus is G = (G_x,G_y), with some mathematical restrictions on the coordinate values (imposed by the curve equation), and a private key d (an integer mod p) corresponds to the public key D = G+G+...+G (d terms), written as D = d*G (or shorter: dG), again is a point on the elliptic curve, D = (x,y). Since the size of p is moderate, a fixed-size encoding of d as well as x and y is used; in DNSKEY RRs, the EC public key is stored as the concatenation x|y. These details only matter for the key generation, signing, and signature verification; administratively, in the DNS keys for the defined EC groups are binary blobs of 2*32=64 or 2*48=96 octet length, respectively. ECDSA signatures (just like DSA signatures) also are pairs of integers, denoted as (r,s), but conceptionally they are independent field elements, not EC group points. For uniformity, the signatures are encoded as the concatenation of two fixed-size integers, in the same way as the public keys; again, for the DNS database and the DNS wire protocol, the internal structure doesn't matter, RFC 6605 ECDSA signatures are fixed-size 64 / 96 octet binary blobs. Regarding size and strenght, perhaps over-simplifying the argument: Because EC points are _pairs_ of such mod-p numbers and the arithmetics defined on these pairs looks rather complicated (but nevertheless can be implemented very easily), you can restrict yourself to much shorter numbers than needed for RSA (or DSA, for the matter) -- which operate on single numbers with scalar modulo arithmetics only -- for comparable "strength". In all these cases, "strength" means the complexity of solving the discrete logarithm problem over the respective groups. For ECC, the fixed primes and the other group parameters can be (and actually are) chosen to yield groups that are not susceptible to the known potential attack vectors on the discrete logarithm problem, and the vetting process was very extensive for the commonly recommended Ellptic Curves; contrary to that, since the primes vary per key for RSA/DSA, you need much headroom for safety. +++++++++++++++++++++++++++++++++++++++++++++++++ Q: In my code I observe the ecdsa generates a different signature every time you resign (with the exact same input). Why is this? Is there some random padding involved? Yes, indeed, ECDSA signatures are "randomized". (Note that this is a property shared between ECDSA and DSA.) But don't use the term "padding"; in crypto parlance, it's better described as using a "salt" -- a random number generated ad hoc and not reused later. See Step 1 in Section 5.4.2 of RFC 6090 (which uses the academical term "KT-I Signature", not the 'branding' term "ECDSA", but it later notes that ECDSA signatures are actually equivalent to these. For convenience, I quote the relevant sections from RFC 6090 below; see the earlier sections of RFC 6090 for the notation; for DNSSEC usage as per RFC 6605, h() is SHA-256 / SHA-384 applied to the to-be-signed part of the RRs, as specified by the DNSSEC RFCs. You might prefer to start reading with s5.4.2 and refer back to the earlier parts as needed. -------- start quotes from RFC 6090 -------- 5.3. KT-IV Signatures [...] The algorithm uses an elliptic curve group, as described in Section 3.3, with prime field order p and curve equation parameters a and b. We denote the generator as alpha, and the order of the generator as q. We follow [FIPS186] in checking for exceptional cases. 5.3.1. Keypair Generation The private key z is an integer between 1 and q-1, inclusive, generated uniformly at random. (See Appendix B regarding random integers.) The public key is the group element Y = alpha^z. Each public key is associated with a particular parameter set as per Section 3.3. [...] 5.4. KT-I Signatures [...] 5.4.1. Keypair Generation Keypairs and keypair generation are exactly as in Section 5.3.1. 5.4.2. Signature Creation To compute a KT-I signature for a message m using the private key z: 1. Choose an integer k uniformly at random from the set of all integers between 1 and q-1, inclusive. (See Appendix B regarding random integers.) 2. Calculate R = (r_x, r_y) = alpha^k. 3. Calculate s1 = r_x mod q. 4. Calculate s2 = (h(m) + z*s1)/k mod q. 5. As an option, one MAY check if s1 = 0 or s2 = 0. If either s1 = 0 or s2 = 0, a new value of k SHOULD be generated and the signature SHOULD be recalculated. (It is extremely unlikely that s1 = 0 or s2 = 0 if signatures are generated properly.) The signature is the ordered pair (s1, s2). Both signature components are non-negative integers. -------- end quotes from RFC 6090 -------- BTW: Methods to "split" private keys, e.g. in support of partial escrow for desaster recovery, also use such randomly selected data, for instance, see the array A in the [TSS] share generation algorithm. (Reportedly, a similar procedure is applied to the Root Zone KSK.) +++++++++++++++++++++++++++++++++++++++++++++++++ Q: What reading should an implementer of ECDSA for DNSSEC consider? A: Below is an annotated list of selected readings on Elliptic Curve Cryptography (ECC) that might be of particular interest for implementers of ECDSA for DNSSEC according to RFC 6605. The references below are to readily online available resources only, with the exception of the two hardcover books near the end of the list. First of all, there is RFC 6605: * [RFC6605] Hoffman, P. and Wijngaards, W., "Elliptic Curve Digital Signature Algorithm (DSA) for DNSSEC", RFC 6605, April 2012. - general information: http://www.RFC-Editor.org/info/rfc6605 - the RFC text: http://www.RFC-Editor.org/rfc/rfc6605.txt * follow the references, some of which are detailed below! For concise background information on Elliptical Curve Cryptography in general, the underlying arithmetics, and citations to original publications, in IETF style, I really, really highly recommend studying RFC 6090: * [RFC6090] McGrew, D., Igoe, K., and M. Salter, "Fundamental Elliptic Curve Cryptography Algorithms", RFC 6090, February 2011. - general information: http://www.RFC-Editor.org/info/rfc6099 - the RFC text: http://www.RFC-Editor.org/rfc/rfc6099.txt * relevant sections: 1-3, 5 excluding 5.3.2 and 5.3.3, 6, 7 excluding 7.1, 8 excluding 8.1, 9, 10 - Errata: http://www.RFC-Editor.ORG/errata_search.php?rfc=6090 * please read! In a nutshell (but IANAL [I am not a lawyer] !), this document shows that all we need for this kind of ECC (based on finite fields of prime order) and its implementation for DNSSEC can be based on scholarly publications that partially date back decades and certainly the much-feared patent applications that try to claim to cover the matter, and on highschool/low-level college mathematics (cf. [AoCP2] below). o Standards for Efficient Cryptography Group (SECG) Many details on practical ECC are specified in the SECG documents (initial versions published in 2000). In particular, the low-level conventions (in particular on byte ordering and conversion between data types) adopted by ANSI, IEEE, NIST, and other national standards are described therein. * These are published by an Industry Consortium, SECG: http://www.secg.org/ - Documents http://www.secg.org/index.php?action=secg,docs_home * Standards for Elliptical Curve Cryptography: - SEC 1: Elliptic Curve Cryptography, Version 2.0; SECG / Certicom Research, January 2010. http://www.secg.org/download/aid-780/sec1-v2.pdf * relevant sections: 1, 2., 2.1 excluding 2.1.2 and 2.2.2, 2.3, 3, 3.1 excluding 3.1.2, 3.2, 3.5, 3.10, 3.11, 4, 4.1, A, B, B.1, B.2 (only subparts corresponding to above parts of s3), B.3, B.6 - SEC 2: Recommended Elliptic Curve Domain Parameters, Version 2.0; SECG / Certicom Research, May 2009. http://www.secg.org/download/aid-784/sec2-v2.pdf * relevant sections: 1, 2.1, 2.4.2, 2.5.1 o NIST Of course, NIST is a major driving force in Standardization. Here are the most important resources: * NIST Computer Security Division | - Computer Security Resource Center | Digital Signatures http://csrc.nist.gov/groups/ST/toolkit/digital_signatures.html * The ECDSA Digital Signature Algorithm has been included in the current (3rd) edition of the DSS: - FIPS 186-3, Digital Signature Standard (DSS) http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf - Recommended Curves White Paper http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf * NIST's DNSSEC recommendations: - NIST Special Publication (SP) 800-81 Rev.1, "Secure Domain Name System (DNS) Deployment Guide", April 2010 http://csrc.nist.gov/publications/nistpubs/800-81r1/sp-800-81r1.pdf o Computer Arithmetics and Random Numbers Many concepts for computer arithmetics, including the kind needed for ECC, and possible optimizations in their implementation, have been investigated, shown, and proven in Donald Knuth's 2nd Volume of "The Art of Computer Programming", first published in 1968. My copy is: * [AoCP2] Donald E. Knuth, The Art of Computer Programming, Volume 2, Seminumerical Algorithms, Addison-Wesley, 2nd ed., 1980. ISBN-10: 0-201-0382206 o The ECC "Bible" - [HEC] Henry Cohen, Gerhard Frey (editors), Roberto Avanzi, Christoph Doche, Tanja Lange, Kim Nguyen, and Frederik Verkauteren; "Handbook of Elliptic and Hyperelliptic Curve Crytography"; Chapman & Hall / CRC, 2006; ISBN-10: URN:ISBN:1-58488-518-1 , ISBN-13: URN:ISBN:978-1-58488-518-4 NOTE: Here you'll find all the math and background, including proofs for optimized algorithms (sound mathematical background needed), and a *huge* bibliography (may be interesting for defense against patent claims) Finally, supplemental to the 'BTW' Note above: o Threshold Secret Sharing (TSS) - [TSS] Internet-draft (expired work in progress) http://tools.ietf.org/html/draft-mcgrew-tss-03 (this section shows use of random numbers in share generation: http://tools.ietf.org/html/draft-mcgrew-tss-03#section-3.2 ) +++++++++++++++++++++++++++++++++++++++++++++++++