Old-ish email from Brian Gladman regarding bit ordering in Galois Field representation. Begin forwarded message: Date: October 26, 2006 Oct 26, 10:10 AM Subject: Re: XEX code
Hi All,
Unfortunately, I haven't had much time to look this over. I've got a
couple comments and some ideas for more test vectors.
- Brian, you might consider using constants from <stdint.h>, such as
'uint32_t', 'uint64_t'. The current code uses 'uint_32t', which is
almost identical to the stdint.h version within the ANSI C99 standard.
Hi Matt (and Colleagues),
Unfortunately <stdint.h> is a C99 feature that many compilers don't
support. In consequence making any code depend on the existence of
<stdint.h> will pretty well guarantee that it is not portable.
And if I do use the exact names used in <stdint.h>, this can then cause
multiple definition problems when it is available and people try to mix
my code with their own.
All very sad really.
So what I do is to use names that can be converted into the names used
in <stdint.h> by using a simple and foolproof regular expression based
search and replace function (I even offer a regular expression to do
this). So if anyone wants to use my code with the standard names it's
pretty trivial to do this conversion.
This applies to all my published code and is the result of a lot of
problems that arose when I did indeed try to use <stdint.h>.
- A comment on Endian order: Pretty much all cryptography is specified
in Big-endian order (e.g. AES, SHA). My recommendation is to keep
big-endian order if possible. It should be possible to have a
reasonably efficient implementation for either choice. The AES cipher
already has to do some kind of conversion from bytes to words before
running the rounds. In looking at the Galois multiply (or rather the
LFSR), I'm thinking it might be useful to do the byte-swap once per
sector, and then handle everything as 32-bit words from that point on
(including the AES operation). The performance shouldn't be too bad.
(Specifically, see the gf_mulx function in xex.c: The IS_LITTLE_ENDIAN
case might be simplified if the bytes are first converted to words, and
then handled consistently from that point onward.)
I don't care a great deal about what you define here PROVIDED that, in
the Galois Field representation of the unit field element, the single 1
bit ends up in a position within whatever byte it ends up in that
represents a numeric value of 1.
This amounts to requiring that the mapping that is used maps x^n in the
field to 2^n in the normal integer representation used on almost all
processors.
The GCM mapping in which a unit field element ends up in a byte as 0x80
is an implementation disaster, one that caused me an enormous amount of
pain in building optimised versions of LRW before you folk (thankfully!)
replaced it with XEX.
The four bit sequence to byte array mappings that make possible sense are:
AES byte 0 1 .... 15 16
1. 0x87 0x00 .... 0x00 0x01 - little endian in bytes
2. 0x01 0x00 .... 0x00 0x87 - big endian in bytes
3. 0xe1 0x00 .... 0x00 0x80 - the GCM mapping
4. 0x80 0x00 .... 0x00 0xe1 - reversed GCM mapping
If you want to move from 1 to 2, I don't have too much of a problem in
principle but I have just spent quite a bit of time optimising for 1 :-(
But if you want to move to mapping 3 or 4 (which includes the GCM
mapping) then I will disown you!!
David McGrew and John Viega know my feelings about their terrible
decision to use this mapping, one which I consider to be a disaster for
software implementation. Why they didn't consult an expert in software
implementation before making this decision is beyond me.
best regards,
Brian
|