P1619.0 XEX endianness ambiguities
Dear all,
First, well done on quickly settling on this new mode after issues with LRW. The spec is nice and
clean, but unfortunately the subject of endianness has to rear its ugly head. I've been meaning to
write this email for a few weeks now, but keep getting pulled onto other things. I've just had a
long chat with Brian Gladman and he's generally in agreement with me on this.
Doug wrote:
> In particular, the definition of byte and bit ordering required for field multiplication
> is NOT contained anywhere in the normative section of the draft. Am I missing something (I hope)?
Yes, Doug, you are right, there are currently two ambiguities in the normative part of the spec, and
I want to point out something unusual about the psuedo-code implementation too!
> The definitions are contained only in the C pseudocode in the (informative) Annex C.
> It seems to me that either we need to move Annex C into a normative portion of the
> spec, or we need to go thru the detail of defining the bit and byte ordering conventions,
> which can be rather lengthy and very difficult to make clear and correct.
I disagree. It only needs two sentences, and two simple 128-bit block drawings. I think Annex C
should remain informative.
Here are my concerns:
1. The bit/byte ordering of the LBA when placed into the tweak AES operation is not specified.
2. The bit ordering of the GF operations with respect to the AES block is not specified.
3. The psuedocode uses an unusual mapping of polynomial bit ordering to AES bit ordering.
4. The sentence "All outputs are little endian byte arrays" needs further clarification or removal.
5. Variable letters used for LBA/sector number and block-within-sector are inconsistent
Here is the ambiguous line:
T <= AES-enc(Key2, i) x (alpha^j)
Let's look at the issues in detail:
1. The encoding of the LBA when placed into the tweak AES operation is not specified.
We need to specify the mapping of LBA integer "i" (lowercase) into LBA block "I" (uppercase). We
could choose to define the encoding at the bit or byte level, depending on whether we think of AES
as having a bit-numbered, or byte-numbered interface. For a byte interface, FIPS-197 $3.3 figure 2
specifies how AES blocks should be treated as arrays of bytes, so there is no need to specify the
bit ordering within the bytes (MS bit 7 of first byte is first leftmost bit 0 of AES block).
So, we could specify the encoding of "i" in one of four popular ways:
(a) encode integer "i" bitwise little-endian, putting LS bit of i at leftmost bit 0 of AES block I.
(b) encode integer "i" bitwise big-endian, putting LS bit of i at rightmost bit 127 of AES block I.
(c) encode integer "i" bytewise little-endian, putting LS bit of i at bit 7 of AES block I.
(d) encode integer "i" bytewise big-endian, putting LS bit of i at rightmost bit 127 of AES block I.
Note that (b) and (d) are equivalent, and that (a) will need bit-flipping of bytes if the integer
"i" is already encoded in bytes (tedious in software, usually free in hardware).
The sensible choice is therefore (c) or (b/d), and the psuedo-code uses (c). I have no preference
(being a processor-agnostic hardware person) but I would normally choose (b/d), since it has the
advantage of being the same when considering both bit-wise and byte-wise mappings.
Action: Add definition of "I" (block) versus "i" (LBA integer). Add one sentence to spec (choose
from (c) or (d) above) and clarify with a figure that shows explicitly where the LS and MS bits and
bytes of "i" end up in a 128-bit AES block I. Change ambiguous line in step-by-step sequence to do
operations with I not i:
T <= AES-enc(Key2, I) x (alpha^j)
where I = LBA_Encode_Method(i) as per figure XX.
PS: Brian just mentioned to me that Serge was looking for pure bit-wise definitions everywhere, in
which case option (b) is the obvious choice since it doesn't mention bytes.
2. The bit ordering of the GF operations with respect to the AES block is not specified.
3. The psuedocode uses an unusual mapping of polynomial bit ordering to AES bit ordering.
We need to specify which end of the AES block corresponds to the LS (unity) term of the polynomial.
This definition should ideally be made at the bit level, since the GF(2^128) polynomial has 128
terms and no concept of bytes. There are two obvious possibilities, and one less obvious:
(a) LS term of polynomial is at leftmost bit 0 of AES block [like GCM]
(b) LS term of polynomial is at rightmost bit 127 of AES block [like OCB, and Rogaway XEX]
(c) LS term of polynomial is at bit 7 of AES block [like psuedo-code!!!]
The spec gives us this information in $4.2:
"\mul: Modular multiplication of two polynomials over the
binary field GF(2), modulo x^128 +x^7 +x^2 +x +1."
"\alpha: An element of GF(2^128) field that corresponds
to polynomial x, i.e. (0000…010)."
Both of these _suggest_ that the LS term of the polynomial should be on the right, corresponding to
bit 127 of the AES block, as per choice (b) above. Also, the original Rogaway XEX paper clearly uses
choice (b) [see "Preliminaries" section]. Choice (a) would be suitable if the two definitions
repeated above were reversed, but is somewhat unfriendly to software, so is not proposed.
However, if you inspect the psuedo-code carefully you will realise that it uses neither (a) nor (b):
#define GF_128_FDBK 0x87
...
T[0] ^= GF_128_FDBK;
It maps the polynomial little-endian byte-wise (c) which puts the LS term of the polynomial in the
LS bit of the first byte, at bit 7 of the AES block, an unusual place. I do not think this is a
sensible choice. It also means that any (hardware) implementation which keeps the AES block in a
128-bit vector cannot just leftshift that whole vector to achieve a polynomial multiply-by-alpha
because the polynominal terms are not contiguous within the AES block.
[Note: there is no issue with bit-ordering of "j" since it is merely counting multiplies by alpha.
And as there is no full GF multiplication and the (alpha^j) operation is trivial the polynomial
ordering with respect to any data word arrival order, etc, is not really a concern like it is in GCM
hardware.]
Action: Add one sentence to spec (choose (b) above) and clarify with a figure that shows explicitly
where the LS and MS terms of polynomials end up in a 128-bit AES block. Change the psuedo-code to
match the original Rogaway definition (b):
// LFSR "shift" the tweak value for the next location
Cin = 0;
for (j=AES_BLK_BYTES-1; j>=0; j--) { /* loop reversed */
Cout = (T[j] >> 7) & 1;
T[j] = ((T[j] << 1) + Cin) & 0xFF;
Cin = Cout;
}
if (Cout)
T[15] ^= GF_128_FDBK; /* LS poly bits in rightmost AES byte */
4. The sentence "All outputs are little endian byte arrays." needs further clarification or removal.
This appears in Annex B, and is meaningless except for the "LBA" vector "i" (which might be printed
in such an order - see next para). Considering point (1) above, I would instead print two lines, the
LBA integer "i" printed as a "proper" hexadecimal integer of the minimum length (with MS nibble on
left, LS on right), and the LBA block "I" printed as a full 128-bit block, showing the chosen
encoding. Having both allows the encoding method to be verified.
An unfortunate property of the LBAs chosen for the test vectors (at least, those in the document) is
that they are either single bytes, or repeated byte sequences, and this makes it very hard to
establish the ordering of the LBA bytes by inspection. Perhaps the test vectors could be changed to
use reasonably large-valued, non-palindromic, consecutive sector numbers, preferably showing a
roll-over from FF..00 in the LS byte for maximum clarity. I note that the additional short vectors
on Doug's last email go some way towards this, but do not increment the sector number from one
vector to the next.
5. Variable letters used for LBA/sector number and block-within-sector inconsistent
A final comment is regarding the consistency of variable letters in different sections. In $5.x.x we
have the tweak pair {i,j}, in Annex C psuedo-code we have {S,i} (j being used for a byte loop
counter) and in Annex D.4.1 we have the pair {s,t}, as per the original Rogaway XEX paper. Is there
any chance we can standardise the letters across the whole document, or at least only have two
different definitions?
Regards,
Colin.
Colin Sinclair
HELION Technology Limited
Ash House, Breckenwood Road
Fulbourn, Cambridge CB1 5DQ
England.
~~~~~~~~~~~~~~~~~~~~~~~~~~~
tel: +44 1223 500 924
fax: +44 1223 500 923
http://www.heliontech.com
mailto:colin@heliontech.com
~~~~~~~~~~~~~~~~~~~~~~~~~~~