Re: Cohen's paper on byte order

From: Mok-Kong Shen (mok-kong.shen@t-online.de)
Date: 04/09/03 

From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Date: Wed, 09 Apr 2003 14:07:56 +0200

Brian Gladman wrote:
>
> "Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote:

> > As an addendum to my previous post, I like to mention
> > that the fact that in C one could define a data structure
> > to access the individual bits clearly indicates that
> > the physical bits in hardware has a natural numerical
> > ordering. Therefore in any 8-bit chunk of hardware
> > there is a bit with the lowerest address. This bit is
> > clearly the unique candidate to be designated as the
> > bit 0 of the chunk in my conviction.
>
> Sadly not.
>
> The smallest bit that has an address on most machines is an 8-bit byte.
> Although C bit-fields allow individual bits to be accessed, compiler writers
> are free to define this in any way they choose and this makes it useless for
> interoperability purposes. If we tried to use this meachanism to solve the
> problem we are now debating, I suspect people on both sides of the debate
> would agree that total chaos would ensue.
>
> In principle there are two common ways of identifying bits in registers -
> numbering them or using numeric significance. But these are not always in
> line because some systems number bits from the least significant bit upwards
> while others do so from the most significant bit downwards.
>
> These are both entirely sound ways of identifying bits on an individual
> machine and either could have been used as the basis for exchanging bytes
> (one or the other has to be preserved when moving bytes between machines
> since they cannot both be preserved).
>
> But since the world has agreed (at least for all practical purposes) to
> exchange _bytes_ in a way that preserves numeric significance rather than
> bit numbers, we have to use this approach if we want to exploit the massive
> support there now is for moving bytes in this form between machines.
>
> And this means that _for the purposes of exchanging bytes_ we are better off
> thinking of them as integers rather than as numbered bit sequences.
>
> And this causes a subtle problem for the AES specification. The issue in
> AES is that the _internal_ byte semantics of the algorithm are those of
> finite fields and the bits in this representation do not have numeric
> significance (interestingly, in view of other parts of this debate, they
> could be said to have 'polynomial significance'). And purists (including
> me) will object to any attempt to directly associate numeric properties with
> these internal objects since this might be used by some to imply that these
> objects actually possess such properties.
>
> But there is no difficulty in associating numeric byte semantics with the
> _external_ interface (in addition to what we have now) and this makes a lot
> of sense given the massive support that exists for moving numeric bytes
> around. Hence, in my view, we need a small change in section 3.1 of the
> FIPS.
[snip]

Elaborating a bit a follow-up of mine just sent: If
one pulls a byte somewhere from the memory into, say,
a variable in the program's storage space, there
is one bit among the 8 bits obtained (accssible
through masks) that is (according to the original
location of the chunk in memory) nearer to the lower
end of the whole memory space (according to values
of the addresses of bytes/words) than the others.
This is clearly the low-order bit of the byte and
one gives it the designation bit-0. Similarly one
has bit-1, ... bit-7. Isn't here everything logical,
natural, unambiguious and even 'necessarily' having
to be so from what is actually 'given' physically?
(Could one offer a sensible argument for designating
any other bit as bit-0?) From this, the unique and
unambiguious mapping of the physical byte to the
abstract byte of the AES follows.

Nevertheless, I like to mention that in my view
the AES document does have sort of an aesthetic flaw
which could confuse people (despite its correctness
as I have argued). Note that in Fig.2 of the document
the increasing order of 'input bit sequence' is
the opposite of the increasing order of 'bit numbers
in byte'. If, in place of the Fig. 2, it had defined
the following

  Input bit sequence 0 1 2 3 4 5 6 7 | 8 9 10 .........
  Byte number 0 | 1
  Bit number in byte 0 1 2 3 4 5 6 7 | 0 1 2 ..........

and had clearly explained the 'natural' designation of
bits of a byte in hardware memory as I indicated above
and, perhaps to round up the whole, write the polynomials
also in the form starting with the lowest exponents,
e.g. 1 + x^6 + x^7 in place of x^7 + x^6 + 1, I believe
that much of the confusions and also discussions here
wouldn't have occured.

M. K. Shen
---------------------------------------

[OT: Sentences on the window panels of a restaurant in
 Munich. Authorship unknown. English translation mine.]

Der Menschheit muss dem Krieg | Mankind must put an end
ein Ende setzen oder der Krieg | to war or war will put
setzt der Menschheit ein Ende. | an end to mankind.
                               |
Ich dachte immer, jeder Mensch | I always thought that
sei gegen den Krieg, bis ich | everyone is against war,
herausfand, dass es welche | till I found out, that
gibt, die nicht hingehen | there are some who needn't
muessen. | go into it.

Relevant Pages

  • Re: Future proofing a system
    ... a quad running at 3.66GHz. ... the expensive machines have gaming video cards in them ... 2GB memory minimum. ... add upgrades to later). ...
    (alt.comp.hardware.pc-homebuilt)
  • Re: 54 Processors?
    ... > My memory is cloudy but I seem to recall these statements around the ... a big problem was strong memory consistency model and cache ... were saturating their machines ... ... the common L2 cache interfaced to the SCI memory access port. ...
    (bit.listserv.ibm-main)
  • Re: Working without a Word work file - Word 2003 / Outlook 2003
    ... Increased the memory on the server to 3gb and defragged ... Deleted the DataKey on the machines and the problem continued. ... and not do a bog standard install and use redirect to correct the ...
    (microsoft.public.word.application.errors)
  • [PATCH] trim memory not covered by WB MTRRs
    ... On some machines, buggy BIOSes don't properly setup WB MTRRs to ... of memory will be marked uncached. ... int i, max; ...
    (Linux-Kernel)
  • Red X on Computers in AD
    ... What does the Red X that shows up on some computers symbolize in Active ... Active Directory and I would like to delete these machines to clean up. ... Does anyone know how this Red X designation is determined by Active ... I don't want to delete machine accounts thinking that they are ...
    (microsoft.public.windowsxp.security_admin)