Re: [kitten] SPAKE preauth: generation of SPAKE2 secret input (proposed text)

Greg Hudson <ghudson@mit.edu> Tue, 19 May 2015 16:16 UTC

Return-Path: <ghudson@mit.edu>
X-Original-To: kitten@ietfa.amsl.com
Delivered-To: kitten@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7AAAF1ABD3A for <kitten@ietfa.amsl.com>; Tue, 19 May 2015 09:16:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.511
X-Spam-Level:
X-Spam-Status: No, score=-1.511 tagged_above=-999 required=5 tests=[BAYES_50=0.8, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 1tlZHQ1GesNJ for <kitten@ietfa.amsl.com>; Tue, 19 May 2015 09:16:49 -0700 (PDT)
Received: from dmz-mailsec-scanner-2.mit.edu (dmz-mailsec-scanner-2.mit.edu [18.9.25.13]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EB34F1AC444 for <kitten@ietf.org>; Tue, 19 May 2015 09:14:49 -0700 (PDT)
X-AuditID: 1209190d-f79676d000000da0-e2-555b6178df47
Received: from mailhub-auth-2.mit.edu ( [18.7.62.36]) (using TLS with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by dmz-mailsec-scanner-2.mit.edu (Symantec Messaging Gateway) with SMTP id BB.9E.03488.8716B555; Tue, 19 May 2015 12:14:48 -0400 (EDT)
Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) by mailhub-auth-2.mit.edu (8.13.8/8.9.2) with ESMTP id t4JGEmRg020597; Tue, 19 May 2015 12:14:48 -0400
Received: from [18.101.8.189] (vpn-18-101-8-189.mit.edu [18.101.8.189]) (authenticated bits=0) (User authenticated as ghudson@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.8/8.12.4) with ESMTP id t4JGEkhj030585 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NOT); Tue, 19 May 2015 12:14:47 -0400
Message-ID: <555B6176.2000906@mit.edu>
Date: Tue, 19 May 2015 12:14:46 -0400
From: Greg Hudson <ghudson@mit.edu>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version: 1.0
To: kitten@ietf.org
References: <x7dk2wd6355.fsf@equal-rites.mit.edu>
In-Reply-To: <x7dk2wd6355.fsf@equal-rites.mit.edu>
Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: 8bit
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFvrJIsWRmVeSWpSXmKPExsUixG6noluRGB1qsHOXicXRzatYLHo6T7I5 MHnsnHWX3WPJkp9MAUxRXDYpqTmZZalF+nYJXBl79zWyFTyRrPh6/xZLA+MH4S5GTg4JAROJ mT9OMULYYhIX7q1n62Lk4hASWMwkcexXBwuEs5FRovfnJUYI5wiTxL8XV5hAWngF1CRmn9nN BmKzCKhKHJrxhBnEZhNQlli/fysLiC0qECYx7fdzVoh6QYmTM5+AxUUEhCV2b30HVs8soC7R PO82WFxYIEJi8aXzYPOFBAwlWo/0g53HKWAksfT7cTaIej2JHdd/sULY8hLNW2czT2AUnIVk xSwkZbOQlC1gZF7FKJuSW6Wbm5iZU5yarFucnJiXl1qka6SXm1mil5pSuokRFMKckrw7GN8d VDrEKMDBqMTDG1kfFSrEmlhWXJl7iFGSg0lJlHdadHSoEF9SfkplRmJxRnxRaU5q8SFGCQ5m JRHeqVFAOd6UxMqq1KJ8mJQ0B4uSOO+mH3whQgLpiSWp2ampBalFMFkZDg4lCd4L8UCNgkWp 6akVaZk5JQhpJg5OkOE8QMPPg9TwFhck5hZnpkPkTzEqSonzWiYAJQRAEhmleXC9sBTzilEc 6BVhXiGQKh5geoLrfgU0mAlosMm2SJDBJYkIKakGxmsKZ9deP7A0THu/xnN9xTf+3MdL19wp 8WG4orVdcn6yRmVi+VkTXUkPxsiDJo2d+pOafeveLBDd0D7F7HrnhYm2h0q/iHV5tDKsMVuk 1z3rTMUC/Yd/9k3bvu3iCbZm3zOaGTrRP/vPHkxqMkzSEjpVxV1yLTr5kxY7r+WejQFbO65u nl04WYmlOCPRUIu5qDgRAJkXbZkMAwAA
Archived-At: <http://mailarchive.ietf.org/arch/msg/kitten/msb3hp33JG8Wpk4Qzn1Zy19aRBo>
Subject: Re: [kitten] SPAKE preauth: generation of SPAKE2 secret input (proposed text)
X-BeenThere: kitten@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Common Authentication Technologies - Next Generation <kitten.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/kitten>, <mailto:kitten-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/kitten/>
List-Post: <mailto:kitten@ietf.org>
List-Help: <mailto:kitten-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/kitten>, <mailto:kitten-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 19 May 2015 16:16:50 -0000

Based on the results of this discussion, here is the wording I came up
with for my pull request.  In the prerequisites section:

   Both KDCs and clients MUST implement one or more groups for which the
   discrete logarithm problem is hard, each with an corresponding object
   identifer.  Group object identifiers MUST refer to one of the
   following:

   o  One of the eight elliptic curves specified in [SEC2] section 2,
      using the corresponding object identifier from appendix A.2.1.

   o  A group with an unambiguous specification for representing group
      elements as octet strings, and an unambiguous specification for
      converting an octet string of a specific length into an integer
      for use as a scalar multiplier.

and then in a new section titled "SPAKE Parameters and Conversions":

   The SPAKE algorithm requires a shared secret input w to be used as a
   scalar multiplier (see [I-D.irtf-cfrg-spake2] section 2).  This value
   MUST be produced from the client principal's long-term key as
   follows:

   1.  Determine a scalar octet string input length for the chosen
       group.  For SEC 2 curves over a prime field F(p), this is
       ceil(log2(p)/8).  For other groups, this length is specified by
       the group.

   2.  Produce an octet string of the above length with PRF+(K,
       "SPAKEsecret"), where K is the long-term key and PRF+ is defined
       in [RFC6113] section 5.1.

   3.  If the chosen group is secp521r1, set the high seven bits of the
       first byte to 0 so that there are at most 521 significant bits in
       the octet string.

   4.  For SEC 2 curves, decode the octet string as a big-endian
       positive integer as specified in [SEC1] section 2.3.8.  For other
       groups, decode the octet string as specified by the group.

Salient points:

* SEC 2 curves over Fp (which include NIST P-256/P-384/P-521) get to use
existing OIDs with conversions specified in this draft, using SEC 1
encoding primitives.  Other groups need to use an OID which
unambiguously specifies the needed conversions.  I expect the
forthcoming CFRG curves to slot in here, although I'm not sure if they
plan to designate OIDs for their curves.

* Because the eight SEC 2 curves all have cofactor 1, we don't have to
worry about cofactors in the conversions we specify.  Except for
secp521r1, they all use primes close to a power of 2^8.

* The w values won't be uniformly distributed even if the long-term key
is.  But as Watson noted, SPAKE doesn't assume that w is uniformly
distributed.

* A small proportion of w values will be larger than the group order.
Implementations need to be able to handle these values correctly and
without side channels.  I will try to make a note of this in the
security considerations, and will try to make sure that there are test
vectors exercising this possibility.  OpenSSL contains P-256 and P-521
implementations which are supposed to be constant-time if the input
bignum doesn't contain more than 256 or 521 significant bits respectively.

* It's possible, though vanishingly unlikely, for w to be equal to 0 or
to the group order.  I believe all of the computations should work in
this case, so there is no need to reject those values.