Subject: Re: Last Call: <draft-herzog-static-ecdh-04.txt> (Use of static-static Elliptic-Curve Diffie-Hellman key agreement in Cryptographic Message Syntax) to Informational RFC

From: Rene Struik <[email-masked]>
Date: Wed, 02 Mar 2011 22:03:33 -0500

Dear colleagues:

Please find below my (modest) comments on draft-herzog-static-ecdh-05 (an update of the document that occurred since the moment 
of issuing the LC).

Best regards, Rene

==

I. Editorial comments:

(E-a) p. 1, Disclaimer, l. 3: "conclusions and" should read "conclusions, and".
(E-b) p. 11, Clause 7, l. -2: "Consder" should read "Consider".
(E-c) p. 12, Clause 7, last para before two bullet points, l. 3: "reciever" should read "receiver".
(E-d) p. 13, Clause 10.2, l. -3: The paper by Menezes and Ustaoglu has appeared in International Journal of Applied Cryptography, 
Vol. 2, No. 2, pp. 154-158, 2010.
(E-e) p. 4, l. -5: The motivation for specifying ECDH seems to be not so much that ECMQV is around (but having problems, as you stated), 
but that static-static-ECDH is *not* around. Thus, specifying static-static-ECDH adds more options to the solution space.

II. Technical comments:

(T-f) p. 5, Clause 1, forelast bullet: The term "data integrity" is more aptly called "data authenticity" (and would also align well with 
AuthenticatedData CMS structure called out at the beginning of the same sentence). NOTE - I am aware of the "attack in Clause 7, but this 
attack seems to be more a flaw in the original CMS scheme, since effective irrespective of the key agreement method (i.e., not just static-
static-ECDH): A --> B: E_K(k) || Secured_k(m) allows any entity C who obtains the same key k to replace Secured_k(m) by another valid 
string. This suggests that (1) one should call this out in the text; (2) one should fix the original problem with CMS (e.g., tieing k to K, the
originator, or recipient via, e.g., a one-way function.

(T-g) p. 6, Clause 2.2, l. -5: At first, it is suggested that the sending agent obtains the recipient's public key somehow (e.g., from its 
certificate), thus suggesting that certificates are not the only option by which the public key may be obtained. However, later on it is stated 
that "it confirms that both certificates [...]", thus suggesting that each of the parties involved in this message flow have public keys that
are certified and that only those can be used. This is confusing.

(T-h) p. 6, Clause 2.2, l. -6 ff: Given the lack of shall/should/may language, it is unclear whether one stipulates that one
checks that public keys in the certificate are on a specific curve (i.e., one does public key validation) or something more relaxed (such as checking
that the claimed elliptic curve domain parameters are the same, without checking the public keys themselves. The para would benefit from some 
firmed-up language here. This should also clarify whether one, in fact, checks the validity of the certificate that included the public key.

(T-i) p. 7, Clause 2.3, l. 8 ff: same comment as T-h, but now for recipient's side.

(T-j) p. 11, Clause 6, l. 4 (also l. 16): I was hoping that by now (2011), the unkeyed hash function SHA-1 would be moth-balled (rather than 
reintroducing this option), more than 5 years after more serious SHA-1 attacks were presented in the academic community.
 
(T-k) p. 11, Clause 6, l. 3 (also l. 15): Why not introduce the CTR encryption mode as an option, at least when authenticity is provided? 
After all, CTR mode allows implementation of block-ciphers with just the forward encryption mode and offers parallelization and precomputation 
prospects.

(T-l) General: When static-static ECDH, as specified here, stipulates checking of the certificate including the public key and that certificate is
an ECDSA certificate, significant speed-ups of the computations are possible by combining the key computation step and ECDSA signature verification
-- cf. http://www.ietf.org/proceedings/78/slides/saag-7.pdf. <http://www.ietf.org/proceedings/78/slides/saag-7.pdf> or the SAC 2010 paper referenced in that IETF-78 presentation. These results also apply here
(and can obviously be ignored or embraced depending upon implementation). I would suggest adding a one-line statement that if ECDSA is used, one shall 
use the "friendly ECDSA" scheme as in the IETF-78 presentation (which has the same format as the ordinary one).

Rene

<http://www.inderscience.com/browse/index.php?journalID=233&year=2010&vol=2&issue=2>
On 02/02/2011 4:55 PM, The IESG wrote:
> The IESG has received a request from an individual submitter to consider
> the following document:
> - 'Use of static-static Elliptic-Curve Diffie-Hellman key agreement in
>    Cryptographic Message Syntax'
>   <draft-herzog-static-ecdh-04.txt> as an Informational RFC
>
> The IESG plans to make a decision in the next few weeks, and solicits
> final comments on this action. Please send substantive comments to the
> [email-masked] mailing lists by 2011-03-02. Exceptionally, comments may be
> sent to [email-masked] instead. In either case, please retain the
> beginning of the Subject line to allow automated sorting.
>
> The file can be obtained via
> http://datatracker.ietf.org/doc/draft-herzog-static-ecdh/
>
> IESG discussion can be tracked via
> http://datatracker.ietf.org/doc/draft-herzog-static-ecdh/
>
>
>
> No IPR declarations have been submitted directly on this I-D.
> _______________________________________________
> IETF-Announce mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ietf-announce

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

---

From: "Herzog, Jonathan - 0668 - MITLL" <[email-masked]>
Date: Mon, 7 Mar 2011 13:51:54 -0500

On Mar 3, 2011, at 12:37 PM, Russ Housley wrote:

> 
> 
> Begin forwarded message:
> 
>> From: Rene Struik <[email-masked]>
>> Date: March 2, 2011 10:03:33 PM EST
>> To: [email-masked]
>> Subject: Re: Last Call: <draft-herzog-static-ecdh-04.txt> (Use of static-static Elliptic-Curve Diffie-Hellman key agreement in Cryptographic Message Syntax) to Informational RFC
>> 
>> Dear colleagues:

Thanks for the comments. I've read through them, and plan to incorporate them into a -06 version in the next few days. Before I do, however, do you mind if I explain what I did and ask a few questions?

>> (E-a) p. 1, Disclaimer, l. 3: "conclusions and" should read "conclusions, and".

I don't disagree, but the Disclaimer is a magic incantation we need to include verbatim in each of our documents. I cannot change it without invoking the wrath of our legal department, so I hope you'll kindly look the other way it if I leave it the way it is?

>> (E-c) p. 12, Clause 7, last para before two bullet points, l. 3: "reciever" should read "receiver".

Whoops. Thanks for catching these.

>> Vol. 2, No. 2, pp. 154-158, 2010.

That's great news. Thanks for mentioning this. (Reference updated.)

>> but that static-static-ECDH is *not* 
>> around. Thus, specifying static-static-ECDH adds more options to the solution space.

I'm not sure how to interpret this. Is this just a general comment, or are you suggesting some change to the draft? if the later, can you say a little more about the change you would like to see?

>> AuthenticatedData CMS structure called out at the beginning of the same sentence).

We will change 'Data integrity' to 'data authenticity'.

>> NOTE - I am aware of the "attack in Clause 7, but this 

I can call it out in the text, and will do so, but fixing the problem in CMS is a little beyond the scope of this Draft. We hope to address it a separate Draft (forthcoming).

>> are certified and that only those can be used. This is confusing.

The intention is that both sender and receiver must have certified public keys. From the abstract:

   In this form of key-agreement, the Diffie-Hellman values of both
   sender and receiver are long-term values contained in certificates.

Also, the fact that both sender and receiver must have certificates is implicit in Section 2.1:

   o  originator identifies the static EC public key of the sender.  It
      MUST be either issuerAndSerialNumber or subjectKeyIdentifier, and
      point to one of the sending agent's certificates.

...

   o  recipientEncryptedKeys contains an identifier and an encrypted CEK
      for each recipient.  The RecipientEncryptedKey
      KeyAgreeRecipientIdentifier MUST contain either the
      issuerAndSerialNumber identifying the recipient's certificate or
      the RecipientKeyIdentifier containing the subject key identifier
      from the recipient's certificate.

But you are right: the use of 'e.g.' is a bit confusing. To resolve this confusion, I propose to change Section 2.2 from

   When using static-static ECDH with EnvelopedData, the sending agent
   first obtains the recipient's EC public key and domain parameters
   (e.g. from the recipient's certificate). 

to
 
          When using static-static ECDH with EnvelopedData, the
	  sending agent first obtains the EC public key(s) and domain
	  parameters contained in the recipient's certificate.

and Section 2.3 from 

   The receiver then retrieves the static EC public key identified in
   the rid field.

to

	  The receiver then retrieves the sender's certificate
	  identified in the rid field.

Do you think that these two changes would resolve the confusion?

>> firmed-up language here. This should also clarify whether one, in fact, checks the validity of the certificate that included the public key

Good points. The language of this draft was based on that in Section 3.1.2 of RFC 3278, but it could be firmed up. 

With regard to parameter validation, SEC1 (Section 3.2.2) lists a few methods by which a public-key can be checked for valid parameters:

* Full check,
* Partial check, and
* Trust the CA. 

(I'm paraphrasing a bit.) Since RFC 5480 doesn't provide any way for the CA to mark the parameters as 'checked' or 'not checked', I'll have our Draft say that the sender and receiver:

* SHOULD do a full parameter check for standard ECDH, and
* SHOULD do a full check for co-factor ECDH, or failing that, SHOULD do a partial check (as seems to be permitted in SEC1, Section 3.2.3).

(By the way, do you know if these validation checks exist in a RFC anywhere? I couldn't find them in RFC 6090...)

As for certificate validation: I'd prefer to remain silent on the issue. That is, I'd prefer to focus entirely on how to use the values found in the certificate. Issues regarding when, how often, and how to validate the certificate seem like much larger issues and out of scope. Thoughts?

But given the above, I've changed the language as follows:

Was:

   When using static-static ECDH with EnvelopedData, the sending agent...
   confirms that both
   certificates contain public-key values with the same curve
   parameters, and that both of these public-key values are marked as
   appropriate for ECDH (that is, marked with algorithm-identifiers id-
   ecPublicKey or id-ecDH [PKI-ECC]).  The sender then determines:

   o  whether to use standard or cofactor Diffie-Hellman, and

   o  which hash algorithms to use for the key-derivation function...

IS NOW

   When using static-static ECDH with EnvelopedData, the sending agent...  
   MUST confirm the following at least
   once per recipient-certificate:

   o  That both certificates (the recipient's certificate and its own)
      contain public-key values with the same curve parameters, and

   o  That both of these public-key values are marked as appropriate for
      ECDH (that is, marked with algorithm-identifiers id-ecPublicKey or
      id-ecDH [RFC5480]).

   The sender then determines whether to use standard or cofactor
   Diffie-Hellman.  After doing so, the sender SHOULD validate the
   receiver's public-key parameters at least once per public key:

   o  If standard Diffie-Hellman is to be used, the sender SHOULD use
      the Elliptic Curve Public Key Validation Primitive found in
      Section 3.2.2.1 of [SEC1].

   o  If cofactor Diffie-Hellman is to be used, the sender SHOULD use
      the Elliptic Curve Public Key Validation Primitive found in
      Section 3.2.2.1 of [SEC1].  If the sender chooses not to apply
      this primitive (for performance reasons, perhaps) then it SHOULD
      apply the Elliptic Curve Public Key Partial Validation Primitive
      found in Section 3.2.3.1 of [SEC1].

   The sender then determines which hash algorithms to use for the key-
   derivation function...

>> (T-i) p. 7, Clause 2.3, l. 8 ff: same comment as T-h, but now for recipient's side.

WAS:

   When using static-static ECDH with EnvelopedData, the receiving agent
   retrieves keyEncryptionAlgorithm to determine the key-agreement
   algorithm chosen by the sender, which will identify:

   o  the domain-parameters of the curve used,

   o  whether standard or cofactor Diffie-Hellman was used, and

   o  which hash-function was used for the KDF.

   The receiver then retrieves the static EC public key identified in
   the rid field.  It confirms that both certificates contain public-key
   values associated with the curve identified by the
   keyEncryptionAlgorithm, and that both of these public-key values are
   marked as appropriate for ECDH (that is, marked with algorithm-
   identifiers id-ecPublicKey or id-ecDH [PKI-ECC]).  The receiver then
   determines a bit string "SharedInfo", which is the DER encoding of
   ECC-CMS-SharedInfo (see Section 7.2 of [CMS-ECC]) and performs the
   key agreement operation of the Elliptic Curve Diffie-Hellman Scheme
   specified in [SEC1]; in either case, use the KDF defined in Section
   3.6.1 of [SEC1].  As a result, the receiving agent obtains a shared
   secret bit string "K", which it uses as the pairwise key-encryption
   key to unwrap the CEK.

IS NOW:

   When using static-static ECDH with EnvelopedData, the receiving agent
   retrieves keyEncryptionAlgorithm to determine the key-agreement
   algorithm chosen by the sender, which will identify:

   o  the domain-parameters of the curve used,

   o  whether standard or cofactor Diffie-Hellman was used, and

   o  which hash-function was used for the KDF.

   The receiver then retrieves the sender's certificate identified in
   the rid field.  It MUST confirm the following at least once per
   sender-certificate:

   o  That both certificates (the sender's certificate and its own)
      contain public-key values with the same curve parameters, and

   o  That both of these public-key values are marked as appropriate for
      ECDH (that is, marked with algorithm-identifiers id-ecPublicKey or
      id-ecDH [RFC5480]).

   The receiver then determines whether standard or cofactor Diffie-
   Hellman was used.  After doing so, the receiver SHOULD validate the
   sender's public-key paramaters at least once per public key:

   o  If standard Diffie-Hellman is to be used: The receiver SHOULD use
      the Elliptic Curve Public Key Validation Primitive found in
      Section 3.2.2.1 of [SEC1].

   o  If cofactor Diffie-Hellman is to be used: The receiver SHOULD use
      the Elliptic Curve Public Key Validation Primitive found in
      Section 3.2.2.1 of [SEC1].  If the receiver chooses not to apply
      this primitive (for performance reasons, perhaps) then it SHOULD
      apply the Elliptic Curve Public Key Partial Validation Primitive
      found in Section 3.2.3.1 of [SEC1].

   The receiver then determines a bit string "SharedInfo", which is the
   DER encoding of ECC-CMS-SharedInfo (see Section 7.2 of [RFC5753]) and
   performs the key agreement operation of the Elliptic Curve Diffie-
   Hellman Scheme specified in [SEC1]; in either case, use the KDF
   defined in Section 3.6.1 of [SEC1].  As a result, the receiving agent
   obtains a shared secret bit string "K", which it uses as the pairwise
   key-encryption key to unwrap the CEK.

>> reintroducing this option), more than 5 years after more serious SHA-1 attacks were presented in the academic community.

Fair enough. Shall I say that implementations SHOULD NOT support the SHA-1 schemes?

Along those same lines, I will also change the DES algorithms to SHOULD NOT.

>> After all, CTR mode allows implementation of block-ciphers with just the forward encryption mode and offers parallelization and precomputation 

I left it out because I have serious reservations about the security of counter mode. But in looking in to your question, I see there's an even-more serious problem: I can't find an RFC for AES-in-counter-mode for CMS. Perhaps, though, my Google-foo is insufficient. Do you have a pointer to an appropriate RFC?

(But your question did spur me to add AES in CCM and GCM as optional algorithms.)

>> -- cf. 
>> http://www.ietf.org/proceedings/78/slides/saag-7.pdf.
>>  or the SAC 2010 paper referenced in that IETF-78 presentation. These results also apply here

That seems like an impressive speed-up, but is this really the right document for the SHALL you recommend? If I read your mail correctly (which I admit may not be the case) it sounds like your proposed SHALL is binding on the CA which issued either the sender's certificate or the receiver's certificate. If this is the case, I worry that it would be out of place in this draft, which (as written now) only becomes relevant after certificates are issued.

Or am I reading this incorrectly?

Thanks.

-- 
Jonathan Herzog							voice:  (781) 981-2356
Technical Staff							fax:    (781) 981-7687
Cyber Systems and Technology Group		email:  [email-masked]
MIT Lincoln Laboratory               			www:    http://www.ll.mit.edu/CST/
244 Wood Street    
Lexington, MA 02420-9185

---

From: "Herzog, Jonathan - 0668 - MITLL" <[email-masked]>
Date: Thu, 10 Mar 2011 17:50:45 -0500

Just to keep everyone informed: Dr. Struik and I spoke by phone earlier today about his comments. My recollection of the conversation is that he accepted most of the comments as resolved, modulo the following additional details:

(And Dr. Struik! One of our agreements has been overtaken by events! Please see below.)

> I'm not sure how to interpret this. Is this just a general comment, or are you suggesting some change to the draft? if the later, can you say a little more about the change you would like to see?

This comment got folded into another comment about our motivation. The new version dispenses with motivations (1) and (3), focusing on the fact that ECMQV is no longer in Suite B. Therefore, some participants will not be able to use ECMQV for policy reasons, and may also be unable to sign their messages for lack of a certified signature key. This Draft presents static-static ECDH as an alternative mechanism for achieving source authentication if they should happen to have a certified ECDH key.

> 	  identified in the rid field.

This last sentence now reads:

   The receiver then retrieves the sender's certificate identified in
   the rid field, and extracts the EC public key(s) and domain
   parameters contained therein. 

> * SHOULD do a full check for co-factor ECDH, or failing that, SHOULD do a partial check (as seems to be permitted in SEC1, Section 3.2.3).

***** Dr. Struik! This has been overtaken by events! ************

Due to IPR concerns, I have removed these checks from the draft. The relevant sections now read:

Section 2.2:

   When using static-static ECDH with EnvelopedData, the sending agent
   first obtains the EC public key(s) and domain parameters contained in
   the recipient's certificate.  It MUST confirm the following at least
   once per recipient-certificate:

Section 2.3:

   The receiver then retrieves the sender's certificate identified in
   the rid field, and extracts the EC public key(s) and domain
   parameters contained therein.  It MUST confirm the following at least
   once per sender-certificate:

> I left it out because I have serious reservations about the security of counter mode. But in looking in to your question, I see there's an even-more serious problem: I can't find an RFC for AES-in-…

Neither Dr. Struik nor I could find OIDs for AES in counter mode, and so they remain absent from the Draft.

>>> use the "friendly ECDSA" scheme as in the IETF-78 presentation (which has the same format as the ordinary one).

I told Dr. Struik that I preferred to leave this out of the draft, and he (I believe) agreed.

Thanks all.

---

From: Rene Struik <[email-masked]>
Date: Fri, 11 Mar 2011 19:10:17 -0500

Dear Jonathan:

Thanks for our phone call yesterday afternoon (Thu March 10th) and your
summary below.

Please see my further comments below on your feedback on my review
comments (T-h), (T-i), (T-k), and (T-l),
a) where you labelled (T-h) and (T-i) as "overtaken by events";
b) where (T-k) refers to CTR mode;
c) where (T-l) refers to speed-up support.

I have some security concerns re #a, a question re #b, and a remark re
#c. If lack of time, at least try and address the security concerns.

Please feel free to discuss.

Have a nice weekend (well, it probably already started).

Best regards, Rene

>       ECDH (that is, marked with algorithm-identifiers id-ecPublicKey or
RS>>
[First a disclaimer: I have no stake in the ground here, except
advocating good security practices]

Fair enough, as long as this does not make the security considerations
sections null and void.

However, I am a little bit puzzled here, since this does not seem to
address any of the ambiguities noted in my comment (T-h). After all,
the only change to the text of Section 2.2 of
draft-herzog-static-ecdh-05 you suggest seems to be to replace the phrase
"It confirms that" by "It MUST confirm the following at least once per
recipient-certificate", without any further changes.

This does *not* address, since it is entirely unclear whether
a) one checks that public keys in the certificate are on a specific
curve (i.e., one does public key validation)
or
b) something more relaxed (such as checking that the claimed elliptic
curve domain parameters are the same, without checking the public keys
themselves;
c) whether one, in fact, checks the validity of the certificate that
included the public key

Ad #c:
Without checking the validity of certificates (item #c) {by performing a
cryptographic signature verification operation at least once}, one might
as well do away with certificates altogether, since no implicit key
authentication assurances can be obtained.

Ad #b:
By just checking that the certificate has a substring indicating the
purported domain parameters of the other entity's public key (item #b),
one does not seem to have any assurance that that public key is, in
fact, indeed of the proper form, i.e., on the curve and a generator of
the prime order cyclic subgroup of the curve indicated by the domain
parameters (unless the CA did those checks and by issuing the cert
attests to this and one indeed verifies the certificate itself
cryptographically).

Ad #a:
Without checking whether the public keys exchanged by both entities in
the protocol are on the same curve, one opens oneself up to a plethora
of potential attacks (small subgroup attack, invalid point attack, etc.
-- all well-documented in the cryptographic literature and also
referenced in the Security Consideration section).

It would help if you could comment on the lingering ambiguities I noted
in my original comment T-h (elaborated upon above with #a, #b, and #c)
and which, unless I misunderstand, are not taken away by your suggested
resolution. Further, it would help if you could indicate whether the
intention is to publish the draft with sufficient safeguards so as not
to succumb to well-documented vulnerabilities.

<<RS

>       ECDH (that is, marked with algorithm-identifiers id-ecPublicKey or
RS>>
Same concern as with (T-h) above.
<<RS
> Neither Dr. Struik nor I could find OIDs for AES in counter mode, and so they remain absent from the Draft.
RS>>
Okay - if OIDs are the only "stairway to heaven".

Question:
Shouldn't we put together an I-D that specifies the CTR mode and on OID
for this??? It would be a shame not to have this available (or could we
refer to NIST SP 800-38A and does NIST have an OID for this???).
Any thoughts?

<<RS
> I told Dr. Struik that I preferred to leave this out of the draft, and he (I believe) agreed.
RS>>
We can indeed deal with fostering speed-ups separately (as long as this
is not pushed in a cob-webbed corner!). The interesting thing is that
implementers of the draft could still move towards these "Friendly
ECDSA" techniques, without violating the current draft, so the door is
not completely closed on that one.
<<RS

---

From: "Herzog, Jonathan - 0668 - MITLL" <[email-masked]>
Date: Mon, 14 Mar 2011 10:13:08 -0400

>> (And Dr. Struik! One of our agreements has been overtaken by events! Please see below.)

[snip]

> recipient-certificate", without any further changes.

I believe this is more-or-less correct.

> authentication assurances can be obtained.

This Draft does not forbid verification and validation of certificates. Like RFC 5753, it is merely silent on the issue. My personal opinion is that this is as it should be, as issues of certificate generation, distribution, validation and verification are out of scope of this Draft. 

> attests to this and one indeed verifies the certificate itself

While the CA may have performed these checks, it is not required by this document. (In fact, it can't be-- there is no field in the certificate by which the CA can indicate that such a check has been done.)

> referenced in the Security Consideration section).

I agree.

> to succumb to well-documented vulnerabilities.

The ambiguities remain. The Draft is silent on when and how the certificates are verified and validated, or when/how the public-key parameters of the ECC key are validated. The first is out of scope, and the second is hindered by IPR considerations. But again, I note that:

1) The draft does not *prohibit* validation of the public-key parameters, and
2) This Draft mirrors the RFC 5753 treatment of the same issues.

Yes, The Draft would be better (meaning that the described system would be more secure) if it mandated the validation of the public-key parameters. But my read of the landscape is that were that the case, the IPR considerations would derail approval of the Draft. So the question is this:  given that RFC 5753 also lacks these validation mandates, is the world less secure with this Draft augmenting RFC 5753, or with just RFC 5753 and without this draft?

[snip]

> refer to NIST SP 800-38A and does NIST have an OID for this???).

I couldn't find anything in SP 800-38A by searching on 'OID', 'ASN', or 'identifier'. 

It may be worthwhile to create OIDs for counter-mode, but that would be outside the scope of this Draft.

> not completely closed on that one.

In case you didn't see through other channels, we have submitted the -06 version of this draft. It's waiting for manual approval, so I attach it to this email for your perusal.

Thanks.