Re: Idle curiosity (ieee bitorder)

BRG wrote:
> No, it's not that simple. The GCM specification has no concept of
> 'registers' or multiplication by 2 - all it has is 'bit sequences' and
> field multiplication by 'x'.
>
> And if you look carefully at the GCM specification you will find that it
> defines Galois Field multiplication by 'x' as a right shift of the
> ***bit sequence*** (when presented with increasing bit indexes from left
> to right).
>
> Now if _you_ map the bit sequences onto registers one way round this
> will require a right shift of your register representation whereas if
> you map this the other way round you will need a left shift. But it is
> important to see this as _your_ choice as the implementer.

If you look at the test vectors they specify an array of bytes. If you
load them that way into a register on ANY modern processor the meaning
is reversed. "right shift" multiplies by x.

Where this becomes a problem is the byte array is LITTLE ENDIAN. That
is the first byte is the LSbyte (and the MSnible of that is the
LSnibble of the sequence).

So if you want to load say 4 or 8 bytes into a register you have to
load in big endian not little endian as you would expect. If you load
little endian then both a right and left shift won't produce the
desired result. My problem isn't that the math is "broken" it's that
it's needlessly complicated.

Part of a good design spec writer is to write something that
implementors can make good use of. GCM and LRW would be "just as
secure" had they defined a proper bit order. Where you wouldn't have
two directions of operations.

> > So with that in mind for GCM and LRW you have to load the bytes in big
> > endian and do right shifts to "double" the value. But the first byte
> > is not the actual MSbyte ...
>
> You most certainly don't have to do this. Moreover you might do this but
> I don't in many of my implementations.

You'd have to swap the bits per byte before you could load it.
Otherwise a shift would send the carries into the wrong bytes.

For instance, if you did a LITTLE ENDIAN load then shifted right the
7th bit of byte 3 would go into bit 0 of byte 2 which is backwards.

At best, you could swap the bytes and then do a left shift to get the
"multiply by x".

> I frequently load bytes into registers using platform byte order and
> then choose either left or right shift operations depending on whether
> the machine uses big or little endian register loading conventions.

Most platforms load bits of a byte in the same order though.

The only way to "multiply by x" in their natural bit order is a right
shift. Regardless of the order bytes are loaded into a word. Othewise
you'd have bit 1 going to bit 0 with a left shift which is not a
"multiply by x".

> > in normal representation you'd load it in little endian and do a left
> > shift to double it.
>
> It is interesting that people get so used to dealing with integers that
> they do not notice that other things don't behave in the same way. The
> Galois field multiplication by x is a shift of a _bit sequence_ which
> can be mapped onto registers in either order whilst still being able to
> use shift operations effectively.

Effectively it's a double operation. For instance, any integer can be
expressed as a polynomial in GF(2)[x] by substituting 2 for x. So a
"shift by x" is just a multiplication by two in most traditional
senses.

Most algorithms follow this convention. Rijndael, Twofish and most
LFSR implementations are this way. That's why it's called a
"convention". It isn't "right" just more natural.

> If you miss this you could easily end up with slower code since you
> might map the field onto registers in a way that requires byte swapping
> on some systems. You are hence giving up on useful optimisation
> possibilities.

I don't see how a left shift produces the right values. Your bits are
still in big endian inside the byte. You'd have to perform a bit swap
on load anyways. It's cheaper to load in reverse order than send all
the bytes through an 8x8 to fix up the order.

> Those who wrote the (mostly) abstract specifications for AES and GCM
> worked hard to avoid making implementation decisions in order to ensure
> that implementers - those who should make such choices - would have the
> freedom to do so.

AES is defined left to right from MS to LS. 0x11B is the reduction
polynomial not 0xE1 or 0x87 or ??? So when you literally map this to C
code you can use the constant 0x11B against your registers.

Since really no platform purposefully loads bits in the wrong order.
They may be big endian but the bits are still the same order inside
each unit [octet].

Tom

.

Relevant Pages

  • REPOST: Re: Idle curiosity (ieee bitorder)
    ... > defines Galois Field multiplication by 'x' as a right shift of the ... > Now if _you_ map the bit sequences onto registers one way round this ... Where this becomes a problem is the byte array is LITTLE ENDIAN. ... So if you want to load say 4 or 8 bytes into a register you have to ...
    (sci.crypt)
  • REPOST: Re: Idle curiosity (ieee bitorder)
    ... I say "do a shift which doubles the value in a register" ... "multiply by x" which is typically analogous to multiplying by 2. ... So with that in mind for GCM and LRW you have to load the bytes in big ... endian and do right shifts to "double" the value. ...
    (sci.crypt)
  • Re: Idle curiosity (ieee bitorder)
    ... I say "do a shift which doubles the value in a register" ... "multiply by x" which is typically analogous to multiplying by 2. ... So with that in mind for GCM and LRW you have to load the bytes in big ... endian and do right shifts to "double" the value. ...
    (sci.crypt)
  • RE: Backwards File Dump
    ... The fact that left shift multiplies and right shift divides establishes ... Strings are therefore stored in a Big endian fashion, ... >and right in memory. ... >C code permits aliasing. ...
    (comp.os.vms)
  • Re: Tai Chi
    ... People have an innate ability to shift force vectors. ... ground or the weight. ... Instead of "holding" the load on the ...
    (rec.martial-arts)