 1/draftietfdnsextecckey05.txt 20060204 23:10:35.000000000 +0100
+++ 2/draftietfdnsextecckey06.txt 20060204 23:10:35.000000000 +0100
@@ 1,18 +1,17 @@
©À
INTERNETDRAFT ECC Keys in the DNS
Expires: February 2005 August 2004
+Expires: June 2005 December 2004
Elliptic Curve KEYs in the DNS
     

+
Richard C. Schroeppel
Donald Eastlake 3rd
Status of This Document
By submitting this InternetDraft, I certify that any applicable
patent or other IPR claims of which I am aware have been disclosed,
or will be disclosed, and any of which I become aware will be
disclosed, in accordance with RFC 3668.
@@ 32,22 +31,22 @@
material or to cite them other than a "work in progress."
The list of current InternetDrafts can be accessed at
http://www.ietf.org/1idabstracts.html
The list of InternetDraft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
Abstract
 The standard method for storing elliptic curve cryptographic keys in
 the Domain Name System is specified.
+ The standard method for storing elliptic curve cryptographic keys and
+ signatures in the Domain Name System is specified.
Copyright Notice
Copyright (C) The Internet Society. All Rights Reserved.
INTERNETDRAFT ECC Keys in the DNS
Acknowledgement
The assistance of Hilarie K. Orman in the production of this document
@@ 59,58 +58,56 @@
Abstract...................................................1
Copyright Notice...........................................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
 Copyright and Disclaimer..................................12
+ 5. Elliptic Curve SIG Resource Records....................11
+ 6. Performance Considerations.............................13
+ 7. Security Considerations................................13
+ 8. IANA Considerations....................................13
+ Copyright and Disclaimer..................................14
 Informational References..................................13
 Normative Refrences.......................................13
+ Informational References..................................15
+ Normative Refrences.......................................15
 Authors Addresses.........................................14
 Expiration and File Name..................................14
+ Author's Addresses........................................16
+ Expiration and File Name..................................16
INTERNETDRAFT 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 intro,
protocol, records].
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].
+ (ECC) keys and signatures in the DNS so they can be used for a
+ variety of security purposes. 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 key RRs with the structure shown below [RFC records].

 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.
+ portions of key RRs, such as RRKEY and KEY [RFC records] RRs, with
+ the structure shown below.
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, representations are
defined 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
@@ 291,21 +288,21 @@
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 highestdegree
coefficients first  the leading coefficient 1 is most important,
and the constant term is least important. Coefficients are ordered
by signmagnitude: 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^D1, which isn‚ÇÖt. Assuming
+ is sometimes irreducible, followed by X^D1, which isn't. Assuming
odd P, this series continues to X^D  (P1)/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 highorder 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 +
@@ 395,21 +392,21 @@
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 Wcoordinate
of the curve point is given explicitly; the Zcoordinate is
implicit.
 LY,Y is the user‚ÇÖs public signing key, another curve point of
+ LY,Y is the user's public signing key, another curve point of
order Q. The Wcoordinate 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.)
@@ 436,21 +433,21 @@
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 single1bit 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
+ 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 (numberofpointsoncurve/Q). G must not itself
be the "point at infinity"; in this astronomically unlikely event, a
@@ 463,151 +460,251 @@
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 highestdegree nonzero 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 highestorder 1
bit of W (or C)) is used in subsequent calculations.
 Y is specified by giving the Wcoordinate of the user‚ÇÖs public
+ Y is specified by giving the Wcoordinate of the user's public
signature key. The Zcoordinate 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.
INTERNETDRAFT ECC Keys in the DNS
During the key generation process, a random [RFC 1750] number X must
be generated such that 1 <= X <= Q1. 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 Zcoordinate of the computed point Y is wrong (i.e., Z > P/2
in the (mod P) case, or the highorder nonzero 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 QX. This will
correspond to the correct Zcoordinate.
5. Performance Considerations
+5. Elliptic Curve SIG Resource Records
 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.
+ The signature portion of an RR RDATA area when using the EC
+ algorithm, for example in the RRSIG and SIG [RFC records] RRs is
+ shown below.
+
+ 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
+ +++++++++++++++++++++++++++++++++
+  R, (length determined from LQ) .../
+ +++++++++++++++++++++++++++++++++
+  S, (length determined from LQ) .../
+ +++++++++++++++++++++++++++++++++
+
+ R and S are integers (mod Q). Their length is specified by the LQ
+ field of the corresponding KEY RR and can also be calculated from the
+ SIG RR's RDLENGTH. They are right justified, highorderoctet first.
+ The same conditional formula for calculating the length from LQ is
+ used as for all the other length fields above.
+
+ The data signed is determined as specified in [RFC 2535]. Then the
+ following steps are taken where Q, P, G, and Y are as specified in
+ the public key [Schneier]:
+
+ hash = SHA1 ( data )
+
+ Generate random [RFC 1750] K such that 0 < K < Q. (Never sign two
+ different messages with the same K. K should be chosen from a
+ very large space: If an opponent learns a K value for a single
+ signature, the user's signing key is compromised, and a forger
+ can sign arbitrary messages. There is no harm in signing the
+ same message multiple times with the same key or different
+ keys.)
+
+ R = (the Wcoordinate of ( K*G on the elliptic curve )) interpreted
+
+INTERNETDRAFT ECC Keys in the DNS
+
+ as an integer, and reduced (mod Q). (R must not be 0. In
+ this astronomically unlikely event, generate a new random K
+ and recalculate R.)
+
+ S = ( K^(1) * (hash + X*R) ) mod Q.
+
+ S must not be 0. In this astronomically unlikely event, generate a
+ new random K and recalculate R and S.
+
+ If S > Q/2, set S = Q  S.
+
+ The pair (R,S) is the signature.
+
+ Another party verifies the signature as follows:
+
+ Check that 0 < R < Q and 0 < S < Q/2. If not, it can not be a
+ valid EC sigature.
+
+ hash = SHA1 ( data )
+
+ Sinv = S^(1) mod Q.
+
+ U1 = (hash * Sinv) mod Q.
+
+ U2 = (R * Sinv) mod Q.
+
+ (U1 * G + U2 * Y) is computed on the elliptic curve.
+
+ V = (the Wcoordinate of this point) interpreted as an integer
+ and reduced (mod Q).
+
+ The signature is valid if V = R.
+
+ The reason for requiring S < Q/2 is that, otherwise, both (R,S) and
+ (R,QS) would be valid signatures for the same data. Note that a
+ signature that is valid for hash(data) is also valid for
+ hash(data)+Q or hash(data)Q, if these happen to fall in the range
+ [0,2^1601]. It's believed to be computationally infeasible to
+ find data that hashes to an assigned value, so this is only a
+ cosmetic blemish. The blemish can be eliminated by using Q >
+ 2^160, at the cost of having slightly longer signatures, 42 octets
+ instead of 40.
+
+ We must specify how a fieldelement E ("the Wcoordinate") is to be
+ interpreted as an integer. The fieldelement E is regarded as a
+ radixP integer, with the digits being the coefficients in the
+ polynomial basis representation of E. The digits are in the ragne
+ [0,P1]. In the two most common cases, this reduces to "the
+ obvious thing". In the (mod P) case, E is simply a residue mod P,
+ and is taken as an integer in the range [0,P1]. In the GF[2^D]
+
+INTERNETDRAFT ECC Keys in the DNS
+
+ case, E is in the Dbit polynomial basis representation, and is
+ simply taken as an integer in the range [0,(2^D)1]. For other
+ fields GF[P^D], it's necessary to do some radix conversion
+ arithmetic.
+
+ 6. 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
+ 7. Security Considerations
Keys retrieved from the DNS should not be trusted unless (1) they
have been securely obtained from a secure resolver or independently
verified by the user and (2) this secure resolver and secure
obtainment or independent verification conform to security policies
acceptable to the user. As with all cryptographic algorithms,
evaluating the necessary strength of the key is essential and
dependent on local policy.
 Some specific key generation considerations are given in the body of
 this document.
+ Some specific key generation considerations are given in the body
+ of this document.
7. IANA Considerations
+ 8. IANA Considerations
+
+ The key and signature data structures defined herein correspond to
+ the value 4 in the Algorithm number field of the IANA registry
Assignment of meaning to the remaining ECC data flag bits or to
 values of ECC fields outside the ranges for which meaning in defined
+ values of ECC fields outside the ranges for which meaning in
+ defined in this document requires an IETF consensus as defined in
+ [RFC 2434].
INTERNETDRAFT ECC Keys in the DNS
 in this document requires an IETF consensus as defined in [RFC 2434].

Copyright and Disclaimer
 Copyright (C) The Internet Society 2004. This document is subject to
 the rights, licenses and restrictions contained in BCP 78 and except
 as set forth therein, the authors retain all their rights.
+ Copyright (C) The Internet Society 2004. This document is subject
+ to the rights, licenses and restrictions contained in BCP 78 and
+ except as set forth therein, the authors retain all their rights.
 This document and the information contained herein are provided on an
 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
+ This document and the information contained herein are provided on
+ an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
+ REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND
+ THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT
+ THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR
+ ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
+ PARTICULAR PURPOSE.
INTERNETDRAFT 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 intro]  "DNS Security Introduction and Requirements", R.
 Arends, M. Larson, R. Austein, D. Massey, S. Rose, work in progress,
 draftietfdnsextdnssecintro*.txt.
+ Arends, M. Larson, R. Austein, D. Massey, S. Rose, work in
+ progress, draftietfdnsextdnssecintro*.txt.
[RFC protocol]  "Protocol Modifications for the DNS Security
Extensions", R. Arends, M. Larson, R. Austein, D. Massey, S. Rose,
work in progress, draftietfdnsextdnssecprotocol*.txt.
 [RFC 2671]  P. Vixie, "Extension Mechanisms for DNS (EDNS0)", August
 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.
+ [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.
[RFC records]  "Resource Records for the DNS Security Extensions",
R. Arends, R. Austein, M. Larson, D. Massey, S. Rose, work in
progress, draftietfdnsextdnssecrecords *.txt.
INTERNETDRAFT ECC Keys in the DNS
Authors Addresses
+ Author's Addresses
Rich Schroeppel
500 S. Maple Drive
Woodland Hills, UT 84653 USA
 Telephone: 18014237998(h)
 15058449079(w)
+ Telephone: +15058449079(w)
+ +18014237998(h)
Email: rschroe@sandia.gov
Donald E. Eastlake 3rd
Motorola Laboratories
155 Beaver Street
Milford, MA 01757 USA
 Telephone: +1 5086342066 (h)
 +1 5087867554 (w)
+ Telephone: +1 5087867554 (w)
+ +1 5086342066 (h)
EMail: Donald.Eastlake@motorola.com
Expiration and File Name
 This draft expires in February 2004.
+ This draft expires in June 2004.
 Its file name is draftietfdnsextecckey05.txt.
+ Its file name is draftietfdnsextecckey06.txt.