Re: Cohen's paper on byte order

From: Douglas A. Gwyn (DAGwyn_at_null.net)
Date: 05/04/03 

Date: Sun, 04 May 2003 12:35:45 -0400

Mok-Kong Shen wrote:
> You certainly have noted that my arguments essentially
> depend on the applicability of the common hex notation.
> See above. So this applicability issue has to be settled
> in the course of our future discussion, i.e. debated to
> a clear and definite end.

Since the FIPS quite clearly associates its use of hex
notation with the *internal* byte "values", that does
not help address the issue of bit order within external
multibit organizations of data. And since it applies
specifically to 8-bit units, a conflation of notation
for internal objects with values of external objects
does not work for the general case.

> If I don't err, Markus Kuhn's paper principally
> discusses the byte ordering problem in relation to
> AES.

I'm not sure what it does, but if so then it's
irrelevant to the actual issue.

> In several posts of yours, you stressed however
> that byte ordering isn't a problem for anyone.

Quite so.

> How do you explain that? Is Kuhn then 'entirely' wrong
> in his paper?

I have no wish to dig into Kuhn's paper, which according
to you concerns an aspect that I have no problem with.
Since FIPS-197 quite clearly treats the input bit
sequence in groups of 8, with a well-defined order for
those groups, there should not be an octet-ordering issue
for octet-sequence based implementations of AES, just a
bit-ordering-within-octet issue. There is also no
ordering issue at any scale for a true bit-sequence
environment. Because the FIPS-197 I/O model is a pure
bit sequence, there is a bit-order-within-unit issue for
*any* multibit storage units, not just octet units, and
any supplemental specification should apply to all of
them.

> Danny Cohen: On Holy Wars and a Plea for Peace.
>> Bigendian computer scientists send the most significant
>> bit or byte (="end") first or store it at the earlier
>> (= lower) address. ......
> Note that the last quoted sentences implies, as one
> would expect, that whether the most significant bit is
> first sent matters. ...

You're dropping context. A serial stream is considered
bitwise big-endian if the most-significant bit of the
multibit representation of an integer value is transmitted
earliest in time. A serial stream is considered bytewise
big-endian if the most-significant byte of the multibyte
representation of an integer value is transmitted earliest.
A storage organization is considered bytewise big-endian
if it is byte-addressable and the most-significant byte of
the representation of an integer value is stored at the
numerically lowest byte address. In the rare case that a
storage organization is bit-addressable, it is considered
bitwise big-endian if the most significant bit of the
representation of an integer value is stored at the lowest
bit address.

The common thread is that "big endian" means most-
significant portion of a value occurring for smaller
index values for a sequence of those portions. When
there is no particular order established then there
is no particular endianness, as for bits within words
on a computer that doesn't have any instructions that
embed "bit number". (Many such computers do exist.)

> The conventions for the transmission of 8-bit byte
> sequences are usually well established for each type
> of interface.

That is infelicitously worded. What is well established
is the endianness convention for serial transmission of
the integer values represented within octets. For
example, the common "serial port" (e.g. RS-232-C)
specifies that the least-significant bit is transmitted
earliest, and the UART on the receiving end makes use of
that knowledge to reassemble a byte having the same
value as the byte originally serialized by the
transmitting UART.

> Taking both the above together, my interpretation is
> that the common communication protocol guarantees
> correct transport of bytes, leaving the programmer
> the task of taking care of the byte ordering issue,
> which he discusses in some detail. So, assuming that
> your points are right, he must have been wrong
> somewhere. But where? Could you please tell?

Your logic is faulty. The AES implementor does not
*have* to worry about octet order if he has data that
is already organized as a byte sequence, which is in
fact true of almost all data storage and transmission
these days. It is the *user* of the AES API that has
to figure out how to format information within the
message being encrypted by AES. That is an entirely
orthogonal issue, well understood and clearly not
within the *ability* of a generic encryption API to
specify, since it knows nothing about the application.
The AES, or any other block-encryption scheme,
implementation issue on most platforms begins,
"Given a sequence of octet values stored in a block
buffer, ..." *Not* "Given a sequence of bit values."
There are implicitly bit values within those octet
values, but the sequence is not well defined.

> Note that, in another follow-up I questioned whether
> I/O of byte arrays via diskettes could be a problem
> (since there doesn't appear to be an appropriate
> communication protocol involved in such situation).
> Do you happen to have knowledge in that issue?

Yes, we have adequate standards for data exchange as
octet sequences on a variety of media, including 3.5"
diskettes. There is some complication caused by use
of operating-system specific file system organizations
on such media, but these days everybody supports the
most commonly used IBM-PC compatible file system as
well as whatever proprietary system they may prefer.
Sometimes there are official standards, such as an
ISO standard for CD-ROM (unfortunately, supplemented
by a handful of other conventions, e.g. "Rock Ridge")
and an ANSI standard for file-structured magtape. Not
everybody adheres to these standards, which naturally
causes some problems; the problems are especially bad
for "antique" formats from defunct operating systems,
e.g. 20-year old archives. Often there is no longer
any documentation to be found on the old formats.

Relevant Pages

  • Re: Cohens paper on byte order
    ... represented as a sequence of physical bits in the ... the value of the octet, 0xpq, is correctly transported. ... It's available on the internet from NIST. ... > fact true of almost all data storage and transmission ...
    (sci.crypt)
  • Re: Cohens paper on byte order
    ... > indexing to byte sequence indexing, ... > the sequence or altering individual octet values. ... > implementations of AES. ... secifies the order of transmission of the diverse ...
    (sci.crypt)
  • Re: World Moonie Herald: The challenge to Darwins theory of evolution - 5
    ... Denton presented his critique of neo-Darwinism based on the latest ... all types of cytochrome-c is similar and therefore common. ... amino-acid sequence differs according to organisms. ...
    (talk.origins)
  • Re: DNA carries information
    ... And that means that the "fitness" ... Thus "use" the first aspect clearly affects transmission, ... by merely looking at the first, the mere sequence of events ... Here you appear to be confusing "measurements" made by the ...
    (talk.origins)
  • Re: Cantors definition of set
    ... I would not like to say that they have anything in common. ... of the signs we use to portray numbers, ... arranged in a sequence and not numbers after all? ...
    (sci.logic)