 1/draftietfdnsextecckey07.txt 20060204 17:20:26.000000000 +0100
+++ 2/draftietfdnsextecckey08.txt 20060204 17:20:26.000000000 +0100
@@ 1,17 +1,18 @@
INTERNETDRAFT ECC Keys in the DNS
Expires: January 2006 July 2005
+INTERNETDRAFT Richard C. Schroeppel
+ Donald Eastlake 3rd
+Expires: April 2006 October 2005
 Elliptic Curve KEYs in the DNS
      

+ Elliptic Curve Keys and Signatures in the DNS
+        
+
Richard C. Schroeppel
Donald Eastlake 3rd
Status of This Document
By submitting this InternetDraft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
@@ 21,109 +22,111 @@
to the DNS mailing list .
InternetDrafts 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.
InternetDrafts 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 InternetDrafts as reference
 material or to cite them other than a "work in progress."
+ material or to cite them other than as "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 and
 signatures in the Domain Name System is specified.
+ elliptic curve SHA1 based signatures in the Domain Name System is
+ specified.
Copyright Notice
 Copyright (C) The Internet Society (2005). All Rights Reserved.
+ Copyright (C) The Internet Society (2005).
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC 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
Copyright Notice...........................................1
Acknowledgement............................................2
Table of Contents..........................................2
1. Introduction............................................3
 2. Elliptic Curve Data in Resource Records.................3
+ 2. Elliptic Curve Keys in Resource Records.................3
3. The Elliptic Curve Equation.............................9
4. How do I Compute Q, G, and Y?..........................10
 5. Elliptic Curve SIG Resource Records....................11
+ 5. Elliptic Curve Signature Resource Records..............11
6. Performance Considerations.............................13
7. Security Considerations................................13
8. IANA Considerations....................................13
Copyright and Disclaimer..................................14
Informational References..................................15
Normative Refrences.......................................15
Author's Addresses........................................16
Expiration and File Name..................................16
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC 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 4033, 4034,
4035].
This document describes how to store elliptic curve cryptographic
(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].
+ variety of security purposes. The signatures use the SHA1 eigest
+ algorithm [RFC 3174]. 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
+2. Elliptic Curve Keys in Resource Records
Elliptic curve public keys are stored in the DNS within the RDATA
portions of key RRs, such as RRKEY and KEY [RFC 4034] 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
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.
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC 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) .../
+++++++++++++++++++++++++++++++++
@@ 162,21 +165,21 @@
 LB 
+++++++++++++++++++++++++++++++++
 B (length determined from LB) .../
+++++++++++++++++++++++++++++++++
 LC 
+++++++++++++++++++++++++++++++++
 C (length determined from LC) .../
+++++++++++++++++++++++++++++++++
 LG 
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC in the DNS
+++++++++++++++++++++++++++++++++
 G (length determined from LG) .../
+++++++++++++++++++++++++++++++++
 LY 
+++++++++++++++++++++++++++++++++
 Y (length determined from LY) .../
+++++++++++++++++++++++++++++++++
SMFMTABZ is a flags octet as follows:
@@ 211,21 +214,21 @@
= 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.
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC 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.
@@ 264,21 +267,21 @@
ceiling(log2 P) bits. Coefficients are in the numerical range
[0,P1]. The coefficients are packed into fixedwidth 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 loworder "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
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC in the DNS
determining the bit position of the left most 1bit 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.
@@ 317,21 +320,21 @@
divisor. The small polynomial is rightadjusted in the two octet
field TRDV. DEG specifies the degree of the field. The degree of
TRDV is calculated from the position of the highorder 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 2octet
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC 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 twooctet 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 twooctet rightadjusted binary polynomial of degree <
@@ 367,21 +370,21 @@
PK. 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 highorder 0 coefficients or bits.
If the finite field is simply (mod P), then the field elements are
simply numbers (mod P), in the usual rightjustified notation. If
the finite field is GF[2^D], the field elements are the usual right
justified polynomial basis representation.
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC 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
@@ 418,21 +421,21 @@
+ 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 righthandside is different. When P=3, this equation is more
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC 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 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?
@@ 465,36 +468,36 @@
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
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
+INTERNETDRAFT ECC 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. Elliptic Curve SIG Resource Records
+5. Elliptic Curve Signature Resource Records
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) .../
+++++++++++++++++++++++++++++++++
@@ 502,50 +505,51 @@
+++++++++++++++++++++++++++++++++
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]:
+ the public key [Schneier]. For further information on SHA1, see [RFC
+ 3174].
hash = SHA1 ( data )
Generate random [RFC 4086] 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
+INTERNETDRAFT ECC in the DNS
+ R = (the Wcoordinate of ( K*G on the elliptic curve )) interpreted
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:
+ Another party verifies the signature as follows. For further
+ information on SHA1, see [RFC 3174].
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.
@@ 566,25 +570,25 @@
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
+INTERNETDRAFT ECC in the DNS
+ 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]
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.
@@ 613,38 +617,40 @@
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 in this document requires an IETF consensus as defined in
[RFC 2434].
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC in the DNS
Copyright and Disclaimer
 Copyright (C) The Internet Society 2005. 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 2005.
+
+ 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.
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC 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 2671]  P. Vixie, "Extension Mechanisms for DNS (EDNS0)",
@@ 672,38 +678,41 @@
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 3174]  Eastlake 3rd, D. and P. Jones, "US Secure Hash
+ Algorithm 1 (SHA1)", RFC 3174, September 2001.
+
[RFC 4034]  Arends, R., Austein, R., Larson, M., Massey, D., and
S. Rose, "Resource Records for the DNS Security Extensions", RFC
4034, March 2005.
INTERNETDRAFT ECC Keys in the DNS
+INTERNETDRAFT ECC in the DNS
Author's Addresses
Rich Schroeppel
500 S. Maple Drive
Woodland Hills, UT 84653 USA
Telephone: +15058449079(w)
Email: rschroe@sandia.gov
Donald E. Eastlake 3rd
Motorola Laboratories
155 Beaver Street
Milford, MA 01757 USA
Telephone: +1 5087867554 (w)
EMail: Donald.Eastlake@motorola.com
Expiration and File Name
 This draft expires in January 2006.
+ This draft expires in April 2006.
 Its file name is draftietfdnsextecckey07.txt.
+ Its file name is draftietfdnsextecckey08.txt.