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

Michael Clark <michael@metaparadigm.com> Tue, 27 January 2015 19:56 UTC

Return-Path: <michael@metaparadigm.com>
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 3C7E41A8866 for <cfrg@ietfa.amsl.com>; Tue, 27 Jan 2015 11:56:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.458
X-Spam-Level:
X-Spam-Status: No, score=-1.458 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, IP_NOT_FRIENDLY=0.334, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_DKIM_INVALID=0.01] autolearn=no
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 HXEJeiLg1k-o for <cfrg@ietfa.amsl.com>; Tue, 27 Jan 2015 11:56:21 -0800 (PST)
Received: from tlsx.org (tlsx.org [67.207.128.90]) (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 72A161A8A1C for <cfrg@irtf.org>; Tue, 27 Jan 2015 11:56:21 -0800 (PST)
Received: from monty.local (unknown.maxonline.com.sg [58.182.168.20] (may be forged)) (authenticated bits=0) by tlsx.org (8.14.4/8.14.4/Debian-4) with ESMTP id t0RKICS7004231 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NOT); Tue, 27 Jan 2015 20:18:16 GMT
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=metaparadigm.com; s=klaatu; t=1422389898; bh=aYUF7cr1MEyZBJxIG207lcItxxLtTBYZXswwcIDzHyA=; h=Date:From:To:Subject:References:In-Reply-To:From; b=JUsmn49WhRdCNuy8R4XhWAS2dpwY1ZzAZ7jRcrOT6wbMEVGKadM6hHyAl4a6qlUIl IRS1lo87gUbHI8Z/NkETIVjerRXh/oMjazlRJ349fxMrrAls+JCZWABuD3mNI9Lye2 wRUHdTgMD0clJkcxvqS0RFXH2ZmIFc0qBUeQq8R8=
Message-ID: <54C7ED50.2000303@metaparadigm.com>
Date: Wed, 28 Jan 2015 03:56:00 +0800
From: Michael Clark <michael@metaparadigm.com>
Organization: Metaparadigm
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.10; rv:31.0) Gecko/20100101 Thunderbird/31.4.0
MIME-Version: 1.0
To: Peter Gutmann <pgut001@cs.auckland.ac.nz>, "'cfrg@irtf.org'" <cfrg@irtf.org>
References: <9A043F3CF02CD34C8E74AC1594475C73AAF68325@uxcn10-tdc05.UoA.auckland.ac.nz>
In-Reply-To: <9A043F3CF02CD34C8E74AC1594475C73AAF68325@uxcn10-tdc05.UoA.auckland.ac.nz>
Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: 8bit
X-Virus-Scanned: clamav-milter 0.98.4 at klaatu.tlsx.org
X-Virus-Status: Clean
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/Zc-UIFBOHpdoSbzlBggxxKX1pM0>
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: Tue, 27 Jan 2015 19:56:23 -0000

On 27/1/15 6:34 pm, Peter Gutmann wrote:
> Michael Clark <michael@metaparadigm.com> writes:
> 
>> This code could do with some optimization, bswap(32|64) intrinsic (uses BSWAP
>> machine instruction on x86_64, ARM, etc), working with a machine word size
>> loop with a small tail loop to handle the modulus of the difference in length
>> of the bignum from the machine word size. It is working byte by byte.
> 
> This is another example of "I can't believe we're having this discussion".
> We're talking about bignum operations measured in the millions of CPU cycles
> (a basic 1024-bit RSA decrypt is about 10M cycles, with P256 it's 7M cycles,
> courtesy of the Crypto++ benchmark data) and you're bringing up optimising
> something that might take a few hundred cycles (ignoring memory latency
> overhead, which is going to hit you at some point whether you endian-reverse
> or not).
> 
> The issue isn't about whether a 0.001% overhead is worth applying custom
> architecture-specific assembly-language to eliminate, it's the issue of
> encoding a particular implementation artefact into a standard.  As djb has
> helpfully pointed out, he could have decided to encode the values as ASCII
> decimal digits, or perhaps doodles, sign language, and squirrel noises.  Would
> crypto standards then require that everything using 25519 be able to encode
> the output as squirrel noises just because that's what one implementation
> does?
> 
> The universal standard for crypto bignums is big-endian (things like
> curve25519-sha256@libssh.org aren't a standard, it's what one implementation
> chooses to do).  The 25519 form is an implementation artefact and should have
> no place in a standard.

I agree. I did qualify the statement that its unlikely to register on a
profile. e.g. don't forget to paraphrase without the context:

On 26/1/15 8:57 pm, Michael Clark wrote:
> So with big-endian wire-formats, practically all machines are going to
> bswap as the internal rep will be little endian. That cost is probably
> low compared to the cost of the computation, so there is a reasonable
> rationale to stick to big-endian.

This seems to be about adapting to IETF tradition. Fair enough.

The question is whether or not in the case of Curve25519, the keys are
considered an "opaque octet string" or unless the point needs to be
consumed and interpreted outside of the cryptographic primitive; then
there is an argument to follow the big-endian bignum tradition.

1). Will Curve25519 be used elsewhere (other than as a diffie-hellman
replacement) where the keys are exposed in form they need to be operated
on as a bignum, rather than opaque 32-byte octet strings? i.e. is to be
considered a standalone cryptographic primitive?

2). From reading Curve25519, the keys are stated as opaque, however I
understand that Curve25519 can be expressed in various isogenies where
the keys (32-byte strings) are no longer opaque and are big-nums. Is it
intended to be used in a general way as a parametrization?

If so it would mean it might be a good idea either for Curve25519 to use
byteswap from network byte order or to define a big-endian alternative
with a different name that does so. X25519; where the keys are no longer
opaque as per the current normative reference that specifies
"little-endian" 32-byte strings:

  https://tools.ietf.org/html/draft-josefsson-tls-curve25519-01
  http://cr.yp.to/ecdh/curve25519-20060209.pdf

a). If it is intended to be used as a standalone primitive, then it
doesn't matter so much: "32-byte octet string"

b). However if it is to be used generally as a parametrization that fits
into a curve generalization then this provides a good rationale to use
the tradition of big-endian bignums. i.e. ends up in ASN.1 fields, with
different parametrization of the same generalization.

Does that make it any easier? :-)