Re: Cohen's paper on byte order

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

Date: Mon, 21 Apr 2003 03:44:41 -0400
From: "Douglas A. Gwyn" <DAGwyn@null.net>

Brian Gladman wrote:
> In the absense of a demonstration by you of such a version, it seems that we
> have to allow others who are following this thread to judge for themselves
> which of our respective claims is the more credible one.

Now you're clearly resorting to sophistry. It is trivial
to convert any, for example your, implementation into the
alternative case:
        uint8_t input_byte() {
                uint8_t x = input_byte_Gladman();
                x = bit_reverse(x);
        }
etc. If the Gladman code already has an explicit bit-
reversal phase, then an equivalent to the above could be
coded more directly using simpler code than Gladman's.
Otherwise, it is a straightforward interpretation of what
Figure 2 and associated definitions in FIPS-197 seem to
be trying to say, according to one reasonable attempt to
guess what should be done.

It should have been clear all along that "to bit-reverse
or not to bit-reverse, that is the question". I am not
the first to raise this question. Originally you and
others were arguing that it was deliberately left
unspecified, and that that was a highly desirable and
intentional feature of FIPS-197. Recently you have
changed your tune and are claiming that the question has
an obvious answer (I wish I knew what) that can be obtained
by some sort of gestalt divination process applied to the
specification. But to me the very clear and explict
refusal of the specification to address the issue, which
I have agreed all along was an intentional decision made
during the production of FIPS-197, trumps whatever you
think can be intuited from "the standard as a whole".
Nothing in the whole standard appears to me to try to talk
about external data structure other than bit stream, which
agrees with what you were originally saying about it. In
fact, if your claims that it really *is* talking about
external data as 8-bit numerically valued units is correct,
then there is a serious logical flaw since that would
render the FIPS inapplicable to inherently bit-stream and
other non-8-bit data environments. I suspect *some*body
else involved in the process should object to saying that
FIPS-197 is intended to apply only when external data
has an 8-bit binary numeration interpretation imposed on
it. Frankly, I have trouble believing that anyone with
even modest qualifications who carefully reads FIPS-197
could possibly think that that is the intention of its
wording.

> The term 'test vectors' is normally used to describe the set of vectors that
> are external to the FIPS but which are used to test the validity of AES
> implementations.

You can use words as you will, but that doesn't reflect one
way or another upon the way similar words were used within
the specification document.

> You have used the term in this sense in previous posts,
> stressing that you do not consider these to be a part of the FIPS. But it
> now seems that you wish to change your mind and accept after all that the
> FIPS does include test vectors.

There are test vectors, both of a kind that clearly cannot
refer to external octet values and of a kind that could
(conceivably), in appendices to FIPS-197. I'm not sure
whether these are considered normative, but in any event
the clear intent is for use in checking that one's
understanding or implementation of the calculation (key
scheduling, etc.). It is quite likely that some not-very-
careful implementors think that the test vectors that are
close to the I/O interface should have the same numeric
byte values as external data. But the associated
nomenclature and symbols were rather clearly established
earlier in FIPS-197 as pertaining solely to internal byte
values, *and this is appropriate for expresing these
internal register values*. (If somebody computed the test
vectors involving a bit-swap, then it was a screw-up not
to re-swap the bits when embedding them in the standard as
internal values.)

> This is good news since some of the 'test vectors' in the
> FIPS are expressed (in error) as byte arrays.

I don't see that as an error. That's in fact what should
be used ("byte" is the defined term for *internal* 8-bit
organization expressed using the nybble notation that is
also spelled out as part of the specification).

> Moreover the FIPS includes the byte array external
> interface that is used by all software implementations.

Please point me to the relevant section/paragraph, as I
did not see it in the copy of the FIPS I downloaded from
NIST. (If you're referring to the paragraphs near Figure
2, they emphatically do *not* refer to external byte
organization; to the contrary it is made quite clear
that external data is represented only as indexed streams
of bit values.)

> And all reasonable interpretations of these test vectors
> is that they are byte arrays applied at the external byte
> array interface of an AES implementation.

That's simply inconsistent with the FIPS's very denial of
any external data organization other than the bit stream.
And it is certainly reasonable to think that the
nomenclature and symbols specifically *defined* in the
specification as pertaining to data *only* inside the
I/O layer, pertains to data inside the I/O layer. Why
is it reasonable to think otherwise? Did they really
publish bit-reversed values that do not work if used at
as internal defined-"byte" values? If so, what the heck
did they do with the values of the *scheduled key* in the
first of the two test=vector appendices? Since those
values are certainly internal, are they expressed with
bits reversed compared to the clear description (early
in the FIPS) of how to interpret the nybble values as
individual bits within internal bytes? If so, I would
(finally) concede that the test-vectors values imply a
particular answer to the original external bit-order-
within-octet question, but only in a most erroneous
manner, and one that is an inappropriately obscure way
to mandate a crucial aspect of implementations in an
octet-organized external environment. If not, your
argument is either patently wrong or else would imply
that the top (external data) row Figure 2 assigns bit
numbers to external octet bits but makes no use of
those bit numbers, more specifically the reversal of
order shown patently by Figure 2 means nothing. One
would perhaps wonder why in a true bit-stream
environment the bits have to be swapped within each
successive group of 8; it's hard to imagine that there
is a purpose to that clear requirement if that is what
it means. Would you call it "reasonable" nonetheless?

> I know of only one person who might perversely claim that
> the cipher key is not an external input to an encryption algorithm.

I neither said that, nor is it germane. The internal
values obtained by key scheduling, to which I *did*
refer, are clearly internally generated.

> But this is only the most obvious way in which the FIPS eliminates your
> mytical alternative AES version. It turns out that there are other
> surprising inconsistencies - ones that I would not have expected. I only
> discovered these on running the 'other' version and I am NOT going to say
> what they are (but they have nothing to do with figure 2).

Who is being mystical here??

> I am not relying on figure 2.

And you're not saying *what* you're relying on, just
"the standard as a whole". I read the whole standard
and I don't see what you claim to see.

> The wrong version can be made into the right version
> by externally reversing the bit order in bytes in all
> inputs and outputs.

If there were a clear "right" version. Sure, the
difference under discussion concerns solely the order
of bits within each external octet.

> In consequence once 'b' has been bit reversed it will
> become 'F'.

I now see that you must mean the ASCII code values for
those characters. Sure, there is no misunderstanding
of what it means to reverse a sequence of 8 bits.

> My view of this is that this version cannot
> be produced accidently and that anyone who produces it
> deliberately without documenting its special character
> would be acting in a highly irresponsible way.

I have carefully explained the exact way in which FIPS-197
intentionally omits specification of the organization of
external data bits within external octets (where they
exist, which is certainly not every context in which
FIPS-197 can be expected to be used). I have also shown
how an implementor could allow his guess at a reasonable
order to be influenced by the FIPS in various ways (such
as that Figure 2 requires a bit reversal and that the
test vectors refer to what the notation and context make
it appear that they refer to, which is indeed what they
should refer to). But since there is deliberately no
specification given by FIPS-197 for this mapping, any
attempt to devise one *is* guesswork. One's guess may
turn out to be interoperable with other implementations
or not.

> I do not believe that anyone has produced such a version
> with the intent that it should be offerred for use.

We heard some time ago from a fellow who had difficulty
on this very score, which he presumably resolved not by
an understanding of what FIPS-197 requires but rather by
changing his implementation to match yours. Since your
guidance on bit reversal has in this thread gone both
ways, I still have no clear guidance about which way
you chose. I can figure it out by studying your code,
but is *that* any way to run a standard?? And why is
everybody supposed to do it your way? The standard
clearly punts on the matter; who made you king?

> there would be any market for such a version if someone did produce it. In
> consequence, in my view, your 'problem' is of no practical concern
> whatsoever.

My implementation, for example, would not be put on the
market, but at some significantly later date it is likely
to be connected to other AES implementations. An
interoperability problem found at that time will have
extremely expensive consequences. Again, is this any
way to run a standard?

The standard is deficient in this regard. It needs
official correction or augmentation to provide the
missing specification for octet-stream oriented
environments (which means most of the computing world).

Interoperability depends on this. How is that not of
practical concern?

> I choose the bit order for the AES byte array interface
> that maps the external integer byte 0xpq (p and q hex
> digits) to the internal finite field element {pq}.

Okay, that might agree with MKS's notion. So tell me
what the bytewise bit reversal indicated in Figure 2
is supposed to be about. You bypassed it altogether,
apparently. That might be reasonable given that there
is already a byte-clumping data organization in the
environment, and it affirms that the test vectors
really *are* the internal byte values (no bit swapping).
However, the whole bit-reversal phase, which is
explicitly specified, then makes no sense. Affecting
at most only bit-stream environments, why not copy the
external bits into internal bits in the sequence used
in numbering the internal bits? One might, as yet one
more *guess*, think that perhaps this is an artifact of
some earlier draft (Rijndael) that used the opposite
numbering convention. Or, perhaps, again *guessing*,
perhaps there was some early bit-stream implementation
for which AES operability was considered desirable.
But really, how is one to guess that your approach is
the proper one when it raises this natural puzzlement?
It is certainly less puzzling to me to guess that the
explicit octet-wise bit reversal means to actually
perform one. (The only puzzle then is why that was
specified; I've already indicated analogy with another
similar puzzline specification for which there were
valid although obscure reasons, so one might not be
too bothered by this particular puzzle.)

> In discussions of this issue you have said (more than once now) that what
> really concerns you is a change (in your view) in the goal of the AES and/or
> the AES-FIPS development process while it was underway. But, so far, you
> have not shared these wider concerns with the rest of us in specific terms.

Sure I have. The proper, and generally understood
among people I work with, intent of the AES FIPS was to
produce a good specification for a block-encryption
algorithm to be used in contexts where DES might have
been appropriate, with the expectation that multiple
parties conforming to the specification would be able
to communicate with AES privacy protection (using some
specific mode of operation). Obviously there are
matters of key exchange, etc., but the role of AES was
to be a plug-in module to encrypt and decrypt data
blocks symmetrically using agreed keys, such that the
decrypted data would be identical to the original data.

The original Rijndael submission, which so far as I am
aware may have had portability flaws as originally
specified, still appeared to be mapping blocks of
octet values, which had clear meaning for implementation
(the "I/O/key" octet values would be those of the bytes
as used in actual [external] data). In the course of
evlving Rijndael into FIPS-197, a big deal was made,
perhaps correctly, of needing to improve the spec by
abstracting away from the original direct connection
with octet-organized actual data. This would be
appropriate, for example, to fit the algorithm to non-
octet organized data so long as a clear bit sequence
could be specified or inferred. (For bit streams that
is easy!) But much of the public explanation did not
mention practical reasons for the abstraction, but
instead stated the purely pedantic reason that the
algorithm should be expressed in terms of finite field
elements rather than numeric values. By the time the
FIPS was published, it nevertheless imposed its own
internal numeric values upon the finite-field element
representations ("bytes"). The FIPS also had adopted
a precise I/O model wherein external data was treated
*only* in terms of an indexed sequence of bits, with
no guidance as to how a user of the spec should index
bits in a non-bit stream environment. Clearly, in the
process of abstracting away from connection with
external octet-organized bit sets each treated as a
finite-field element in the computation, to external
individual bits with assembly into field elements
explicitly specified, something important got lost.
Therefore it is appropriate to associate the problem
that was introduced with that process of changing the
way the algorithm was specified.

> It is hence possible, in my view, that you are using
> the issue being discussed here as a surrogate for
> more deep rooted issues that you are are not willing
> to share with us.

No, I have told you (again) that that is not the case.
An important piece of specification is missing from
the FIPS as published. I want that piece supplied
(you could say "restored"). The missing piece is a
logical requirement for anybody working from the FIPS
to produce a conforming implementation. Some have
argued that the missing piece *should not* be
specified. Since that would not meet the original
goal of interoperability that was supposed to be
provided by this standard, that is unacceptable.

In fact I myself am not convinced that I will not
encounter interoperability problems when my own
implementation bumps into that of somebody else
who has applied his own reasonable interpretation
of what FIS-197 seems to expect him to do. This
is true whether or not I make my implementation
match yours. This is an unacceptable situation
for such a standard. It should be easily
correctable. (If it were the C standard, we'd
quickly reach a working-group consensus on the
intent and prepare wording for a Technical
Corrigendum, or at worst an explanatory response
to the Defect Report, all of which would be
published even in draft form on our official Web
site, as guidance for implementors and programmers
who run into the issue.)

Any more talk about a hidden agenda and I'll have
to wonder about yours.

> Accordingly I won't be supporting any changes
> (or augmentation) of the AES-FIPS that are promoted
> by you until I better understand your wider
> concerns in more specific terms.

Since those "wider concerns" are a figment of your
imagination, there is no possibility of you better
understanding them. They don't exist!

> I do not consider you to be a liar. But I no
> longer consider your position on this issue to
> have any credibility.

What have I said that is unreasonable?
I get the impression that your complaint with me is
that I have identified a problem in a part of the
specification that you appear to have contributed to.
Believe me, I've been in that position myself in
connection with the C standard. Sometimes there is
a real problem for a reasonable reader of a spec,
and impugning the credibility of the messenger who
pointed it out is no substitute for fixing the
problem. This is not a case (which does occur,
way too frequently in my C standards experience) of
somebody nit-picking an inconsequential flaw for
the purpose of advertising how much smarter he is
than the people who did the real work. This is a
case of a very real gap in a specification, which
interferes in a very real way with proper use of an
important information-interchange standard, and has
potential adverse economic impact (in several ways).
Why in the world would one not fix this? Why is a
request that it be fixed not credible?

Relevant Pages

  • Re: Cohens paper on byte order
    ... I'm not sure that "ambiguous in a way that prevents interoperability" ... is a thing it would make sense to say about the AES FIPS. ... You could say it about, say, a standard for USB nose hair trimmer ...
    (sci.crypt)
  • Re: Cohens paper on byte order
    ... NIST - implements AES in accrdance with the FIPS specification! ... byte array interface, in principle, we then have two non-interoperable ... there is a really good chance that this will set a wider standard. ...
    (sci.crypt)
  • Re: Cohens paper on byte order
    ... I have given my reasons clearly in several ... > NIST - implements AES in accrdance with the FIPS specification! ... code standard. ...
    (sci.crypt)
  • Re: A new paradigm
    ... First I use a 3rd party btree handler for several reasons - cross platform ... Therefore all our programs use a standard common area ... but no one in the rest of the market seemed interested. ... people just shifting where they're buying their features and support ...
    (comp.databases.pick)
  • Re: Cohens paper on byte order
    ... > Why not make manufacturer t's depiction look like this: ... between different hardware. ... and as such is NOT in the proper domain of AES. ... > for this in the AES standard. ...
    (sci.crypt)