REPOST: Re: Idle curiosity (ieee bitorder)

Tom St Denis wrote:
> What would posess someone to define a bit order wherein each byte has
> the bits stored in big endian format then store the bytes in little
> endian?
>
> ... I'm trying to speed up LRW/GCM table creation with a word-oriented
> multiplier followed by optimized reduction (e.g. 8x16 table) and so far
> it ain't working.
>
> But just curious who thought this break of convention was a "good
> idea".

What convention?

As far as I remember GCM has an abstract specification that defines its
Galois field elements only as bit sequences without specifying a mapping
of these sequences onto arrays of bytes or onto bits within bytes (or
any other representation). I don't recall if this is also true for LRW.
Where integers are involved (for example, for bit sequence lengths) GCM
uses a big endian convention.

There is a logic for indexing bits from zero upwards left to right and
then mapping bits 8n..8n+7 onto byte[n] and I suspect that almost all
implementers will do this (fortunately most probably won't even realise
that they have a choice).

We then have to decide whether an 8-bit sequence such as:

01234567 ... <- bit index in sequence
11100001 ... <- bit sequence

is mapped to bytes as 0xe1, 0x87 or in some other way (I am treating
bytes here as they are normally written in C). Here there is a strong
logic for either 0xe1 or 0x87 over other alternatives but no
overwhelming logic for choosing between these two.

The advantage of mapping to 0xe1 is that the bit sequence expressed
naturally, left to right, as a sequence of 4-bit units in hex has the
same sequence of hex units on paper as an array of bytes that represents
it, which is an aid to implementation (test vector inspection etc.).

So, assuming we discount 'perverse' mapping choices and go for one of
these two options (combined with the bit sequence to byte array mapping
indicated earlier) we end up with two possible GCM implementations.

This is the same choice as we have for AES and arises because there is
NO universally agreed convention for mapping bit sequences onto bytes.
Worse still, when we are dealing with Galois fields (as both AES and GCM
do) we have the further complication that we cannot, in principle, rely
on numeric significance unless we specify how to map Galois field
elements onto integers. And again there is no standard way of doing this.

Fortunately for both AES and GCM, reference implementations and test
vectors (provided as files rather than on paper) are supplied in a form
that heavily suppress the 'wrong' versions even though these might not
be ruled out by the specifications themselves. So, even though there is
a choice, I suspect again that many implementers may not even realise
that alternative implementations are possible.

For AES this issue came as a surprise to some as it was only evident
well after the standard had been published (those involved in the
specification were well aware of the issue). But as far as I am aware
it has not proved to be a significant issue in practice.

Brian Gladman

========= WAS CANCELLED BY =======:
Path: ...204.153.245.151.MISMATCH!green.octanews.net!news-out.octanews.net!news.glorb.com!news-feed01.roc.ny.frontiernet.net!nntp.frontiernet.net!cox.net!news-xfer.cox.net!p01!fed1read05.POSTED!53ab2750!not-for-mail
From: BRG <brg@xxxxxxxxxxx>
Control: cancel <43dcd400$0$1462$ed2619ec@xxxxxxxxxxxxxxxxxxxxxxxxxx>
Subject: Cancel "Re: Idle curiosity (ieee bitorder)"
Newsgroups: sci.crypt
Message-ID: <23cbc850$3%8502$fc3866ce@xxxxxxxxxxxxxxxxxxxxxxxxxx>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Newsreader: TIN ("Quincy") [UNIX 4.4 45348BETA PL7]
Lines: 2
Date: Sun, 29 Jan 2006 17:13:51 GMT
NNTP-Posting-Host: 70.162.170.136
X-Complaints-To: abuse@xxxxxxx
X-Trace: fed1read05 1138562843 70.162.170.136 (Sun, 29 Jan 2006 14:27:23 EST)
NNTP-Posting-Date: Sun, 29 Jan 2006 14:27:23 EST
Organization: Cox Communications
.

Relevant Pages

  • C++ Binding: Sequence allocbuf/freebuf
    ... I've checked the TAO and MICO sequence implementation and both appear ... Is the TAO and MICO implementations non conforming? ... C++ dialects without exception handling (especially for ctors ...
    (comp.object.corba)
  • Re: Idle curiosity (ieee bitorder)
    ... Galois field elements only as bit sequences without specifying a mapping ... Where integers are involved (for example, for bit sequence lengths) GCM ... Fortunately for both AES and GCM, reference implementations and test ...
    (sci.crypt)
  • Re: newbie question concatenate function useage
    ... Glossary of the HyperSpec) for some type of sequence. ... Sequence is a supertype of vectors and lists. ... There are no standard types of sequences other than list or vector ... though the standard allows implementations to provide others if they ...
    (comp.lang.lisp)
  • R: [fw-wiz] IPSEC over load-shared T1s (per packet)
    ... >>Implementations that do not take that into account are broken. ... You can spend all of your efforts assuring that in your border router ... packets flow in sequence, but you ...
    (Firewall-Wizards)
  • Re: #include behavior
    ... possibility to place a source file into some place. ... which ignores the mapping specified by 6.10.2. ... the source file identified by the specified sequence between the ...
    (comp.lang.c)