Re: Cohen's paper on byte order

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

From: Mok-Kong Shen <mok-kong.shen@t-online.de>
Date: Thu, 24 Apr 2003 11:44:15 +0200

"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > "Douglas A. Gwyn" wrote:
> > > Only in the sense that the I/O mapping is bitwise 1-1 onto,
> > > which allows us to "identify" corresponding external and
> > > internal bits.
> > What do you meant by this?
>
> It's standard mathematical terminology. When an isomorphism
> is established, mathematicians like to use it to "identify"
> corresponding elements as "essentially the same". This is
> important since the elements are in fact *not* "the same".
> A mapping is involved, and it plays a role in the
> identification process.
>
> > If a user has a certain
> > key externally, then it is the programmers's job
> > to have that same key exactly (i.e. semantically
> > identical) in his algorithm/program.
>
> There you go, ignoring the issue. What is "the same" key
> expressed in two different formats, in the absence of a
> known mapping between the domains? There are at least two
> distinct ways the programmer could map between the external
> and internal representations of the key. FIPS-197 does not
> specify (at least, not explicitly and arguably not
> implicitly) what that mapping is when the external
> representation is other than a sequential bit stream.

Look at another standard, the DES document. What
does it say about 'key'? It simply mentions a key
consisting of 64 bits numbered 1 to 64 (with the
parity property which is irrelevant for our discussion).
Is that 'internal' or 'external'? Now AES similarly
specifies a key of 128 bits numbered 0 to 127. Is that
internal or external? It's BOTH internal and external,
isn't it? An inplementation has to transfer that 128
(externally given) bits 'into' the space of the algorithm
and/or program code with one-to-one correspondence,
having the same binary value and the same numerical
tag (i.e. 0-127). It is 'this' that is 'fundamental'
in correctly transferring the key. Do you agree
or do you have different opinions?

Note also that a standard may use different 'notations'
to denote the same thing, not necessarily meaning
different 'formats'. (In memory dumps, one usually
has hex digits, but actually in the memory there
are bits and not the hex digits in ASCII format
on the dump report, which would be 8 bits for each hex.)

Now let's forget about the grouping which the document
has termed 'byte' in order to avoid any 'questionable'
(debatable) relations of that term with octets on the
physical medium. Look at Sec. A.1, where there is

   Cipher Key = 2b 7e 15 16 28 ae ..........

What is 'your' 'interpretation' of this? Doesn't it
mean in another notation

   Cipher Key = 0010 1011 0111 1110 0001 ......... ?

Referring to the above said case of DES 'key', why do
you think that 'Cipher Key' here is 'only' a term for
an 'internal' entitity and not the same as the (same)
'external' entity? If not the same, why exactly
(according to which paragraphs of the document)? Now
look further at what is in the same section:

   w_0 = 2b7e1516

Doesn't this mean

   w_0 = 0010 1011 0111 1110 ?

Now, w_0 is a computer word. So the content above is
'internal', right? The programmer's task here is
simply to take that part (16 bits) of the 'externally'
given key, namely 0010 1011 0111 1110, into w_0, i.e.
put there in the same order (and do the same for the
other parts of the key), neither more nor less! From
'which' sentences of the document (or where indirectly
'in-between' the words of the sentences) have you
read out anything that clearly indicates that in
'transferring' a bit sequence of 128 bit of the key
from external medium to the four words w_0, w_1, w_2
and w_3 one has to 'fiddle' on the way with the bits,
doing swapping of nibbles or other permutations of
the bits?

Given an external bit sequence (each bit as 0/1 in
ASCII) of 0010 1011 0111 1110 0001 ........., is the
task of writing a program to read that input and
obtain four computer words with the contents

   w_0 = 0010 1011 0111 1110

unclear/ambiguious/hard/tricky or not? (I am quite
sure that anybody could do that perperly after one
semester in a course on computer programming.)

Further, Brian Gladman in his follow-up (to me) of
Mon, 21 Apr 2003 09:37:26 +0100 wrote in this connection:

   Yes, this eliminates any second version since a
   cipher key is an external entity applied to the
   key input interface of an algorithm.

He said 'explicitly' that the 'cipher key' is [also]
an 'external' entity. I don't yet see that you found
his opinions to be gravely in error and hence offered
any corrections or counter-arguments to his opinions.
Could you please kindly 'directly' follow-up to his
post now? He has done lots of work on actual software implementation of
AES and was also involved in the
documentation process, if I don't err. So very
certainly you would get good discussions with him on
this very essential point and many readers would
thereby profit from the ensuing discussion results.
(I certainly don't assume that you have any intention
to avoid debating with him on that issue.)

>
> You say it's the programmer's job, but deny him the
> information he needs to do that job. The mapping needs
> a specification.

See what I said above about the easiness/hardness of
the programming task in question.
 
> > Why is any I/O issue relevant here?
>
> How could you possibly not understand that after it
> has been explained so many times? I/O is an issue
> because in practice one must perform I/O in some way
> (function parameters, etc.) to the module that
> implements the AES algorithm. Interoperability
> depends on different implementations performing that
> mapping in compatible ways. Since the mapping is not
> specified, interoperability is not ensured. That is
> a flaw for such a standard.

I/O is 'certainly' an 'important' issue of 'every'
computer program, not only for crypto applications.
In crypto, how about DES in this matter? Wouldn't
your critiques above be 'similarly' applicable to
the DES document? Why not? Does DES standard say
anything about I/O? If one, for example, describes
an algorithm of merge sort, does one also have to
(for the same reasons) include matters about I/O
for the implementor? Why not?

If a programmer succeeds to realize the content
of the four words mentioned above (which is simple
as argued above), then he can correctly proceed
to do further steps of key-scheduling as described
by the algorithm. So where is the problem? If there
were 'any' problems of I/O in getting these four
words as intended by the document, then, as I said
previously 'several' times, that would be a (very)
'general' issue that affects ALL and every computer
program in practice and that 'general' issue
certainly would have to be solved/treated in a
correspondingly 'general' way in a 'general' context
(and in a 'general' standard document) and not in
the 'particular' document of one 'single' crypto
algorithm. Isn't this very clear?

>
> > You argue that what is shown in Sec. A.1 as
> > Cipher Key = 2b 7e 15 16 28 ae ..........
> > denotes an 'internal' entitiy only, right?
>
> Given that the notation used is derived from that
> specified explicitly for internal byte values only,
> and is in fact used for clearly internal-only
> purposes throughout that Appendix and elsewhere in
> the document, surely it is reasonable to infer that
> this usage too refers to the clearly identified
> element that enters as specified into the computation.

Is the hex notation 'reserved' by the document for
application to internal values 'only', i.e. explicitly
forbidden for use on external values?

See my mentioning of DES above. There is only 'one'
key (no swapping/shuffling/permuation of bits)!!

>
> > Now, that internal entity has a representation also
> > as a sequence of 128 bits as numbered in Fig. 2, ...
>
> That particular element will indeed have a corresponding
> set of "input" indexed bits.

When Fig. 2 employs the prefix 'input' in e.g. 'input_0',
Isn't it that that prefix has a certain clear
connotation/meaning? Doesn't the '0' clearly index the
0-th bit of the 'input' 'before' as well as 'after' it
comes into the inside of the algorithm or program code,
i.e. the index is uneffected by the transition?

>
> > ... In my computation it should be ...
>
> I'm not going to check that you properly translated
> hex notation to binary notation. As I have said before,
> *within* the I/O layer there is no issue! There is also
> no issue, for those internal elements that are involved
> in Input/Output, how the internal bit order maps to the
> external bit-sequence indices. You're wasting time even
> discussing this aspect.

You seem to contradict yourself here. If there is
no issue of correspondence of internal bits to the
external bits (as a result of I/O), then changing
the 'notation' into hexs (which the document employs
to simplify its description -- not 'format' conversion
like binary to digigal) should also result in exact
correspondence of the hex digits. So where is then
the problem? Note that the document only says what
is to be done in an abstract sense. How one achieves
that concretely (and correctly) is not prescribed.

>
> > but IS simply the common universal convention of
> > transcribing bit sequences to hexs and vice versa.
>
> Nonsense. There is no common universal convention for
> notating bit sequences within multibit objects. That
> is why the FIPS had to specify its convention *even for
> the internal use that follows the scheme you think is
> universal*. But it clearly adopted a different, bit-
> stream oriented, notation for input/output sequences.

Transcribing a bit sequence of arbitrary length into
the hex notation is 'universal' in CS! The same
denotation is also employed in the language C. Show
references to demonstrate the opposite, e.g. it
may not be applied to a sequnce of 128 bits, if
you can.
 
> > ... So that bit sequence can presently be considered
> > to be external, ...
>
> Why is this helpful? The FIPS provides a clear mapping
> between internal and external bit sequences (involving
> octetwise bit swapping).

Knowing that two (value identical) hex sequence,
one external and one internal, denote two bit sequences,
one external and one internal, that are the same thing
is exactly my point of non-existence of difference
in meaning of hex sequences outside and inside.

Your parentheses above is a (or the) really crucial
point of our debate! 'Where' does FIPS-197 specify
'swapping' of something? I don't see the document
saying anything of that sort!
 
> > ... Now, being external to AES, one can
> > surely apply the universal convention of transcription
> > to hexs.
>
> Even assuming for the sake of argument (but contrary to
> reality) that your notion of that convention is "universal",
> if you do that, you would mandate end-for-end bit swapping
> at the I/O interface, which is not what Brian Gladman says
> is the intention.

No. In my argument there shouldn't be 'any' swapping!
One has on the external medium a sequence of bits
represented as single bits, or more conveniently as
hex digits. One transfers that sequence 'verbatim'
to the space of the algorithm and/or the program code
in exactly the 'same' sequencial order, without any
swapping or permutations! (How many times have I
repeated this?) Inside the program, one may choose
to place the bits into certain groups, e.g. words,
for convenience of processing. But each bit that
comes form outside must have its uniquely identifiable
location, independent of where the implementor
chooses to group the bits. 'Where' does the document
say anything about permutation of bits in this context?
If a document doesn't 'explicitly' say that one has to
perform certain permutation, how do you come up with
the idea of doing any permuation at all? Could you
please explain that?

Look also from another view point. Suppose one chooses
to implement in an inefficient way and let the
program read a user input of 128 bits from a text
file (each bit being represented as an ASCII character)
-- for purposes of stressing, let's consider that
each bit is read in by a separate read statement --
would there 'ever' be problems of internal vs external?
Now change the 'notation', inside according to Fig. 1,
outside according to the (same) universal hex notation.
What comes out from that? Isn't that clear? Is there
any problems of interpreting Sec. A.1 in this situation?

>
> > Could you elaborate your arguments in view of the
> > above? In particular, you said in a previous post
> > about swapping of nibbles, if I don't err.
>
> You err.
>
> > See above.
>
> Do you really think that your continual ploy of pretending
> that you have satisfactorily addressed an issue elsewhere,
> when all you have done is repeat the same questions and
> make the same mistakes over and over, is fooling anybody
> but yourself?

That's instead a very good description of your own
behaviour in this thread, I am afraid!

>
> > No. The 'basic' notion is simply a block of 128 bits
> > that is a 'sequence' and that has a sequential order.
> > This is numbered 0-127 by the standard. Do you agree
> > up till here? So, given such a block of bits externally,
> > one has to (somehow, 'how' exactly I don't care) ...
>
> Yes, indeed. I am convinced that you don't care.

Argue in concrete scientific terms. Vague sentences,
eventually with ambiguious side connotations, are
not appropriate for achieving the real goal of
a debate.

M. K. Shen

Relevant Pages

  • Re: Cohens paper on byte order
    ... > 'perfect bit sequence FIPS'. ... the other interpretation, ... > sequence but as a sequence of pairs of hex digits clearly implies that it is ...
    (sci.crypt)
  • Re: How Chapman-Kolmogorov implies Markov ??
    ... Perhaps the notation "f_i" is supposed to imply there is ... something equivalent about all of these random variables, ... concept, that we index the index set iself, or else write a finite ... sequence in it, explicitly using the integers as our indices. ...
    (sci.physics)
  • Re: [Collatz] was : Re: Status of Waring-problem - Collatz - Sorry
    ... >>From the notation there is no specific restriction on numbers x. ... all depends on the transform structure. ... >for a certain sequence of exponents only one solution for x is possible; ... The slope of the line up to the excursion is steep, ...
    (sci.math)
  • Re: Cohens paper on byte order
    ... > the 2-nybble byte notation specifically in the context of ... > AES internal bytes, ... > sequence, and which therefore does not provide guidance ... notation, obtaining a sequence of hex digits, again ...
    (sci.crypt)
  • Re: Cohens paper on byte order
    ... > conventions used in the FIPS, ... > If the input is truly an indexed bit sequence, ... >> notation, obtaining a sequence of hex digits, again ...
    (sci.crypt)