Re: [Cfrg] Point format endian (was: Adoption of draft-ladd-spake2 as a RG document)

"Dan Harkins" <dharkins@lounge.org> Wed, 28 January 2015 04:47 UTC

Return-Path: <dharkins@lounge.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 38BA81ACD26 for <cfrg@ietfa.amsl.com>; Tue, 27 Jan 2015 20:47:14 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.867
X-Spam-Level:
X-Spam-Status: No, score=-3.867 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, IP_NOT_FRIENDLY=0.334, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_PASS=-0.001] 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 RfweRhttdwvS for <cfrg@ietfa.amsl.com>; Tue, 27 Jan 2015 20:47:12 -0800 (PST)
Received: from colo.trepanning.net (colo.trepanning.net [69.55.226.174]) by ietfa.amsl.com (Postfix) with ESMTP id 446DA1A1B8D for <cfrg@irtf.org>; Tue, 27 Jan 2015 20:47:12 -0800 (PST)
Received: from www.trepanning.net (localhost [127.0.0.1]) by colo.trepanning.net (Postfix) with ESMTP id B190310224008; Tue, 27 Jan 2015 20:47:11 -0800 (PST)
Received: from 69.12.173.8 (SquirrelMail authenticated user dharkins@lounge.org) by www.trepanning.net with HTTP; Tue, 27 Jan 2015 20:47:11 -0800 (PST)
Message-ID: <0bb77994109993ccca2f70fc646aead0.squirrel@www.trepanning.net>
In-Reply-To: <CACsn0cnFQhRrP=7oG+7eWKr_2+L+kNjGkXW0xHsdV5WLXsH1Tw@mail.gmail.com>
References: <9A043F3CF02CD34C8E74AC1594475C73AAF6839A@uxcn10-tdc05.UoA.auckland.ac.nz> <54C77376.3080005@cs.tcd.ie> <9ad11090808dc1e97bfc10196ad0e0c4.squirrel@www.trepanning.net> <CACsn0c=+uKicVmuex+jo5L6VQcJPLuQ45z3T1EZbSXMOrpy-=A@mail.gmail.com> <4dbcfbff889d175765d549d96826767a.squirrel@www.trepanning.net> <CACsn0cnFQhRrP=7oG+7eWKr_2+L+kNjGkXW0xHsdV5WLXsH1Tw@mail.gmail.com>
Date: Tue, 27 Jan 2015 20:47:11 -0800
From: Dan Harkins <dharkins@lounge.org>
To: Watson Ladd <watsonbladd@gmail.com>
User-Agent: SquirrelMail/1.4.14 [SVN]
MIME-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: 8bit
X-Priority: 3 (Normal)
Importance: Normal
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/fzT26WgkjYw14bS_XhnnLNpeWwo>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Point format endian (was: Adoption of draft-ladd-spake2 as a RG document)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 28 Jan 2015 04:47:14 -0000

On Tue, January 27, 2015 5:49 pm, Watson Ladd wrote:
> On Jan 27, 2015 9:30 AM, "Dan Harkins" <dharkins@lounge.org> wrote:
>>
>> On Tue, January 27, 2015 9:07 am, Watson Ladd wrote:
>> >
>> > My SPAKE2 draft contains specified M&N, generated by a C program
>> > Nathan McCullum sent me. I've been unable to determine what that
>> > program does in anything more than the vaguest terms because OpenSSL
>> > internals are opaque, but users do not need to generate their own
>> > points.
>>
>>   Yes, it's opaque to you, the application writer. That's the point! But
>> to have curve25519 as a special case then you'd have to pry into the
>> opacity of the code and figure out what's going on.
>>
>>   So to allow Nathan McCullum to send you a chunk of code that
>> should work with any curve supported by OpenSSL, and have it just
>> work without you knowing any opaque internals, it requires a
>> canonical conversion of bitstring to integer to field element and
>> back.
>>
>>   If, as you say, users do not need to generate their own points then
>> they're gonna have to have a registry of M and N for all curves. And
>> to import a bitstring (for instance from the appendix of your draft)
>> into code requires converting that bitstring into an element. And
>> without the canonical conversion then you need to know about the
>> opaque internals.
>
> What makes you think I wouldn't write the point appropriately? More
> importantly, if this encoding was different for each curve, how would I
> notice, except when I generate the table? Every point has a representation
> either way.

  You don't understand. It's not that you don't write them appropriately.
It's that you are writing them big endian because you are interpreting the
output of the appropriate hash function as a big endian number.

  Your draft claims "[t]he points are presented in hexidecimal SEC1 format."
If someone wants to implement your draft he or she would have to convert
the bit strings in table 3 into points on the elliptic curve.

  So check out how one converts an octet string into an elliptic curve
point in
SEC1. It's section 2.3.4 and that will take you eventually to section
2.3.8 (octet
string to integer conversion) and that is quite obviously a big endian
conversion.

> I can always do the calculation in PARI and reverse and pad the result. In
> fact, PARI only uses decimal IO so I have to convert anyway. I'm not
> insisting on decimal format to make my tools work.
>
> There is an encoding of x coordinates as 32 byte strings. The intent is
> that this encoding is used for everything having to do with Curve25519.
> Why
> is this such a large problem? At least with the Weierstrass coordinate on
> the wire proposal there was a clear rationale for the change in terms of
> compatibility. But this has nothing to do with compatibility: you will
> need
> to write new code anyway.

 The point is, your draft lists M and N for p256, p384, and p521 and it uses
big endian format exclusively. If one were to try to use curve25519 to
compute M and N it would have to interpret the output of the hash
function differently. So therefore someone who implements your draft
has to know about the special case of curve25519. He has to know not
to do what he'd do for every other curve.

> Of course, it's not the case that there is a single universal key format.
> SEC1 serializes bignums as fixed-width in keys and variable width in
> signatures. PGP uses a different length encoding from TLS. Nor do all
> algorithms on words take the words the same way: MD5 uses a little-endian
> length encoding, and encodes the low byte first. SHA1 uses a big-endian
> length encoding and big-endian words.

  No there is, and it's big endian. MD5 and SHA1 are hash algorithms and
their output is a digest, not a number. The important thing to realize
though is that if one were to use MD5 or SHA1 to generate a bit string
in order to convert the digest into a point on an elliptic curve according
to SEC1 (or X9.62 or ISO/IEC 15946 or RFC 6090) that output would be
interpreted as big endian in both instances, the internals of the hash
algorithm notwithstanding.

> Furthermore, forcing applications to carry out encoding and decoding,
> instead of having the library do it has several bad effects. It makes it
> more complicated to use Curve25519. It prevents codesharing among
> libraries, unless they have identical bignum APIs. It makes applications
> non portable across libraries.

  That is exactly my point! Applications shouldn't have to carry out
different encodings and decodings. If curve25519 does not follow the
canonical convention, though, they will.

> Defining Curve25519 as a function of bigintegers was considered and
> rejected by multiple people due to interoperability problems historically
> caused by lack of canonical byte encodings: TLS DHE uses two distinct
> encodings at some point.
>
> What's wrong with the API everyone is already using?

  Exactly, and everybody is using big endian.

  Dan.