Subject: [dnsext] WGLC: Elliptic Curve DSA

From: Olafur Gudmundsson <[email-masked]>
Date: Wed, 06 Jul 2011 17:17:52 -0400

Dear Colleagues

This message starts a Working Group Last Call for
"Elliptic Curve DSA for DNSSEC" located at
http://www.ietf.org/internet-drafts/draft-ietf-dnsext-ecdsa-01.txt
This document is on Standards track.

This WGLC will conclude on midnight on July 21'th UTC.

Please review the document and sent a statement that you reviewed the
document.  If the review raises any issues, please note what they are.
Remember that we need a minimum of 5 reviewers.

     Olafur & Andrew
_______________________________________________
dnsext mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/dnsext

---

From: Edward Lewis <[email-masked]>
Date: Thu, 7 Jul 2011 11:13:28 -0400

>This document is on Standards track.

I have some minor comments and some questions.

First, and this may fall into "style", "ECDSA" is not expanded in the 
Introduction (but it is in the abstract).  My preference has been to 
expand letters the first use in the main body of the document.

A more significant comment is that there is no reference defining 
ECDSA.  In particular, this paragraph:

#   This document defines the DNSKEY and RRSIG resource records (RRs) of
#   two new signing algorithms: ECDSA with curve P-256 and SHA-256, and
#   ECDSA with curve P-384 and SHA-384.  This document also defines the
#   DS RR for the SHA-384 one-way hash algorithm; the associated DS RR
#   for SHA-256 is already defined in RFC 4509 [RFC4509].

Lacks any document defining ECDSA.  In the references there are two 
FIPS listed.

(Mind you, I am not well read in cryptography.  For the most part I 
don't care for the details.  I'm just asking for a pointer where I 
could go read more if I cared.)

And my question.

When I saw the dreaded "DSA" I immediately harked back to the fact 
that is slower where it matters - verfication - than RSA.  And the 
draft does address this:

#  However, validating RSA signatures is significantly faster than validating
#  ECDSA signatures (about 5 times faster in some implementations).

 From what I gather, the case for ECDSA is that the keys and 
signatures is that they are shorter.

#  ECDSA keys are much shorter than RSA keys; at this size, the 
difference is 256
#  versus 3072 bits.  Similarly, ECDSA signatures are much shorter 
than RSA signatures.

Caveats I cut out here, because I'm no cryptogeek, is that the 
"shorter" is within the same "strengths" (whatever "strength" means) 
of protection.  I'm taking for granted, this is a pound of oranges 
vs. a pound of apples comparison.

What is set up here is the classic - "Space vs. Time" tradeoff.

So here's the question to the authors/experts on this.  Is the 
tradeoff worth it?  Is the extra slowness in validation worth the 
savings in bytes?  I haven't seen much evidence that larger DNSSEC 
responses are killing us - and I don't mean to say that there isn't a 
problem looming, but I don't see any evidence.  So I wonder about the 
value of the lost time (which is something DNS gets hammered with by 
web site operators).

This isn't a situation in which I can contribute text, but I would 
like to see a paragraph or two at least hypothesizing on the tradeoff 
and why ECDSA might be better than the current state of operations. 
Switching to ECDSA for the current 60+ signed TLDs and root would 
take some effort, would it be worth it?

(Yeah, the latter question is one for operators.  I'm asking for the 
experts prognostication if they are willing.)

-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis             
NeuStar                    You can leave a voice message at +1-571-434-5468

I'm overly entertained.

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 7 Jul 2011 08:47:19 -0700

On Jul 7, 2011, at 8:13 AM, Edward Lewis wrote:

> First, and this may fall into "style", "ECDSA" is not expanded in the Introduction (but it is in the abstract).  My preference has been to expand letters the first use in the main body of the document.

Good catch, will do.

> A more significant comment is that there is no reference defining ECDSA.  In particular, this paragraph:
> 
> Lacks any document defining ECDSA.  In the references there are two FIPS listed.

It is not just in the references: Section 3 points directly to the FIPS document that defines the curves used in ECDSA.

> (Mind you, I am not well read in cryptography.  For the most part I don't care for the details.  I'm just asking for a pointer where I could go read more if I cared.)

FIPS 186-3, as listed in Section 3. Not that I'm recommending it, mind you.

> And my question.
> 
> When I saw the dreaded "DSA" I immediately harked back to the fact that is slower where it matters - verfication - than RSA.  And the draft does address this:
> 
> From what I gather, the case for ECDSA is that the keys and signatures is that they are shorter.
> 
> #  ECDSA keys are much shorter than RSA keys; at this size, the difference is 256
> #  versus 3072 bits.  Similarly, ECDSA signatures are much shorter than RSA signatures.
> 
> Caveats I cut out here, because I'm no cryptogeek, is that the "shorter" is within the same "strengths" (whatever "strength" means) of protection.  I'm taking for granted, this is a pound of oranges vs. a pound of apples comparison.
> 
> So here's the question to the authors/experts on this.  Is the tradeoff worth it?  

Yes.

> Is the extra slowness in validation worth the savings in bytes?  

That is not the only tradeoff. The strength of RSA keys goes down year after year, but the strength of ECDSA keys hasn't declined at all. For sites that require a certain strength and want that strength year after year, they have to increase the length of their RSA keys.

> I haven't seen much evidence that larger DNSSEC responses are killing us - and I don't mean to say that there isn't a problem looming, but I don't see any evidence.  So I wonder about the value of the lost time (which is something DNS gets hammered with by web site operators).

That is going to depend on the preferences of who is doing the measurements. ECDSA allows the hosts who have a particular set of priorities to use smaller keys that don't degrade; RSA allows hosts who don't feel the need for as much security to use keys that will validate somewhat faster.

> This isn't a situation in which I can contribute text, but I would like to see a paragraph or two at least hypothesizing on the tradeoff and why ECDSA might be better than the current state of operations. Switching to ECDSA for the current 60+ signed TLDs and root would take some effort, would it be worth it?

Please, no. That kind of pie-in-the-sky speculation does not belong in a technical document such as this. If you feel like writing such a document in DNSOP, great, but it really doesn't belong here. 

> (Yeah, the latter question is one for operators.  I'm asking for the experts prognostication if they are willing.)

Not willing.

--Paul Hoffman

---

From: Edward Lewis <[email-masked]>
Date: Thu, 7 Jul 2011 13:32:08 -0400

At 8:47 -0700 7/7/11, Paul Hoffman wrote:
>It is not just in the references: Section 3 points directly to the 
>FIPS document that defines the curves used in ECDSA.

Then the nit - please add the refernce earlier.

>That is not the only tradeoff. The strength of RSA keys goes down year
>after year, but the strength of ECDSA keys hasn't declined at all. For
>sites that require a certain strength and want that strength year after
>year, they have to increase the length of their RSA keys.

>That is going to depend on the preferences of who is doing the measurements.
>ECDSA allows the hosts who have a particular set of priorities to use
>smaller keys that don't degrade; RSA allows hosts who don't feel the need
>for as much security to use keys that will validate somewhat faster.

I'd like to see those words in the doc.

>Please, no. That kind of pie-in-the-sky speculation does not belong
>in a technical document such as this.

Ok, I get that.

>>   asking for the experts prognostication if they are willing.
>Not willing.

Chicken ;)

I'm overly entertained.

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 7 Jul 2011 10:54:17 -0700

> Then the nit - please add the refernce earlier.

Will do.

> I'd like to see those words in the doc.

Not unless others in the WG really want this. Other docs that have described different crypto algorithms (such as different hash functions) haven't had such descriptions, and I think that's a good thing. Crypto protocol descriptions should not be telling people how to consider them.

--Paul Hoffman

---

From: Edward Lewis <[email-masked]>
Date: Thu, 7 Jul 2011 14:05:14 -0400

At 10:54 -0700 7/7/11, Paul Hoffman wrote:

>Not unless others in the WG really want this. Other docs that have
>described different crypto algorithms (such as different hash functions)
>haven't had such descriptions, and I think that's a good thing. Crypto
>protocol descriptions should not be telling people how to consider them.

But this is a DNS document and we need all the help we can get when 
it comes to understanding crypto, at least as far as it's role in 
DNSSEC deployments.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis
NeuStar                    You can leave a voice message at +1-571-434-5468

I'm overly entertained.

---

From: Olafur Gudmundsson <[email-masked]>
Date: Thu, 07 Jul 2011 14:18:02 -0400

On 07/07/2011 2:05 PM, Edward Lewis wrote:
> But this is a DNS document and we need all the help we can get when it
> comes to understanding crypto, at least as far as it's role in DNSSEC
> deployments.

<chair-hat=on>

I tend to agree with Paul on this one, this is not appropriate content 
for a code allocation document.

I think something like this might be published as BCP in a separate 
document.

	Olafur

---

From: Scott Rose <[email-masked]>
Date: Thu, 7 Jul 2011 14:23:03 -0400

> Not unless others in the WG really want this. Other docs that have described different crypto algorithms (such as different hash functions) haven't had such descriptions, and I think that's a good…

I don't think it is needed in this doc, since it was never considered to be needed in any other algorithm spec doc.  Sounds like something like that would belong in a larger DNSSEC crypto considerations document since similar text would be desired for other algorithms and not just ECDSA.

Scott

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 7 Jul 2011 19:36:05 -0400

Section 8:

"The cryptographic strength of ECDSA with curve P-256 or P-384 is
   generally considered to be equivalent to half the size of the key, or
   128 bits and 192 bits, respectively. "

This should be 'Work Factor'

Whit Diffie corrected me on this while I was speaking at a conference. Work
factor is the way to think about it. 128 bits does not in itself imply a
difficulty, the difficulty of 128 bit RSA being rather different to 128 bit
AES.

On Wed, Jul 6, 2011 at 5:17 PM, Olafur Gudmundsson <[email-masked]> wrote:

> http://www.ietf.org/internet-**drafts/draft-ietf-dnsext-**ecdsa-01.txt<http://www.ietf.org/internet-drafts/draft-ietf-dnsext-ecdsa-01.txt>
> ______________________________**_________________
> dnsext mailing list
> [email-masked]
> https://www.ietf.org/mailman/**listinfo/dnsext<https://www.ietf.org/mailman/listinfo/dnsext>
>

-- 
Website: http://hallambaker.com/
_______________________________________________
dnsext mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/dnsext

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 7 Jul 2011 17:47:21 -0700

> This should be 'Work Factor'

Sounds fine.

--Paul Hoffman

---

From: "John Levine" <[email-masked]>
Date: 8 Jul 2011 01:37:02 -0000

>it comes to understanding crypto, at least as far as it's role in 

I'd rather keep the documents that describe the bits on the wire
separate from the documents that opine about how one should choose
what bits to send.  The former should be highly stable, the latter can
evolve somewhat as we understand better what the deployment issues
are.

It's not exactly a BCP, since I gather there isn't a whole lot of
practice with new algs in DNSSEC.  It's more of a BHP or BPP
(Hypothetical or Proposed).

R's,
John

---

From: Matthijs Mekking <[email-masked]>
Date: Fri, 08 Jul 2011 08:30:41 +0200

I have read this document and have no further comments.

Best regards,
  Matthijs

---

From: bert hubert <[email-masked]>
Date: Fri, 8 Jul 2011 12:56:40 +0200

> Remember that we need a minimum of 5 reviewers.

I have read this document and also the other reviews. I think this
document should go ahead, with two clarifications, one of which is
new.
The first clarification is moving up the definition of ECDSA, but this
has been noted already and Paul is going to fix it.

The second one is that the document describes a signature as 'r|s'. In
such cases, an implementor is always left wondering where r ends and s
begins. In the case of 'r' and 's' both needing their full amount of
bits, this is easy - the '|' goes exactly down the middle.

But it is possible that either r or s fits in one octet less (or more
even!). The same goes for x and y.

It is helpful therefore to add a sentence that r and s are both
left-padded to their full length or, alternatively, that r and s
occupy the same number of octets in an answer (and the same goes for x
and y).

PowerDNS already includes support for ECDSA in the 3.0 prereleases,
and we use the 'cut down the middle' rule.
http://wiki.powerdns.com/trac/browser/trunk/pdns/pdns/cryptoppsigners.cc#L119

But I'd love to see some text that makes it official. A suggestion
might be as the new third paragraph of section 4:
"Implementations will ensure that when concatenating the halves of a
coordinate, each half takes up the same amount of octets, allowing for
the unambiguous reconstruction of the coordinate on reception".

   Bert

---

From: Scott Rose <[email-masked]>
Date: Fri, 8 Jul 2011 08:26:35 -0400

I have read the draft and have no additional comments.  I support it going forward.

Scott

---

From: Rene Struik <[email-masked]>
Date: Thu, 21 Jul 2011 19:01:07 -0400

Dear colleagues:

Please find below my editorial and technical comments on draft-ietf-dnsext-ecdsa-01.

Best regards, Rene

==

Summary of the draft:
The draft specifies two two elliptic curve signature algorithms for use with DNSSEC that were heretoforth not defined,
viz. ECDSA with suite B curves and hash functions at 128-bit and 192-bit crypto bit strength). As pointed out, the main 
rationale for doing so are that use of ECDSA and ECDSA public keys (a) allows smaller size data fields; (b) may allow
computational savings; (c) introduces algorithms with crypto primitives of equivalent cryptographic bit strength.

==

Summary of comments:

1) Editorial:
The draft would benefit from tightening up some of the language, especially since this may lower the chance of confusing 
noncryptographic people.

2) Technical:
The draft results in data fields of size 4n octets, where n is the octet-length of the underlying curve. In fact, one can 
do better and use data fields of size 3n octets, without loss of functionality.

==

Detailed comments:

--

I. Editorial and semi-editorial comments:

(E-a) p.2, Clause 1, first para: 
With RSA, "key" should read "modulus" (e.g., "using 1024 or 2048 bit moduli"). The same remark applies to interchanges 
of keys and moduli with RSA, e.g., third para ("3072-bit keys").

(E-b) p.2, Clause 1, second para:
I suggest adding the following references: 
(1) for P-256 and P-384, xref FIPS Pub 186-3; 
(2) for ECDSA, xref FIPS Pub 186-3 (esp. necessary, so as to specify how to map hash output (bit string) to an integer in Zn); 
(3) SHA-256 and SHA-384, xref FIPS Pub 180-3.
{Note RS: With the availability of RFC 6090 "Fundamentals of ECC", should one refer that RFC as well, besides FIPS Pub 186-3?}

(E-c) p.2, Clause 1, second para:
Replace DS RR by delegating signer resource record (DS RR).

(E-d) p.2, Clause 1, third para:
This para suggests that public keys on the curve P-256 have size 256 bits, but this conflicts the representation in Clause 4, 
first para, where their (affine) representation is 512 bits.
{BTW - I strongly suggest using "octet" units, rather than "bits", since this seems to better align with other crypto-related 
IETF documents, and non-IETF documents (ANSI, SECG, etc.).}

(E-e) p.2, Clause 1, third para:
This para attemts to quantify comparisons of the size of RSA and ECDSA public keys, but does omit this for RSA signatures and ECDSA
signatures. Suggest to correct (for 128-bit crypto bit strength).

(E-f) p.2, Clause 1, fourth para, l.2:
The term "matching" is somewhat unfortunate: why not state that the curve and the hash function are picked with the same cryptographic
bit design strength?

(E-g) p.2, Clause 1, fourth para, l.6:
Unkeyed hash functions do not have a key, so please replace "...is half the length of the key" by "... is half the output size (in bits)".
{Note RS: please note the "(in bits)" phrase, which should also be added to the corresponding statement on cryptographic bit strength for 
public keys (cf. same para, l.4-5: change to "...is half the bit-length of the key"). 

(E-h) p.2, Clause 1, fourth para, l.6:
Replace "using matched strength" by "using the same cryptographic bit strength".

(E-i) p.2, Clause 1, fourth para, l.7:
The notion of "weaker half" of a signature algorithm is somewhat confusing, since, e.g., with ECDSA, while the strength is not entirely 
proven (to my knowledge), it depends on at least three factors, including (1) underlying hash function; (2) underlying ECDHP; 
(3) ECDSA peculiarities. Changing "choosing the weaker half of" by "choosing the weaker cryptographic primitive [or: component] of the 
signature algorithm.

(E-j) p.2, Clause 1, fourth para, l.7-10:
The RSA example would be clearer if one would state that RSA with 2048 modulus is believed to have 112 bit cryptographic bit strength,
since then the discussion about equivalent bit strength becomes simply an exercise in comparing this with the presumed strength of
SHA-256 (half the output size or 128-256/2).

(E-k) p.2, Clause 1, fifth para:
Performance of cryptographic operations is highly platform-dependent, so absolute numbers should be avoided at almost all cost. Moreover, it
is (of course) dependent on the crypto primitive in question -- something that is not mentioned (e.g., is the factor 5x computational advantage
ECDSA signing compared to RSA signing for P-256 vs. RSA-3072, or for something else?). I would suggest to replace "Signing with ECDSA is" by 
"signing with ECDSA may be" and adopt the corresponding absolute language for the verification numbers accordingly as well. Moreover, please 
pick a curve for which these numbers apply. 
{Note RS: as a side note: to illustrate that one has to be careful here, please cf. to Slide 48 of
http://www.ietf.org/proceedings/78/slides/saag-7.pdf, which suggests that for some platforms, both signing and verification for ECDSA is faster
than with RSA (and not just signing, as in this draft).}

(E-l) p.3, Clause 1, sixth para, l.4:
Perhaps, replace "is copied liberally from" by "borrows heavily from"?

(E-m) p.3, Clause 2, l.2:
Replace "the implementation of SHA-384 in DNSSEC" by "the use of SHA-256 in DNSSEC" (after all, now it seems one discusses the implementations 
of SHA-256 and SHA-384 themselves [at least, to me, as nonnative speaker]).

(E-n) p.3, Clause 3:
This clause discusses the need for corresponding parties to have access to the same system-wide parameters, in casu for ECDSA. 
However, the remainder of this clause only talks about the elliptic curve domain parameters (P-256, resp. P-384), but does not mention the 
hash function (SHA-x, etc.) underlying ECDSA, the encoding rules (bit/octet order, etc.) for messages to be signed, etc. This is confusing.

(E-o) p.3, Clause 4, first para:
The x- and y-coordinates of public key Q should be properly introduced. Of course, crypto people know that this corresponds to the affine
representation of points on the corresponding prime curve, but this should be left less as guess work.
In fact, I would strongly urge to use the same representation convention for public keys as used elsewhere, such as, e.g., wiht RFC 3279 
(Clause 2.3.5, ECPoint), with ANSI X9.62-1999 (4.3.6), or with SEC1 or RFC5480. This format nicely allows unique representation of the point
of infinity (0x00), affine points (0x04 | x | y), and compressed points (PC=0x02 or 0x03 | x). Thus, one can represent Q as (0x04 | x | y).

(E-p) p.3, Clause 4, second para:
The signature components r and s are integers, but r | s is an octet string. Please add the following text a the end of the paragraph:
"where "r" and "s" are represented each as octet string, with size the octet size of the (prime) order of the underlying prime curve.

(E-q) p.4, Clause 4, third para:
The two bulletized items should also refer to the underlying ECDSA specification (FIPS Pub 186-3) as well.

(E-r) p.4, Clause 4, fourth para, l.1:
It seems that one cannot state "MUST support" and then offer an "and/or" option. Suggest to change this to support for both signing *and* 
verification (so as to avoid ambiguities here).

(E-s) p.4, Clause 5, second para, l.3:
Not sure why one would not just refer to SHA-1 (which is Algorithm 1, as defined in Clause 11 of RFC 5155). If one somehow does not wish
to admit to using SHA-1, it would really help to add clause numbers, so as to help the reader find all this (some IETF specifications are 
extremely large and making life easier should be explicit goal of writing).

(E-t) p.4, Clause 6, second para:
The picks for TBA-1, TBA-2, and TBA-3 are really obscure; this is much clearer once one disects the examples in Clause 6.1 ff. Also here, 
why not make life easier on the reader and change the last sentence to "The examples use the following algorithm codes:
Code 4 for ECDSAP256SHA256 (TBA-1), ...", etc?

(E-u) p.6, Clause 8, l.2:
Again, please change "half the size of the key" to "half the bit-size of the underlying curve". (Considering the pick in Clause 4 for Q, half 
of the key would be the bit-size of the curve, rather than half the bit-size).

(E-v) pp.3-4, Clause 4 (or, perhaps, more general remark):
Currently, the clause does not make for easy reading, since it just defines the signature format and the public key format and does not
even hint at the clauses in the corresponding base line documentation (RFC 4033,4034, 4035) where all this "falls into place".
I would strongly suggest adding more clues, so as to make this for less esoteric reading. Why not include some text that captures the following
(here, mentioned for 128-bit crypto strength):
The DNSKEY Resource Record is defined in RFC 4034, Clause 2.1.
-the algorithm field (RFC4034, 2.1.3) is set to ECDSAP256SHA256 {TBA-1};
-the public key is set to the representation for the public key introduced in Clause 4;
etc.
Note RS: RFC 4034 already includes Algorithm Type 4 for ECC (cf. Annex A.1), but currently this is undefined.

--

II. Technical comments:

(T-a) p.3, Clause 4, first para:
In this para, the ECDSA signature is 2n octet field, as is the public key Q, where n is the octet size of the order of the underlying curve.
Since the size of the public key Q is important (cf., also Clause 1, third para, last sentence), why not be somewhat more economical here and
represent Q by its x-coordinate only? This does not seem to lead to any loss of functionality, whereas shaving off 25% of the data field 
overhead, from 4n octets to 3n octets. Some details follow:

Underlying motivation:
(1) The point of sending the public key Q along seems to be that one has an identifier for the public signature verification key that one also has
in a white list on the verifier's machine? (If one does not have a white list check on the verifier, the authentication procedure is completely
broken, since then anyone can produce valid signatures.) This assertion seems to be validated by Clause 5.3.1 of RFC 4035 (which discusses 
authentication).
(2) To identify a public key Q residing on a verifier's machine, one does not need the entire public key; the x-coordinate suffices: after all,
no two public signature verification keys belonging to valid signers will have the same x-coordinate (for otherwise, one knows the private key 
of the other).

Suggested improvement:
The above assertions lead to the following 33% size improvement, with following (very modest) changes required:

1) Signing side:
-Clause 4, first para:
Represent the public key Q by its x-coordinate, rather than by the pair x-coordinate and y-coordinate (here, we denote the result by Q');
-Data to be signed: hash data with Q' included, rather than Q (this has no security implications at all, as one can easily see).

2) When verifying an ECDSA signature, "decompress" first:
- Use Q' as index to recover the key Q at verifier's machine;
- Use Q to veerify the ECDSA signature by computing R'=(1/s) (eG +rQ), where e= h(m,Q') and checking that f(R')=r (mathematical short-cut 
notation for ECDSA signature verification).

Final notes RS:
1) If one wishes, one could send either Q'=x-coordinate of Q or Q itself (in case one somehow feels that one needs options (should not be 
necessary, though)). In that case, the "normal" representation of elliptic curve points -- affine representation of Q = (0x04, x, y); new 
x-coordinate only representation Q' = (0x01, x) would do. This does (a) not conflict any ECPoint representations already in use; (b) this does 
allow different representations of the public key in the DNSKEY RR (RFC 4034, Clause 2.1.4), so doing away with need to define new algorithm id 
(RFC 4034, Clause 2.1.3).
2) RFC 4035, Clause 5.1.3 (authentication procedure) already caters for the scenario that one may have "more than one match", so - if one really 
wishes one could compute both Q and -Q from Q' (i.e., compute both (x,y) and (x,-y) given x-coordinate Q') and run the authentication algorithm 
as already specified. 
2) Security is exactly the same as with original construct.
3) There are no nontechnical considerations to be concerned about (note that Q' does not provide any insight on the y-coordinate of Q).

Best regards, Rene

-- 
email: [email-masked]
Skype: rstruik
cell: +1 (647) 867-5658
USA Google voice: +1 (415) 690-7363