Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-07.txt

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 8 Feb 2019 19:05:23 +0000

Dear draft-irtf-cfrg-spake2 authors,

Please find below my review of this ID. My apologies that it has taken so long to produce. 

Happy to discuss the various points further, of course.

Cheers,

Kenny

----
Review of draft-irtf-cfrg-spake2-07
Kenny Paterson (CFRG co-chair)
8th February 2019

Summary:

I have reviewed this draft. I believe it is the basis for a good RFC, but some technical changes and rewriting are needed.

Detailed remarks:

page 2: "Let G be a group in which the Diffie-Hellman (DH) problem is hard of
   order p*h, with p a big prime and h a cofactor." 

-- Change to:
    "Let G be a group in which the computational Diffie-Hellman (CDH) problem is hard. Suppose G has order p*h where p is a large prime; h will be called the cofactor."
   
page 3: "as well as a generator G of the group" 

-- You've already used G for the group itself. "P" is traditional in the ECC setting.

page 3: "truncated and taken mod p" - it's unclear that you want to truncate AND take mod p. This depends on the output size of the hash function and on the size of p, I guess, and also on the extent to which you want the output distribution to be statistically smooth mod p. What do the proofs for SPAKE2 and SPAKE2+ require here?

page 3: ""hashing. [RFC8265]" 

-- Inconsistent on whether references are before or after punctuation (earlier on, they were before, here it is after).

page 3: "ph" and "p*h" - aim for consistency here and throughout.

page 3: "Higher-level protocols
   SHOULD prescribe a method for incorporating a "transcript" of the
   exchanged values and endpoint identity information into the shared
   secret.  One such approach would be to compute a K' as H(len(A) ||
   A || len(B) || B || len(S) || S || len(T) || T || len(K) || K ||
   len(w) || w) and use K' as the key."
   
-- I think this is the wrong approach. I think we (CFRG) should specify a complete PAKE protocol whose keys can safely be used by developers of various experience levels. Asking developers to remember to include transcript hashing and get it right (and inviting them to roll their own by providing one approach but not mandating it) feels like a bad decision to me. So I would argue for making the steps leading to K' as a mandatory part of the SPAKE2 specification here. I would, naturally, recommend the same conservative approach for SPAKE2+.

page 3: "We use the same setup as for SPAKE2,
   except that we have two secrets, w0 and w1, derived by hashing the
   password with the identities of the two participants."
 
-- Please be explicit about how w0, w1 are computed. It's important for later understanding why SPAKE2+ can be considered as being augmented. (In essence, we need a hash function H with two outputs mod p, and we set (w0,w1) = H(pw || A || B).)
   
page 3:  "B stores L=w1*g and w0." (In the context of SPAKE2+.)

-- What is g? Perhaps G, the generator?

-- Assuming g is the generator of G of order p*h, notice that this element L is not necessarily in the order p subgroup of G, since w1 (and w0) are not necessarily multiples of h. Later in the protocol, A computes V = w1(Y-w0*N) where Y should have been received from B. If Y is chosen adversarially, then V may also not be in the order p subgroup of G. This may not have any negative consequences for protocol security because of the manner in which key derivation is performed, with both Z and V being involved in key derivation and V not being exposed to an adversary impersonating B (this another reason to mandate how key derivation is done). But this sits uncomfortably with the following remark in the security considerations (page 7): 

	"It is not necessary to validate membership in the prime
   order subgroup: the multiplication by cofactors eliminates the
   potential for mebership [sic] in a small-order subgroup."

-- It's certainly hard for an attacker to arrange for V to be in the order h (small) subgroup, but it can arrange for V NOT to be in the prime-order subgroup, and L need not be either (without any adversarial behaviour) while the presentation of SPAKE2+ in [TDH] just assumes that everything is a priori in an order p group. How does this difference affect the security analysis? It seems that A performing a check that V is in the prime-order subgroup may be necessary in order to bring the protocol into line with what is assumed in [TDH]. Not doing this check has unknown (to me) consequences.
 
Page 4: "and transmits it to Alice." Replace "it" with "Y" and "Alice" with "A".

Page 4: Table of points for common groups 

-- This is a very useful feature of the ID, and I am glad it is included. I think it would be useful to also include explicit generators G as well. 

-- However, I think we should go even further and mandate that only the specified list of curves and (M,N) points should be permitted for use. There are 2 reasons:
1. (EC)DH parameter validation is quite difficult to do correctly and expensive. If we allow (say) the server to choose its (EC)DH parameters and send them to the client, then we open clients up to attack by parties impersonating the server and sending maliciously generated parameters. This is particularly acute for PAKEs, see: 
	Daniel Bleichenbacher: Breaking a Cryptographic Protocol with Pseudoprimes. Public Key Cryptography 2005: 9-15. 
		and
	Steven Galbraith, Jake Massimo and Kenneth G. Paterson: Safety in Numbers: On the Need for Robust Diffie-Hellman Parameter Validation. IACR eprint 2019/032 (https://eprint.iacr.org/2019/032 and PKC 2019, to appear).
	
2. Mandating a fixed set of curves and parameters (M,N) of known provenance (as per this ID) restricts the opportunities for malicious third parties to later promote the use of parameters for which the discrete logs of M and/or N to base G are known to those parties.

Page 6: "[RFC8032] appendix A" 

-- Change to "[RFC8032, Appendix A]".

Page 7: "A security proof of SPAKE2 for prime order groups is found in [REF]." 
 
 -- Does this proof transfer to the current setting of group of non-prime order via co-factor multiplication in the way its done here? Is that approach equivalent to insisting on subgroup membership checks everywhere? Does it matter for the proof that G here is a generator of a group of order p*h and not of order p? (The original SPAKE2 paper of Abdalla and Pointcheval just assumes everything is in a group of order p, including generator G, does not allow for co-factors, and does not mention group membership tests.)
 
Page 7: "SPAKE2+ appears in [TDH] along with a path to a proof that server
   compromise does not lead to password compromise under the DH
   assumption (though the corresponding model excludes precomputation
   attacks)."
 
 -- There is no fully written up proof in [TDH], and as a consequence, I am somewhat less excited about including SPAKE2+ in this ID, though it's augmented property is definitely a plus. There's also the issue (of potential significance for security) that the original protocol is presented purely in an "order p" setting, but here in a setting with co-factors; see remarks above concerning V and subgroups, etc.
   
Page 7: "as this is a one-round protocol" 

-- There are two protocols in this ID, and both are one-round.
 
Page 7:  "It is
   expected that a protocol using this key exchange mechanism will
   provide key confirmation separately if desired."

-- Let's add details of a key confirmation mechanism here, for completeness. 

Page 7: "In
   particular it is essential to verify that received points are valid
   compressions of points on an elliptic curve when using elliptic
   curves."
 
 -- Does compression apply in the same way to all the curve models for which parameters are given in the ID? 
 
Page 7: "the multiplication by cofactors eliminates the
   potential for mebership [sic] in a small-order subgroup." 
 
 -- Suggestion for replacement text:
    "the implicit multiplication by cofactors when generating x and y eliminates the
   potential for membership of X and Y in a small-order subgroup."
   
Page 7: "Ephemeral values MUST NOT be reused; such
   reuse permits dictionary attacks on the password."
   
-- This is the first and only use of the word "ephemeral" in the document. I suggest to replace this text with:
   "Values x and y MUST NOT be reused; such
   reuse permits dictionary attacks on the password."'
   
 Page 7: "As specified, the shared secret K is not suitable for direct use as a
   shared key.  It MUST be passed to a hash function along with the
   public values used to derive it and the identities of the
   participating parties in order to avoid attacks.  In protocols which
   do not perform this separately, the value denoted K' MUST be used
   instead of K."
   
-- See my earlier remarks concerning my preference for integrating this key derivation as part of the protocol itself.
   
[END OF REVIEW]

-----Original Message-----
From: Cfrg <[email-masked]> on behalf of "[email-masked]" <[email-masked]>
Reply-To: "[email-masked]" <[email-masked]>
Date: Monday, 5 November 2018 at 01:43
To: "[email-masked]" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-07.txt

    A New Internet-Draft is available from the on-line Internet-Drafts directories.
    This draft is a work item of the Crypto Forum RG of the IRTF.
    
            Title           : SPAKE2, a PAKE
            Authors         : Watson Ladd
                              Benjamin Kaduk
    	Filename        : draft-irtf-cfrg-spake2-07.txt
    	Pages           : 9
    	Date            : 2018-11-04
    
    Abstract:
       This document describes SPAKE2, a means for two parties that share a
       password to derive a strong shared key with no risk of disclosing the
       password.  This method is compatible with any group, is
       computationally efficient, and has a security proof.

    The IETF datatracker status page for this draft is:
    https://datatracker.ietf.org/doc/draft-irtf-cfrg-spake2/
    
    There are also htmlized versions available at:
    https://tools.ietf.org/html/draft-irtf-cfrg-spake2-07
    https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-spake2-07
    
    A diff from the previous version is available at:
    https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-spake2-07

    Please note that it may take a couple of minutes from the time of submission
    until the htmlized version and diff are available at tools.ietf.org.
    
    Internet-Drafts are also available by anonymous FTP at:
    ftp://ftp.ietf.org/internet-drafts/
    
    _______________________________________________
    Cfrg mailing list
    [email-masked]
    https://www.irtf.org/mailman/listinfo/cfrg