Re: Cohen's paper on byte order

From: Douglas A. Gwyn (DAGwyn@null.net)
Date: 04/22/03


Date: Tue, 22 Apr 2003 01:01:51 -0400
From: "Douglas A. Gwyn" <DAGwyn@null.net>

Mok-Kong Shen wrote:
> (1) The AES algorithm is fundamentally (at the end)
> based on the notion of blocks of 128 (individual)
> bits which are designated with sequential numbering
> 0 to 127 in Fig. 2. There are terms applied to groups
> of bits in the document, the one relevant in the
> current debate being 'byte'. But these are for
> convenience/simplification of descriptions only.
> That is, one could 'in principle' 'rewirte' the
> algorithm entirely in terms of the 128 numbered bits
> (directly) without affecting the semantics in
> any way. Do you argree? (If I don't err, you said
> something in conformity with this previously.)

You're being too glib. There are *two* bit numbering
conventions used in the FIPS, both evident in Figure 2.
One of them (top row) applies only to external data,
which is treated only as an indexed bit stream. All
the rest of the FIPS pertains to the bits (organized
in blocks of bytes) from the bottom part of Figure 2
onwards. The significance of these *internal* bits
within the *internal* byte values and also within the
*internal* finite field elements is spelled out in the
FIPS. There is *no* specification for significance of
the external bits within external multibit numerical
objects, which aren't even mentioned in the FIPS.

> (2) In order to be able to run the algorithm to do
> encryption, the user has to supply blocks of
> plaintext as well as the key on an external medium
> to be read by a piece of program code that implements
> AES. Let's suppose that he flips a coin and writes
> down the key as a sequence of 128 bits, starting from
> the left end as one commonly does. Does this sequence
> 'correspond' to Fig. 2 in the sense that the first
> (leftmost) bit of the user is to be identified with
> input_0 of Fig. 2 etc. in that sequential order (i.e.
> without any swapping, shuffling or other permutations)?

If the input is truly an indexed bit sequence, then it
is *specified* how to map it into the block buffers;
that's the top row of Figure 2. This has never been
in question.

> (3) According to common convention, groups of bits
> can be designated in the hexadecimal notation, so e.g.
> '010' can be written as the hex '2'. Thus the user
> can choose to express his key in the hexadecimal
> notation, obtaining a sequence of hex digits, again
> written left to right, with the first hex digit
> corresponding to the first three bits of the original
> bit sequence, etc. Is that o.k.? Note that the
> hex digits are to be obtained from the bit sequence
> in strict sequential order from left to right. In
> particular, there is no swapping of hex digits, nor
> swapping of any larger units (e.g. groups of two hex
> digits).

Wrong. The FIPS *specifies* its use of hex (2-nybble)
notation for *internal* byte values only. There is no
specification in the FIPS for external representation
of key, data, or anything else in terms of hex notation,
octet values, or anything else other than a sequence of
bit values. If somebody tells me that the first byte
of his key (as stored in an external object) has value
32 (decimal) or 0x20 (hexadecimal), that doesn't mean
that the first byte of the internal key byte array must
necessarily have the same numeric value, especially
since there is an apparent requirement for bit reversal
at the I/O interface. You're mixing levels. For a
better example, suppose you are using a 9-bit oriented
architecture (Sperry 1100 series for example) and the
first byte of the external key data has the numeric
value 260 (decimal) or 0x104 (hexadecimal). When it
reaches the AES internal key byte array, does bit 0
of byte 0 (using the FIPS-specified internal numbering)
contain a 1 or a 0? The answer is that this is *not
specified*. We don't know how to apply the FIPS index
values for external data bits to the bits within the
actual data in external storage. And when the external
data organization is other than as octets, this lack of
specification is much more evident, to the point that
it is patently absurd to attempt to infer it from the
FIPS test vectors, pseudo-code, or any other argument
that we have been hearing in this thread.

I have suggested (off-line) to Brian Gladman a small
note that could be attached to the FIPS to provide
recommended practice for this mapping.

> (4) Now look at Sec. A.1 of the document where there
> is an example:
> Cipher Key = 2b 7e 15 16 28 ae ..........

Since the notation has been explicitly been defined
in the FIPS for internal byte values, and *only* for
internal byte values, a careful reader would infer
that these are the values in the AES key "byte" array
(where "byte" is also carefully defined by the FIPS
for *only* the internal 8-bit groupings), i.e. the
lower part of Figure 2. That is entirely appropriate
given that outside the I/O layer there could be a
wide variety of architectures (data organizations),
so that there is no way to know what the key would
have to look like externally (except in terms of the
AES indexed bit array model, but specifying a long
string of 1s and 0s would be unwieldy).

> Doesn't this 'identify', in this example case,
> exactly the user-given key as expressed as hex digits
> in (3) above and, being the 'same' is, in particular,
> (trivially) in the same sequential order?

It identifies the values in the internal byte array.

> (5) The Sec. A.1 then said that from that key one
> should obtain four words w_0, w_1, w_2 and w_3
> with contents (also expressed in hex digits) as
> depicted there. If an implementation that correctly
> realizes that, then it has done it in a way in
> conformity to the AES standard. Do you agree?

All of this pertains to what the values look like
on the "inside" of the algorithm, not in the external
environment (which might not even *be* organized into
8-bit bytes).