INTERNET-DRAFT ECC Keys in the DNS Expires: February 2004 August 2003 Elliptic Curve KEYs in the DNS -------- ----- ---- -- --- --- <draft-ietf-dnsext-ecc-key-04.txt> Richard C. Schroeppel Donald Eastlake 3rd Status of This Document This draft is intended to be become a Proposed Standard RFC. Distribution of this document is unlimited. Comments should be sent to the DNS mailing list <namedroppers@internic.com> or to the authors. This document is an Internet Draft and is in full conformance with all provisions of Section 10 of RFC 2026. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract A standard method for storing elliptic curve cryptographic keys in the Domain Name System is described. R. Schroeppel, et al [Page 1]

INTERNET-DRAFT ECC Keys in the DNS Acknowledgement The assistance of Hilarie K. Orman in the production of this document is greatfully acknowledged. Table of Contents Status of This Document....................................1 Abstract...................................................1 Acknowledgement............................................2 Table of Contents..........................................2 1. Introduction............................................3 2. Elliptic Curve Data in Resource Records.................3 3. The Elliptic Curve Equation.............................9 4. How do I Compute Q, G, and Y?..........................10 5. Performance Considerations.............................11 6. Security Considerations................................11 7. IANA Considerations....................................11 Informational References..................................12 Normative Refrences.......................................12 Authors' Addresses........................................13 Expiration and File Name..................................13 R. Schroeppel, et al [Page 2]

INTERNET-DRAFT ECC Keys in the DNS 1. Introduction The Domain Name System (DNS) is the global hierarchical replicated distributed database system for Internet addressing, mail proxy, and other information. The DNS has been extended to include digital signatures and cryptographic keys as described in [RFC 2535]. This document describes how to store elliptic curve cryptographic (ECC) keys in the DNS so they can be used for a variety of security purposes. A DNS elliptic curve SIG resource record is not defined. Familiarity with ECC cryptography is assumed [Menezes]. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC 2119]. 2. Elliptic Curve Data in Resource Records Elliptic curve public keys are stored in the DNS within the RDATA portions of RRs with the structure shown below. The period of key validity may not be in the RR with the key but could be indicated by RR(s) with signatures that authenticates the RR(s) containing the key. The research world continues to work on the issue of which is the best elliptic curve system, which finite field to use, and how to best represent elements in the field. So, we have defined representations for every type of finite field, and every type of elliptic curve. The reader should be aware that there is a unique finite field with a particular number of elements, but many possible representations of that field and its elements. If two different representations of a field are given, they are interconvertible with a tedious but practical precomputation, followed by a fast computation for each field element to be converted. It is perfectly reasonable for an algorithm to work internally with one field representation, and convert to and from a different external representation. R. Schroeppel, et al [Page 3]

INTERNET-DRAFT ECC Keys in the DNS 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |S M -FMT- A B Z| +-+-+-+-+-+-+-+-+ | LP | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | P (length determined from LP) .../ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LF | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | F (length determined from LF) .../ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DEG | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DEGH | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DEGI | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DEGJ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | TRDV | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |S| LH | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | H (length determined from LH) .../ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |S| LK | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | K (length determined from LK) .../ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LQ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Q (length determined from LQ) .../ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LA | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | A (length determined from LA) .../ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ALTA | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LB | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | B (length determined from LB) .../ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | C (length determined from LC) .../ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LG | R. Schroeppel, et al [Page 4]

INTERNET-DRAFT ECC Keys in the DNS +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | G (length determined from LG) .../ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LY | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Y (length determined from LY) .../ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ SMFMTABZ is a flags octet as follows: S = 1 indicates that the remaining 7 bits of the octet selects one of 128 predefined choices of finite field, element representation, elliptic curve, and signature parameters. MFMTABZ are omitted, as are all parameters from LP through G. LY and Y are retained. If S = 0, the remaining parameters are as in the picture and described below. M determines the type of field underlying the elliptic curve. M = 0 if the field is a GF[2^N] field; M = 1 if the field is a (mod P) or GF[P^D] field with P>2. FMT is a three bit field describing the format of the field representation. FMT = 0 for a (mod P) field. > 0 for an extension field, either GF[2^D] or GF[P^D]. The degree D of the extension, and the field polynomial must be specified. The field polynomial is always monic (leading coefficient 1.) FMT = 1 The field polynomial is given explicitly; D is implied. If FMT >=2, the degree D is given explicitly. = 2 The field polynomial is implicit. = 3 The field polynomial is a binomial. P>2. = 4 The field polynomial is a trinomial. = 5 The field polynomial is the quotient of a trinomial by a short polynomial. P=2. = 6 The field polynomial is a pentanomial. P=2. Flags A and B apply to the elliptic curve parameters. R. Schroeppel, et al [Page 5]

INTERNET-DRAFT ECC Keys in the DNS A = 1 When P>=5, the curve parameter A is negated. If P=2, then A=1 indicates that the A parameter is special. See the ALTA parameter below, following A. The combination A=1, P=3 is forbidden. B = 1 When P>=5, the curve parameter B is negated. If P=2 or 3, then B=1 indicates an alternate elliptic curve equation is used. When P=2 and B=1, an additional curve parameter C is present. The Z bit SHOULD be set to zero on creation of an RR and MUST be ignored when processing an RR (when S=0). Most of the remaining parameters are present in some formats and absent in others. The presence or absence of a parameter is determined entirely by the flags. When a parameter occurs, it is in the order defined by the picture. Of the remaining parameters, PFHKQABCGY are variable length. When present, each is preceded by a one-octet length field as shown in the diagram above. The length field does not include itself. The length field may have values from 0 through 110. The parameter length in octets is determined by a conditional formula: If LL<=64, the parameter length is LL. If LL>64, the parameter length is 16 times (LL-60). In some cases, a parameter value of 0 is sensible, and MAY be represented by an LL value of 0, with the data field omitted. A length value of 0 represents a parameter value of 0, not an absent parameter. (The data portion occupies 0 space.) There is no requirement that a parameter be represented in the minimum number of octets; high-order 0 octets are allowed at the front end. Parameters are always right adjusted, in a field of length defined by LL. The octet-order is always most-significant first, least-significant last. The parameters H and K may have an optional sign bit stored in the unused high-order bit of their length fields. LP defines the length of the prime P. P must be an odd prime. The parameters LP,P are present if and only if the flag M=1. If M=0, the prime is 2. LF,F define an explicit field polynomial. This parameter pair is present only when FMT = 1. The length of a polynomial coefficient is ceiling(log2 P) bits. Coefficients are in the numerical range [0,P-1]. The coefficients are packed into fixed-width fields, from higher order to lower order. All coefficients must be present, including any 0s and also the leading coefficient (which is required to be 1). The coefficients are right justified into the octet string of length specified by LF, with the low-order "constant" coefficient at the right end. As a concession to storage efficiency, the higher order bits of the leading coefficient may be elided, discarding high- order 0 octets and reducing LF. The degree is calculated by R. Schroeppel, et al [Page 6]

INTERNET-DRAFT ECC Keys in the DNS determining the bit position of the left most 1-bit in the F data (counting the right most bit as position 0), and dividing by ceiling(log2 P). The division must be exact, with no remainder. In this format, all of the other degree and field parameters are omitted. The next parameters will be LQ,Q. If FMT>=2, the degree of the field extension is specified explicitly, usually along with other parameters to define the field polynomial. DEG is a two octet field that defines the degree of the field extension. The finite field will have P^DEG elements. DEG is present when FMT>=2. When FMT=2, the field polynomial is specified implicitly. No other parameters are required to define the field; the next parameters present will be the LQ,Q pair. The implicit field poynomial is the lexicographically smallest irreducible (mod P) polynomial of the correct degree. The ordering of polynomials is by highest-degree coefficients first -- the leading coefficient 1 is most important, and the constant term is least important. Coefficients are ordered by sign-magnitude: 0 < 1 < -1 < 2 < -2 < ... The first polynomial of degree D is X^D (which is not irreducible). The next is X^D+1, which is sometimes irreducible, followed by X^D-1, which isn't. Assuming odd P, this series continues to X^D - (P-1)/2, and then goes to X^D + X, X^D + X + 1, X^D + X - 1, etc. When FMT=3, the field polynomial is a binomial, X^DEG + K. P must be odd. The polynomial is determined by the degree and the low order term K. Of all the field parameters, only the LK,K parameters are present. The high-order bit of the LK octet stores on optional sign for K; if the sign bit is present, the field polynomial is X^DEG - K. When FMT=4, the field polynomial is a trinomial, X^DEG + H*X^DEGH + K. When P=2, the H and K parameters are implicitly 1, and are omitted from the representation. Only DEG and DEGH are present; the next parameters are LQ,Q. When P>2, then LH,H and LK,K are specified. Either or both of LH, LK may contain a sign bit for its parameter. When FMT=5, then P=2 (only). The field polynomial is the exact quotient of a trinomial divided by a small polynomial, the trinomial divisor. The small polynomial is right-adjusted in the two octet field TRDV. DEG specifies the degree of the field. The degree of TRDV is calculated from the position of the high-order 1 bit. The trinomial to be divided is X^(DEG+degree(TRDV)) + X^DEGH + 1. If DEGH is 0, the middle term is omitted from the trinomial. The quotient must be exact, with no remainder. When FMT=6, then P=2 (only). The field polynomial is a pentanomial, with the degrees of the middle terms given by the three 2-octet R. Schroeppel, et al [Page 7]

INTERNET-DRAFT ECC Keys in the DNS values DEGH, DEGI, DEGJ. The polynomial is X^DEG + X^DEGH + X^DEGI + X^DEGJ + 1. The values must satisfy the inequality DEG > DEGH > DEGI > DEGJ > 0. DEGH, DEGI, DEGJ are two-octet fields that define the degree of a term in a field polynomial. DEGH is present when FMT = 4, 5, or 6. DEGI and DEGJ are present only when FMT = 6. TRDV is a two-octet right-adjusted binary polynomial of degree < 16. It is present only for FMT=5. LH and H define the H parameter, present only when FMT=4 and P is odd. The high bit of LH is an optional sign bit for H. LK and K define the K parameter, present when FMT = 3 or 4, and P is odd. The high bit of LK is an optional sign bit for K. The remaining parameters are concerned with the elliptic curve and the signature algorithm. LQ defines the length of the prime Q. Q is a prime > 2^159. In all 5 of the parameter pairs LA+A,LB+B,LC+C,LG+G,LY+Y, the data member of the pair is an element from the finite field defined earlier. The length field defines a long octet string. Field elements are represented as (mod P) polynomials of degree < DEG, with DEG or fewer coefficients. The coefficients are stored from left to right, higher degree to lower, with the constant term last. The coefficients are represented as integers in the range [0,P-1]. Each coefficient is allocated an area of ceiling(log2 P) bits. The field representation is right-justified; the "constant term" of the field element ends at the right most bit. The coefficients are fitted adjacently without regard for octet boundaries. (Example: if P=5, three bits are used for each coefficient. If the field is GF[5^75], then 225 bits are required for the coefficients, and as many as 29 octets may be needed in the data area. Fewer octets may be used if some high-order coefficients are 0.) If a flag requires a field element to be negated, each non-zero coefficient K is replaced with P-K. To save space, 0 bits may be removed from the left end of the element representation, and the length field reduced appropriately. This would normally only happen with A,B,C, because the designer chose curve parameters with some high-order 0 coefficients or bits. If the finite field is simply (mod P), then the field elements are simply numbers (mod P), in the usual right-justified notation. If the finite field is GF[2^D], the field elements are the usual right- justified polynomial basis representation. R. Schroeppel, et al [Page 8]

INTERNET-DRAFT ECC Keys in the DNS LA,A is the first parameter of the elliptic curve equation. When P>=5, the flag A = 1 indicates A should be negated (mod P). When P=2 (indicated by the flag M=0), the flag A = 1 indicates that the parameter pair LA,A is replaced by the two octet parameter ALTA. In this case, the parameter A in the curve equation is x^ALTA, where x is the field generator. Parameter A often has the value 0, which may be indicated by LA=0 (with no A data field), and sometimes A is 1, which may be represented with LA=1 and a data field of 1, or by setting the A flag and using an ALTA value of 0. LB,B is the second parameter of the elliptic curve equation. When P>=5, the flag B = 1 indicates B should be negated (mod P). When P=2 or 3, the flag B selects an alternate curve equation. LC,C is the third parameter of the elliptic curve equation, present only when P=2 (indicated by flag M=0) and flag B=1. LG,G defines a point on the curve, of order Q. The W-coordinate of the curve point is given explicitly; the Z-coordinate is implicit. LY,Y is the user's public signing key, another curve point of order Q. The W-coordinate is given explicitly; the Z- coordinate is implicit. The LY,Y parameter pair is always present. 3. The Elliptic Curve Equation (The coordinates of an elliptic curve point are named W,Z instead of the more usual X,Y to avoid confusion with the Y parameter of the signing key.) The elliptic curve equation is determined by the flag octet, together with information about the prime P. The primes 2 and 3 are special; all other primes are treated identically. If M=1, the (mod P) or GF[P^D] case, the curve equation is Z^2 = W^3 + A*W + B. Z,W,A,B are all numbers (mod P) or elements of GF[P^D]. If A and/or B is negative (i.e., in the range from P/2 to P), and P>=5, space may be saved by putting the sign bit(s) in the A and B bits of the flags octet, and the magnitude(s) in the parameter fields. If M=1 and P=3, the B flag has a different meaning: it specifies an alternate curve equation, Z^2 = W^3 + A*W^2 + B. The middle term of the right-hand-side is different. When P=3, this equation is more R. Schroeppel, et al [Page 9]

INTERNET-DRAFT ECC Keys in the DNS commonly used. If M=0, the GF[2^N] case, the curve equation is Z^2 + W*Z = W^3 + A*W^2 + B. Z,W,A,B are all elements of the field GF[2^N]. The A parameter can often be 0 or 1, or be chosen as a single-1-bit value. The flag B is used to select an alternate curve equation, Z^2 + C*Z = W^3 + A*W + B. This is the only time that the C parameter is used. 4. How do I Compute Q, G, and Y? The number of points on the curve is the number of solutions to the curve equation, + 1 (for the "point at infinity"). The prime Q must divide the number of points. Usually the curve is chosen first, then the number of points is determined with Schoof's algorithm. This number is factored, and if it has a large prime divisor, that number is taken as Q. G must be a point of order Q on the curve, satisfying the equation Q * G = the point at infinity (on the elliptic curve) G may be chosen by selecting a random [RFC 1750] curve point, and multiplying it by (number-of-points-on-curve/Q). G must not itself be the "point at infinity"; in this astronomically unlikely event, a new random curve point is recalculated. G is specified by giving its W-coordinate. The Z-coordinate is calculated from the curve equation. In general, there will be two possible Z values. The rule is to choose the "positive" value. In the (mod P) case, the two possible Z values sum to P. The smaller value is less than P/2; it is used in subsequent calculations. In GF[P^D] fields, the highest-degree non-zero coefficient of the field element Z is used; it is chosen to be less than P/2. In the GF[2^N] case, the two possible Z values xor to W (or to the parameter C with the alternate curve equation). The numerically smaller Z value (the one which does not contain the highest-order 1 bit of W (or C)) is used in subsequent calculations. Y is specified by giving the W-coordinate of the user's public signature key. The Z-coordinate value is determined from the curve equation. As with G, there are two possible Z values; the same rule is followed for choosing which Z to use. R. Schroeppel, et al [Page 10]

INTERNET-DRAFT ECC Keys in the DNS During the key generation process, a random [RFC 1750] number X must be generated such that 1 <= X <= Q-1. X is the private key and is used in the final step of public key generation where Y is computed as Y = X * G (as points on the elliptic curve) If the Z-coordinate of the computed point Y is wrong (i.e., Z > P/2 in the (mod P) case, or the high-order non-zero coefficient of Z > P/2 in the GF[P^D] case, or Z sharing a high bit with W(C) in the GF[2^N] case), then X must be replaced with Q-X. This will correspond to the correct Z-coordinate. 5. Performance Considerations Elliptic curve signatures use smaller moduli or field sizes than RSA and DSA. Creation of a curve is slow, but not done very often. Key generation is faster than RSA or DSA. DNS implementations have been optimized for small transfers, typically less than 512 octets including DNS overhead. Larger transfers will perform correctly and and extensions have been standardized to make larger transfers more efficient [RFC 2671]. However, it is still advisable at this time to make reasonable efforts to minimize the size of RR sets stored within the DNS consistent with adequate security. 6. Security Considerations Many of the general security consideration in [RFC 2535] apply. Some specific key generation considerations are given above. Of course, the elliptic curve key stored in the DNS for an entity should not be trusted unless it has been obtain via a trusted DNS resolver that vouches for its security or unless the application using the key has done a similar authentication. 7. IANA Considerations Assignment of meaning to the remaining ECC data flag bits or to values of ECC fields outside the ranges for which meaning in defined in this document requires an IETF consensus as defined in [RFC 2434]. R. Schroeppel, et al [Page 11]

INTERNET-DRAFT ECC Keys in the DNS Informational References [RFC 1034] - P. Mockapetris, "Domain names - concepts and facilities", 11/01/1987. [RFC 1035] - P. Mockapetris, "Domain names - implementation and specification", 11/01/1987. [RFC 1750] - D. Eastlake, S. Crocker, J. Schiller, "Randomness Recommendations for Security", 12/29/1994. [RFC 2535] - D. Eastlake,"Domain Name System Security Extensions", March 1999. [RFC 2671] - P. Vixie, "Extension Mechanisms for DNS (EDNS0)", August 1999. [Schneier] - Bruce Schneier, "Applied Cryptography: Protocols, Algorithms, and Source Code in C", 1996, John Wiley and Sons [Menezes] - Alfred Menezes, "Elliptic Curve Public Key Cryptosystems", 1993 Kluwer. [Silverman] - Joseph Silverman, "The Arithmetic of Elliptic Curves", 1986, Springer Graduate Texts in mathematics #106. Normative Refrences [RFC 2119] - S. Bradner, "Key words for use in RFCs to Indicate Requirement Levels", March 1997. [RFC 2434] - T. Narten, H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", October 1998. R. Schroeppel, et al [Page 12]

INTERNET-DRAFT ECC Keys in the DNS Authors' Addresses Rich Schroeppel 500 S. Maple Drive Woodland Hills, UT 84653 USA Telephone: 1-801-423-7998(h) 1-505-844-9079(w) Email: rcs@cs.arizona.edu rschroe@sandia.gov Donald E. Eastlake 3rd Motorola 155 Beaver Street Milford, MA 01757 USA Telephone: +1 508-634-2066 (h) +1 508-851-8280 (w) EMail: Donald.Eastlake@motorola.com Expiration and File Name This draft expires in February 2004. Its file name is draft-ietf-dnsext-ecc-key-04.txt. R. Schroeppel, et al [Page 13]