Re: Cohen's paper on byte order
From: Mok-Kong Shen (firstname.lastname@example.org)
From: Mok-Kong Shen <email@example.com> Date: Tue, 15 Apr 2003 23:58:46 +0200
Eugene Starokoltsev wrote:
> Mok-Kong Shen <firstname.lastname@example.org> wrote:
> > Eugene Starokoltsev wrote:
> > >
> > > reMok-Kong Shen <email@example.com> wrote:
> > > > Brian Gladman wrote:
> > > > > The problem is a rather technical one about abstraction. As written the
> > > > > entity called a 'byte' is only strictly defined internally ( ...Bytes _in_
> > > > > AES ...) but the interface makes this internal entity visible externally.
> > > >
> > > > Fig. 2 of FIPS-197 defines the relation of the
> > > > 128 (abstract) bits to the (abstract) bytes. If an
> > > > implementation were (I don't think any real implementation
> > > > does that) to use a bit arrary to realize the algorithm,
> > > > then there would certainly be no interface problem.
> > > > What one has to do in the real-life case of using
> > > > octets (simply a precise term for 8-bit bytes) on
> > > > external medium is to have a fixed correspondence
> > > > (mapping) between a (physical) octet and an abstract
> > > > byte of the AES document. But then isn't it
> > > > self-evident that an array of octets with increasing
> > > > indices should correspond to the 16 (abstract) bytes
> > > > of AES with increasing numbers? (True, the document
> > > > doesn't explicitly say that, but wouldn't a specific
> > > > mentioning of that be unnecessary pedantry? One
> > > > would certainly also not mention there e.g. that in
> > > > numerical computations the Peano Axioms are assumed,
> > > > would one?) The AES byte has bit number 0 on the
> > > > right side, in conformity with the common convention
> > > > of writing a binary number. For the octet, it is
> > > > (according to a post of Olson, among others) an
> > > > integer. An integer must have (somewhere) a least
> > > > significant bit. That bit evidently corresponds
> > > > to bit number 0 of the AES document. Any other
> > > > correspondences would be fancy, weird, artificial,
> > > > unreasonalbe and hence is invalid in my conviction.
> > > > Note that this argument does not even marginally
> > > > touch the question of how the hardware stores the
> > > > 8 bits of an octet in their positions with respect
> > > > to one another. (It could distribute them in any
> > > > way it likes, provided that on access it delivers
> > > > the said integer in [0, 255] and consequently one
> > > > could use an appropriate mask to access e.g. the
> > > > LSB of it.) When such an octet is transmitted from
> > > > one machine to another of different architecture,
> > > > the transport protocol should bother to ensure that
> > > > the octet arrived and stored on the target machine
> > > > would deliver the same integer as on the source
> > > > machine, thus preserving the information content.
> > > > But that's the business of the transmission protocol
> > > > and transferring a text file would 'in general' have
> > > > the 'same' issue to be taken into consideration.
> > > > If there is defect in such transmission protocol
> > > > (I don't know, but I don't think so), the remedy
> > > > should be done there, not in AES.
> > > [snip]
> > >
> > > You would be right if AES does specify identity of AES internal bytes
> > > and external octets.
> > >
> > > We discuss formal aspects of the problem there so your argumentation
> > > about self-evidence is not relevant for the question. Other mappings
> > > are allowed by the specification while you think they are
> > > unreasonalbe. But as it does natural to identify bytes stored in RAM
> > > with internal AES bytes _if_ the opposite is not specified there is no
> > > problems with real AES implementations.
> > >
> > > I know at least one system storing plain bit stream (having no meaning
> > > for the system itself) in memory array starting from LSB of the byte
> > > with the lowest address and transmitting it by a specialized serial
> > > link. If somebody adds an encryption of the bit stream to the system
> > > (I don't think anybody needs, but what if), which mapping of memory
> > > bytes into AES bit stream should he/she use?
> > Certainly 'other' mappings could be allowed, if the
> > implementor cares to preserve the same 'semantics'
> > and hence obtain the same results of encryption
> > and decryption. (How to do this is then his 'job'.)
> > The point was that there 'IS' one natural way to do
> > the processing. So why would one not follow that?
> > (Analogy: By train one normally travels directly
> > from Munich to Vienna. But it is certainly possible
> > (allowed) to go first to Paris, then over Zurich,
> > Rome to Vienna. But isn't the 'natural' route to be
> > preferred at least in some sense?)
> Could you please define a meaning of term 'semantics' you use? I
> suspect there is no easy answer to this question (while most of
> programmers understand what semantics is).
By semantics I meant the 'meaning'. Now what meaning
do the 8 bits in an octet have? They have each a
value individually (0/1) and they have collectively a
value, an integer in the interval [0,255]. This is
why people have claimed that an octet IS an integer.
So a byte in the AES document has an integer value.
As long as that value is retained, it is immaterial
how one has realized it physically for the algorithm
AES as such. For example, I could let bit 0 of byte 0
of AES be represented by a two-byte integer at
address 1234 and let bit 1 of byte 0 be represented
by another two-byte integer at address 5678, etc.
Of course, one wouldn't do that in practice. But
that illustrates what I meant.
> If you say "'other' mappings could be allowed" this mean that you
> agree that the standard can't specify (require) some specific mapping.
> It can _recommend_ it at maximum.
It specifies one unique 'meaning' of the algorithm.
If you are 'able' to implement (realize) that same
meaning in many different ways, then very fine. But
if you don't preserve that (standard) meaning, then
that's your error.
> Your analogy is unclear. IMHO analogies are good for teaching physics
> but are bad for analysis of logical systems where accuracy is
> > Please see also the other follow-up to you, sent
> > simultaneously with the present one.
> The thread is so big now that it's hard to follow all posts. I have
> answered a few yours. If I've missed some still - please give a URL on
> BTW I think I see what you misunderstand (that's my opinion only, of
> course). You think that as MSB-first bit mapping is used most widely
> nobody needs to specify it, don't you? That's a mistake. If another
> mapping is used at least sometimes by computer engineers this mapping
> is not a notorious fact. So it must be specified somethere in
> specifications related to integration of encryption functionality into
> communication protocols.
If you agree that an octet is an integer (if you
don't please say so), then it has an MSB and LSB.
When written on paper, the common convention is that
the MSB is on the left and that's what one consider
to be 'first'. Note that, if you hold that piece of
paper and look from the other side, then that same
MSB will appear on the right and would be 'last'. So
I like to consider instead an octet to be a bunch of
bits that the hardware interprets them collectively
as an integer in [0, 255] such that the bit having
the significance of 2^i is designated as the i-th
bit. This obviates the necessity of considering
first/last and left/right. Do you think that's o.k.?
M. K. Shen