[Cfrg] draft-irtf-cfrg-spake2 edwards25519 M/N values

Greg Hudson <ghudson@mit.edu> Thu, 30 November 2017 18:19 UTC

Return-Path: <ghudson@mit.edu>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 416CF1293D8 for <cfrg@ietfa.amsl.com>; Thu, 30 Nov 2017 10:19:22 -0800 (PST)
X-Quarantine-ID: <bCTBHa9NwsjQ>
X-Virus-Scanned: amavisd-new at amsl.com
X-Amavis-Alert: BANNED, message contains text/plain,.exe
X-Spam-Flag: NO
X-Spam-Score: -4.2
X-Spam-Status: No, score=-4.2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id bCTBHa9NwsjQ for <cfrg@ietfa.amsl.com>; Thu, 30 Nov 2017 10:19:20 -0800 (PST)
Received: from dmz-mailsec-scanner-1.mit.edu (dmz-mailsec-scanner-1.mit.edu []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 42E67127977 for <cfrg@ietf.org>; Thu, 30 Nov 2017 10:19:19 -0800 (PST)
X-AuditID: 1209190c-4afff70000004a55-6c-5a204ba5ea8c
Received: from mailhub-auth-2.mit.edu ( []) (using TLS with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by dmz-mailsec-scanner-1.mit.edu (Symantec Messaging Gateway) with SMTP id BE.A9.19029.5AB402A5; Thu, 30 Nov 2017 13:19:18 -0500 (EST)
Received: from outgoing.mit.edu (OUTGOING-AUTH-1.MIT.EDU []) by mailhub-auth-2.mit.edu (8.13.8/8.9.2) with ESMTP id vAUIJE0H000590 for <cfrg@ietf.org>; Thu, 30 Nov 2017 13:19:16 -0500
Received: from localhost (EQUAL-RITES.MIT.EDU []) (authenticated bits=0) (User authenticated as ghudson@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.8/8.12.4) with ESMTP id vAUIJD84030321 for <cfrg@ietf.org>; Thu, 30 Nov 2017 13:19:14 -0500
From: Greg Hudson <ghudson@mit.edu>
To: cfrg@ietf.org
Date: Thu, 30 Nov 2017 13:19:13 -0500
Message-ID: <x7dvahrvdcu.fsf@equal-rites.mit.edu>
MIME-Version: 1.0
Content-Type: text/plain
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFprLIsWRmVeSWpSXmKPExsUixG6norvMWyHK4MF9fouju9pYHBg9liz5 yRTAGMVlk5Kak1mWWqRvl8CVMeX5Z5aC+eIVl1oWszYwzhXsYuTkkBAwkWh5f5O9i5GLQ0hg MZPE6wmfWCCco4wSb/a/Z4Jw2pgk2m4+YQZpYRNQlli/fytQFQeHiICgRMcaGZCwsIC5xK/d 29hAbBYBVYkD9/tYQUp4BQwlni/OAgnzAlWfnPmEBcRmFpCQOPjiBfMERu5ZSFKzkKQWMDKt YpRNya3SzU3MzClOTdYtTk7My0st0jXUy80s0UtNKd3ECAoBTkmeHYxn3ngdYhTgYFTi4bUQ VIgSYk0sK67MPcQoycGkJMob6QUU4kvKT6nMSCzOiC8qzUktPsQowcGsJMKb4gSU401JrKxK LcqHSUlzsCiJ824L2hUpJJCeWJKanZpakFoEk5Xh4FCS4M0CGSpYlJqeWpGWmVOCkGbi4AQZ zgM0/LEHyPDigsTc4sx0iPwpRlWOZzNfNzALseTl56VKifPOAhkkAFKUUZoHN+cVozjQO8K8 X0GyPMA4h5vwCmg4E9DwzOXyIMNLEhFSUg2MrtKipTd/5DfcvK+aZf5hs1WNjcq5uCkbvvaZ L5rzUOki48WrG3Zcv9a+W0XR2n/RutWTvTmWJXzJOV1QvThcqD95Xuzi3Z9zrM6wbTypWn5M ybfB+nOCmMtyhieLpm4UZppwXtLm5HTzk8cSfjTfzT/0b9HbZS+WVrxd8oG5PMKKYeIThlez I5VYijMSDbWYi4oTAXQdudywAgAA
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/0schMpX2I_VFNrfCew9PBGY7wq8>
Subject: [Cfrg] draft-irtf-cfrg-spake2 edwards25519 M/N values
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 30 Nov 2017 18:19:22 -0000

I would like to see M/N values for edwards25519 added to
draft-irtf-cfrg-spake2.  This addition requires minor adjustments to the
text and Python code.  Combined with my suggestions from
https://www.ietf.org/mail-archive/web/cfrg/current/msg09370.html the
introductory text for the section should read:

   For each curve in the table below, we construct a string using the
   curve OID from [RFC5480] or its name, combined with the needed
   constant, for instance " point generation seed (M)" for
   P-512.  This string is turned into a series of blocks by hashing with
   SHA256, and hashing that output again to generate the next 32 bytes,
   and so on.  This pattern is repeated for each group and value, with
   the string modified appropriately.

   A byte string of length equal to that of an encoded group element is
   constructed by concatenating as many blocks as are required, starting
   from the first block, and truncating to the desired length.  The byte
   string is then formatted as required for the group.  In the case of
   Weierstrass curves, this means setting the first byte to 0x02 or 0x03
   depending on the low-order bit.  For [RFC7748] curves this means
   taking all the bytes as the representation of the group element.  The
   byte string is then interpreted as an element in the group.  If this
   interpretation yields a valid group element with the correct order
   (p), the byte string is the output.  Otherwise, the initial hash
   block is discarded and the process is repeated until a valid element
   is found.

The new M and N points are:

   For edwards25519:

   M =
   seed: edwards25519 point generation seed (M)

   N =
   seed: edwards25519 point generation seed (N)

I would also like the draft to list the seed string for each point, as
included above.

The Python code should read:

   def canon_pointstr(s):
       return chr(ord(s[0]) & 1 | 2) + s[1:]

   def iterated_hash(seed, n):
       h = seed
       for i in xrange(n):
           h = SHA256.new(h).digest()
       return h

   def bighash(seed, start, sz):
       n = -(-sz // 32)
       hashes = [iterated_hash(seed, i) for i in xrange(start, start + n)]
       return ''.join(hashes)[:sz]

   def gen_point(seed, ec, order, need_canonicalization):
       for i in xrange(1, 1000):
           pointstr = bighash(seed, i, ec.nbytes_point())
           if need_canonicalization:
               pointstr = canon_pointstr(pointstr)
               p = ec.decode_point(pointstr)
               if p != ec.identity() and ec.mul(p, order) == ec.identity():
                   return pointstr, i
           except Exception:

(I will submit a pull request to Ben's github repository for the draft
with all of this.)