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

Michael Clark <michael@metaparadigm.com> Tue, 27 January 2015 05:50 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 4286B1B2BA0 for <cfrg@ietfa.amsl.com>; Mon, 26 Jan 2015 21:50:20 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.032
X-Spam-Level: *
X-Spam-Status: No, score=1.032 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, IP_NOT_FRIENDLY=0.334, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] 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 lW3FsB-kR_XT for <cfrg@ietfa.amsl.com>; Mon, 26 Jan 2015 21:50:19 -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 A51C31B2B9E for <cfrg@irtf.org>; Mon, 26 Jan 2015 21:50:16 -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 t0R6CF85001883 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NOT) for <cfrg@irtf.org>; Tue, 27 Jan 2015 06:12:19 GMT
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=metaparadigm.com; s=klaatu; t=1422339140; bh=k8S3w6fGMfdNMveupBw0bFg9Au+ezUHWjp1lEYx7URM=; h=Date:From:To:Subject:References:In-Reply-To:From; b=UTXdDvg06KtxiBo68zAoiUsrZ42XExvPDMYztIhqcEyn35S+TlIhnHFXznwBTaK7j VA5JjNBUonpER55A996TZS1wuG2pWScQ5daOHCyAs264BkLOvpozkwivXVraneBnaz 6fif2FqU4sTu91YE8v4rdVltRKG24tHVGda1wFxQ=
Message-ID: <54C7270B.1000806@metaparadigm.com>
Date: Tue, 27 Jan 2015 13:50:03 +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: CFRG Mailing List <cfrg@irtf.org>
References: <9A043F3CF02CD34C8E74AC1594475C73AAF65EBB@uxcn10-tdc05.UoA.auckland.ac.nz> <54C639D5.5050104@metaparadigm.com>
In-Reply-To: <54C639D5.5050104@metaparadigm.com>
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/yn1vy-dgxEgdK4HExNioZsyoKLg>
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 05:50:20 -0000

On 26/1/15 8:57 pm, Michael Clark wrote:
> Someone starting today would indicate endianness statically or
> dyanamically in their number format and use the hot potato principle.
> Get it off your hands at the lowest cost to yourself, which nowadays is
> little-endian. Remember GHASH is Bit Reflected (base 2 little endian)
> and it made it into a spec.

Just saw DJB's email on twitter.

https://www.ietf.org/mail-archive/web/cfrg/current/msg05938.html

Wrote this last night before seeing it:

I believe GCM GHASH is bit-reflected (more accurately bit level little
endian, the true opposite to big-endian or "true little endian") on the
wire in the GCM AEAD hash. It is an existing example of not using
big-endian, but also not using little-endian as we commonly know it
(bignums: with 8-bit big endian limbs, little limb first).

The finite field bit set for GHASH could potentially be represented in
either big-endian or little-endian. e.g. where the bit offsets [0-127]
are within either of those domains, but it is neither. It is perhaps
better called "true little-endian or base 2 little-endian".

Just citing this as precedence for a 16-octet opaque encoding of a
galois field value that is not big-endian and is used in TLS, SSH, etc.

That said, GHASH is really a GF(2^n) bit set, and not a scalar.

The fact that GHASH only uses xor and shifts makes it different to
scalarmult, however the Intel PCLMULQDQ GHASH implementation needs to
deal with this bit-reflection property in AES-GCM as the PCLMULQDQ
instruction shifts "left", not "right" as you would typically do for
GHASH. It seems to cause extra work for computers with little-endian
bignums and 8-bit big endian limbs, little 8-bit limb first.
litte-endian as we know it is a misnomer and GHASH is perhaps "true
little-endian". GCM is an example of making computers work even harder
using an even more obscure encoding.

If you want to break a tradition; it pays to have a counter example
where it has already been broken (and made things harder).

You have to consciously decide to "not do extra work" on most computers
or maintain tradition. le wire format still needs bswaps for portable
code: just they will be compiled out on prevalent systems "today" versus
mid-to-late-90's.

Ref:
{Carry-Less Multiplication and Its Usage for Computing the GCM Mode}