draft-ietf-dnsext-ecc-key-08.txt   draft-ietf-dnsext-ecc-key-09.txt 
INTERNET-DRAFT Richard C. Schroeppel INTERNET-DRAFT Richard C. Schroeppel
Donald Eastlake 3rd Donald E. Eastlake 3rd
Expires: April 2006 October 2005 Expires: October 2006 April 2006
Elliptic Curve Keys and Signatures in the DNS Elliptic Curve Keys and Signatures in the Domain Name System (DNS)
-------- ----- ---- --- ---------- -- --- ---- -------- ----- ---- --- ---------- -- --- ------ ---- ------ -----
<draft-ietf-dnsext-ecc-key-08.txt> <draft-ietf-dnsext-ecc-key-09.txt>
Richard C. Schroeppel Richard C. Schroeppel
Donald Eastlake 3rd Donald Eastlake 3rd
Status of This Document Status of This Document
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware 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 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. aware will be disclosed, in accordance with Section 6 of BCP 79.
skipping to change at page 1, line 43 skipping to change at page 1, line 43
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.html http://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html http://www.ietf.org/shadow.html
Abstract Abstract
The standard method for storing elliptic curve cryptographic keys and The standard format for storing elliptic curve cryptographic keys and
elliptic curve SHA-1 based signatures in the Domain Name System is elliptic curve SHA-1 based signatures in the Domain Name System (DNS)
specified. is specified.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2005). Copyright (C) The Internet Society (2006).
INTERNET-DRAFT ECC in the DNS INTERNET-DRAFT ECC in the DNS
Acknowledgement Acknowledgement
The assistance of Hilarie K. Orman in the production of this document The assistance of Hilarie K. Orman in the production of this document
is greatfully acknowledged. is greatfully acknowledged.
Table of Contents Table of Contents
skipping to change at page 2, line 25 skipping to change at page 2, line 25
Abstract...................................................1 Abstract...................................................1
Copyright Notice...........................................1 Copyright Notice...........................................1
Acknowledgement............................................2 Acknowledgement............................................2
Table of Contents..........................................2 Table of Contents..........................................2
1. Introduction............................................3 1. Introduction............................................3
2. Elliptic Curve Keys in Resource Records.................3 2. Elliptic Curve Keys in Resource Records.................3
3. The Elliptic Curve Equation.............................9 3. The Elliptic Curve Equation.............................9
4. How do I Compute Q, G, and Y?..........................10 4. How do I Compute Q, G, and Y?..........................10
5. Elliptic Curve Signature Resource Records..............11 5. Elliptic Curve Signatures..............................11
6. Performance Considerations.............................13 6. Performance Considerations.............................13
7. Security Considerations................................13 7. Security Considerations................................13
8. IANA Considerations....................................13 8. IANA Considerations....................................13
Copyright and Disclaimer..................................14 Copyright, Disclaimer, and Additional IPR Provisions......13
Informational References..................................15 Informational References..................................15
Normative Refrences.......................................15 Normative Refrences.......................................15
Author's Addresses........................................16 Author's Addresses........................................16
Expiration and File Name..................................16 Expiration and File Name..................................16
INTERNET-DRAFT ECC in the DNS INTERNET-DRAFT ECC in the DNS
1. Introduction 1. Introduction
The Domain Name System (DNS) is the global hierarchical replicated The Domain Name System (DNS) is the global hierarchical replicated
distributed database system for Internet addressing, mail proxy, and distributed database system for Internet addressing, mail proxy, and
other information. The DNS has been extended to include digital other information. [RFC 1034, 1035] The DNS stores data in resource
signatures and cryptographic keys as described in [RFC 4033, 4034, records and has been extended to include digital signatures and
4035]. cryptographic keys in some of these resource records.
This document describes how to store elliptic curve cryptographic This document describes how to format elliptic curve cryptographic
(ECC) keys and signatures in the DNS so they can be used for a (ECC) key and signature data in the DNS so they can be used for a
variety of security purposes. The signatures use the SHA-1 eigest variety of purposes. The signatures use the SHA-1 eigest algorithm
algorithm [RFC 3174]. Familiarity with ECC cryptography is assumed [RFC 3174]. Familiarity with ECC cryptography is assumed [Menezes].
[Menezes].
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC 2119]. document are to be interpreted as described in [RFC 2119].
2. Elliptic Curve Keys in Resource Records 2. Elliptic Curve Keys in Resource Records
Elliptic curve public keys are stored in the DNS within the RDATA Elliptic curve public keys are stored, using the structure described
portions of key RRs, such as RRKEY and KEY [RFC 4034] RRs, with the below, in the DNS within the RDATA portions of key RRs, such as RRKEY
structure shown below. [RFC 4034] and IPSECKEY [RFC 4025] RRs.
The research world continues to work on the issue of which is the 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 elliptic curve system, which finite field to use, and how to
best represent elements in the field. So, representations are best represent elements in the field. So, representations are
defined for every type of finite field, and every type of elliptic defined for every type of finite field, and every type of elliptic
curve. The reader should be aware that there is a unique finite curve. The reader should be aware that there is a unique finite
field with a particular number of elements, but many possible field with a particular number of elements, but many possible
representations of that field and its elements. If two different representations of that field and its elements. If two different
representations of a field are given, they are interconvertible with representations of a field are given, they are interconvertible with
a tedious but practical precomputation, followed by a fast a tedious but practical precomputation, followed by a fast
skipping to change at page 11, line 20 skipping to change at page 11, line 20
as as
Y = X * G (as points on the elliptic curve) 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 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 > 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 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 GF[2^N] case), then X must be replaced with Q-X. This will
correspond to the correct Z-coordinate. correspond to the correct Z-coordinate.
5. Elliptic Curve Signature Resource Records 5. Elliptic Curve Signatures
The signature portion of an RR RDATA area when using the EC The signature portion of an RR RDATA area when using the ECC
algorithm, for example in the RRSIG and SIG [RFC records] RRs is algorithm, for example in the SIG and RRSIG [RFC 4304] RRs is shown
shown below. below.
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 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 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) .../ | R, (length determined from LQ) .../
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| S, (length determined from LQ) .../ | S, (length determined from LQ) .../
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
R and S are integers (mod Q). Their length is specified by the LQ R and S are integers (mod Q). Their length is specified by the LQ
skipping to change at page 11, line 47 skipping to change at page 11, line 47
The same conditional formula for calculating the length from LQ is The same conditional formula for calculating the length from LQ is
used as for all the other length fields above. used as for all the other length fields above.
The data signed is determined as specified in [RFC 2535]. Then the 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 following steps are taken where Q, P, G, and Y are as specified in
the public key [Schneier]. For further information on SHA-1, see [RFC the public key [Schneier]. For further information on SHA-1, see [RFC
3174]. 3174].
hash = SHA-1 ( data ) hash = SHA-1 ( data )
Generate random [RFC 4086] K such that 0 < K < Q. (Never sign two Generate random [RFC 4086] K such that 0 < K < Q. (Never sign
different messages with the same K. K should be chosen from a two different messages with the same K. K should be chosen
very large space: If an opponent learns a K value for a single from a very large space: If an opponent learns a K value
signature, the user's signing key is compromised, and a forger for a single signature, the user's signing key is
can sign arbitrary messages. There is no harm in signing the compromised, and a forger can sign arbitrary messages.
same message multiple times with the same key or different There is no harm in signing the same message multiple times
keys.) with the same key or different keys.)
INTERNET-DRAFT ECC in the DNS INTERNET-DRAFT ECC in the DNS
R = (the W-coordinate of ( K*G on the elliptic curve )) interpreted R = (the W-coordinate of ( K*G on the elliptic curve ))
as an integer, and reduced (mod Q). (R must not be 0. In interpreted as an integer, and reduced (mod Q). (R must
this astronomically unlikely event, generate a new random K not be 0. In this astronomically unlikely event, generate
and recalculate R.) a new random K and recalculate R.)
S = ( K^(-1) * (hash + X*R) ) mod Q. S = ( K^(-1) * (hash + X*R) ) mod Q.
S must not be 0. In this astronomically unlikely event, generate a S must not be 0. In this astronomically unlikely event,
new random K and recalculate R and S. generate a new random K and recalculate R and S.
If S > Q/2, set S = Q - S. If S > Q/2, set S = Q - S.
The pair (R,S) is the signature. The pair (R,S) is the signature.
Another party verifies the signature as follows. For further Another party verifies the signature as follows. For further
information on SHA-1, see [RFC 3174]. information on SHA-1, see [RFC 3174].
Check that 0 < R < Q and 0 < S < Q/2. If not, it can not be a Check that 0 < R < Q and 0 < S < Q/2. If not, it can not be a
valid EC sigature. valid EC sigature.
skipping to change at page 12, line 44 skipping to change at page 12, line 44
(U1 * G + U2 * Y) is computed on the elliptic curve. (U1 * G + U2 * Y) is computed on the elliptic curve.
V = (the W-coordinate of this point) interpreted as an integer V = (the W-coordinate of this point) interpreted as an integer
and reduced (mod Q). and reduced (mod Q).
The signature is valid if V = R. The signature is valid if V = R.
The reason for requiring S < Q/2 is that, otherwise, both (R,S) and The reason for requiring S < Q/2 is that, otherwise, both (R,S) and
(R,Q-S) would be valid signatures for the same data. Note that a (R,Q-S) would be valid signatures for the same data. Note that a
signature that is valid for hash(data) is also valid for signature that is valid for hash(data) is also valid for hash(data)+Q
hash(data)+Q or hash(data)-Q, if these happen to fall in the range or hash(data)-Q, if these happen to fall in the range [0,2^160-1].
[0,2^160-1]. It's believed to be computationally infeasible to It's believed to be computationally infeasible to find data that
find data that hashes to an assigned value, so this is only a hashes to an assigned value, so this is only a cosmetic blemish. The
cosmetic blemish. The blemish can be eliminated by using Q > blemish can be eliminated by using Q > 2^160, at the cost of having
2^160, at the cost of having slightly longer signatures, 42 octets slightly longer signatures, 42 octets instead of 40.
instead of 40.
We must specify how a field-element E ("the W-coordinate") is to be We must specify how a field-element E ("the W-coordinate") is to be
interpreted as an integer. The field-element E is regarded as a interpreted as an integer. The field-element E is regarded as a
radix-P integer, with the digits being the coefficients in the radix-P integer, with the digits being the coefficients in the
polynomial basis representation of E. The digits are in the ragne polynomial basis representation of E. The digits are in the ragne
[0,P-1]. In the two most common cases, this reduces to "the [0,P-1]. 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
INTERNET-DRAFT ECC in the DNS INTERNET-DRAFT ECC in the DNS
obvious thing". In the (mod P) case, E is simply a residue mod P, taken as an integer in the range [0,P-1]. In the GF[2^D] case, E is
and is taken as an integer in the range [0,P-1]. In the GF[2^D] in the D-bit polynomial basis representation, and is simply taken as
case, E is in the D-bit polynomial basis representation, and is an integer in the range [0,(2^D)-1]. For other fields GF[P^D], it's
simply taken as an integer in the range [0,(2^D)-1]. For other necessary to do some radix conversion arithmetic.
fields GF[P^D], it's necessary to do some radix conversion
arithmetic.
6. Performance Considerations 6. Performance Considerations
Elliptic curve signatures use smaller moduli or field sizes than Elliptic curve signatures use smaller moduli or field sizes than RSA
RSA and DSA. Creation of a curve is slow, but not done very often. and DSA. Creation of a curve is slow, but not done very often. Key
Key generation is faster than RSA or DSA. generation is faster than RSA or DSA.
DNS implementations have been optimized for small transfers, DNS implementations have been optimized for small transfers,
typically less than 512 octets including DNS overhead. Larger typically less than 512 octets including DNS overhead. Larger
transfers will perform correctly and and extensions have been transfers will perform correctly and and extensions have been
standardized to make larger transfers more efficient [RFC 2671]. standardized to make larger transfers more efficient [RFC 2671].
However, it is still advisable at this time to make reasonable However, it is still advisable at this time to make reasonable
efforts to minimize the size of RR sets stored within the DNS efforts to minimize the size of RR sets stored within the DNS
consistent with adequate security. consistent with adequate security.
7. Security Considerations 7. Security Considerations
Keys retrieved from the DNS should not be trusted unless (1) they Keys retrieved from the DNS should not be trusted unless (1) they
have been securely obtained from a secure resolver or independently have been securely obtained from a secure resolver or independently
verified by the user and (2) this secure resolver and secure verified by the user and (2) this secure resolver and secure
obtainment or independent verification conform to security policies obtainment or independent verification conform to security policies
acceptable to the user. As with all cryptographic algorithms, acceptable to the user. As with all cryptographic algorithms,
evaluating the necessary strength of the key is essential and evaluating the necessary strength of the key is essential and
dependent on local policy. dependent on local policy.
Some specific key generation considerations are given in the body Some specific key generation considerations are given in the body of
of this document. this document.
8. 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 Assignment of meaning to the remaining ECC data flag bits or to
values of ECC fields outside the ranges for which meaning in values of ECC fields outside the ranges for which meaning in defined
defined in this document requires an IETF consensus as defined in in this document requires an IETF consensus as defined in [RFC 2434].
[RFC 2434].
INTERNET-DRAFT ECC in the DNS Copyright, Disclaimer, and Additional IPR Provisions
Copyright and Disclaimer Copyright (C) The Internet Society 2006.
Copyright (C) The Internet Society 2005. INTERNET-DRAFT ECC in the DNS
This document is subject to the rights, licenses and restrictions This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors contained in BCP 78, and except as set forth therein, the authors
retain all their rights. retain all their rights.
This document and the information contained herein are provided on This document and the information contained herein are provided on an
an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
PARTICULAR PURPOSE.
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at ietf-
ipr@ietf.org.
INTERNET-DRAFT ECC in the DNS INTERNET-DRAFT ECC in the DNS
Informational References Informational References
[RFC 1034] - P. Mockapetris, "Domain names - concepts and [RFC 1034] - P. Mockapetris, "Domain names - concepts and
facilities", 11/01/1987. facilities", 11/01/1987.
[RFC 1035] - P. Mockapetris, "Domain names - implementation and [RFC 1035] - P. Mockapetris, "Domain names - implementation and
specification", 11/01/1987. specification", 11/01/1987.
[RFC 2671] - P. Vixie, "Extension Mechanisms for DNS (EDNS0)", [RFC 2671] - P. Vixie, "Extension Mechanisms for DNS (EDNS0)", August
August 1999. 1999.
[RFC 4033] - Arends, R., Austein, R., Larson, M., Massey, D., and [RFC 4025] - M. Richardson, "A Method for Storing IPsec Keying
S. Rose, "DNS Security Introduction and Requirements", RFC 4033, Material in DNS", February 2005.
March 2005.
[RFC 4035] - Arends, R., Austein, R., Larson, M., Massey, D., and [RFC 4033] - Arends, R., Austein, R., Larson, M., Massey, D., and S.
S. Rose, "Protocol Modifications for the DNS Security Extensions", Rose, "DNS Security Introduction and Requirements", RFC 4033, March
RFC 4035, March 2005. 2005.
[RFC 4035] - Arends, R., Austein, R., Larson, M., Massey, D., and S.
Rose, "Protocol Modifications for the DNS Security Extensions", RFC
4035, March 2005.
[RFC 4086] - Eastlake, D., 3rd, Schiller, J., and S. Crocker, [RFC 4086] - Eastlake, D., 3rd, Schiller, J., and S. Crocker,
"Randomness Requirements for Security", BCP 106, RFC 4086, June "Randomness Requirements for Security", BCP 106, RFC 4086, June 2005.
2005.
[Schneier] - Bruce Schneier, "Applied Cryptography: Protocols, [Schneier] - Bruce Schneier, "Applied Cryptography: Protocols,
Algorithms, and Source Code in C", 1996, John Wiley and Sons Algorithms, and Source Code in C", 1996, John Wiley and Sons
[Menezes] - Alfred Menezes, "Elliptic Curve Public Key [Menezes] - Alfred Menezes, "Elliptic Curve Public Key
Cryptosystems", 1993 Kluwer. Cryptosystems", 1993 Kluwer.
[Silverman] - Joseph Silverman, "The Arithmetic of Elliptic [Silverman] - Joseph Silverman, "The Arithmetic of Elliptic Curves",
Curves", 1986, Springer Graduate Texts in mathematics #106. 1986, Springer Graduate Texts in mathematics #106.
Normative Refrences Normative Refrences
[RFC 2119] - S. Bradner, "Key words for use in RFCs to Indicate [RFC 2119] - S. Bradner, "Key words for use in RFCs to Indicate
Requirement Levels", March 1997. Requirement Levels", March 1997.
[RFC 2434] - T. Narten, H. Alvestrand, "Guidelines for Writing an [RFC 2434] - T. Narten, H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", October 1998. IANA Considerations Section in RFCs", October 1998.
[RFC 3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash [RFC 3174] - Eastlake 3rd, D. and P. Jones, "US Secure Hash Algorithm
Algorithm 1 (SHA1)", RFC 3174, September 2001. 1 (SHA1)", RFC 3174, September 2001.
[RFC 4034] - Arends, R., Austein, R., Larson, M., Massey, D., and [RFC 4034] - Arends, R., Austein, R., Larson, M., Massey, D., and S.
S. Rose, "Resource Records for the DNS Security Extensions", RFC Rose, "Resource Records for the DNS Security Extensions", RFC 4034,
4034, March 2005. March 2005.
INTERNET-DRAFT ECC in the DNS INTERNET-DRAFT ECC in the DNS
Author's Addresses Author's Addresses
Rich Schroeppel Rich Schroeppel
500 S. Maple Drive 500 S. Maple Drive
Woodland Hills, UT 84653 USA Woodland Hills, UT 84653 USA
Telephone: +1-505-844-9079(w) Telephone: +1-505-844-9079(w)
skipping to change at page 16, line 26 skipping to change at page 16, line 26
Donald E. Eastlake 3rd Donald E. Eastlake 3rd
Motorola Laboratories Motorola Laboratories
155 Beaver Street 155 Beaver Street
Milford, MA 01757 USA Milford, MA 01757 USA
Telephone: +1 508-786-7554 (w) Telephone: +1 508-786-7554 (w)
EMail: Donald.Eastlake@motorola.com EMail: Donald.Eastlake@motorola.com
Expiration and File Name Expiration and File Name
This draft expires in April 2006. This draft expires in October 2006.
Its file name is draft-ietf-dnsext-ecc-key-08.txt. Its file name is draft-ietf-dnsext-ecc-key-09.txt.
 End of changes. 34 change blocks. 
93 lines changed or deleted 109 lines changed or added

This html diff was produced by rfcdiff 1.29, available from http://www.levkowetz.com/ietf/tools/rfcdiff/