Re: Cohen's paper on byte order

From: Eugene Starokoltsev (
Date: 04/13/03

From: (Eugene Starokoltsev)
Date: 13 Apr 2003 04:32:44 -0700

"Brian Gladman" <> wrote in message news:<L7Vla.4213$>...
> "Eugene Starokoltsev" <> wrote in message
> > "Brian Gladman" <> wrote in message
> news:<QoBla.4890$>...
> > > > Neither of them are wrong. Specification is correct. Implementations
> > > > of just AES are correct. As FIPS does not specify how to represent bit
> > > > stream in C functions interface any such implementation is correct
> > > > even it use LSB-first mapping of characters in C interface - the C
> > > > function interface is out of scope of the FIPS clearly.
> > >
> > > I don't think this argument quite holds up. The reason is that the FIPS
> > > actually documents C like pseudo code with this very interface. Hence
> for
> > > this reason. if no other, it should have been documented. At the moment
> the
> > > FIPS implies that 'internal bytes' and 'external octets' are
> structurally
> > > identical in all cases but this is not true in principle (it is true in
> > > practice for all validated AES software implementations)
> >
> > The pseudocode seems to be Pascal ;)
> Its actually derived directly from C code. A few people commented that it
> was too much like C so it was disguised a bit!

Well, I can derive from your words that specification of C language
interface was not a goal of the FIPS writers so it is out of scope of
the FIPS. And formally the FIPS does not define implementation
interface in any language. I agree with you that it would be better if
the FIPS describe the interface of examples better but I do not thing
that this pseudocode requires from the implementers to use the same

But this question is theoreticall only - the mappping from bit string
into internal bytes (which are used in the interface of examples) is
well-specified in the FIPS.

> > Yes, you have pointed me a detail I have missed before. Thank you.
> > I don't think that FIPS implies something about external octets as it
> > does not mention them at all.
> The pseudo code is technically wrong on two counts. First it uses an octet
> interface which is not defined. Secondly its external interface relies on an
> entity called a 'byte' that is only supposed to be defined internaly. This
> is very pedantic but a lot of this discussion is about pedantry!

My opinion is that the pseudocode just do not implements the cipher
completely. It does process the internal-byte array completely but do
not show how external bit stream is mapped into this internal array
and do not show how the result byte block is mapped into bit string.
Of course, if AES implementation external interface uses internal
bytes the mapping is trivial. No matter of the mapping triviality it
is still exists formally but the example does not mention it.

> > While implementations using LSB-first mapping are
> > conformant with FIPS someone needs very serious reasons to write them.
> > It is unlikely that the new implementation will have a mistake about
> > the question as it will be compared with existing implementations
> > first of all. And it is very unlikely that some inexperienced
> > programmer will write a new AES inplementation with incompatible bits
> > mapping instead of using some free existing.
> >
> > So the question is about formal compleetness of specifications only.
> In my view its about an "in principle" tidying up loose ends since the
> external octet interface exists and is very well stadardised in practice
> anyway.

IMHO there is a cluster of cryptographic specifications using bit
strings in interfaces and there is another cluster of communication
protocols using octets as the basic type. To use them together someone
need to specify how communicational octets are mapped into
cryptographic bit strings and vice versa. By tradition they are mapped
MSB-first but it seems that the rule is not well-specified formally. I
do not think that adding the specification into just FIPS-197 will
solver the problem.

> But others consider it to be a practical issue. I am open minded about this
> but find it extremely hard to believe that a bit reversed version could be
> built by accident. I found this very hard to do because deeply inbuilt
> conventions can be used to 'force' assumptions that seem self evident even
> though they are not actually correct - e.g. finite field{0xab} <==>
> Integer{0xab} This was absolutely deliberate in the FIPS since we wanted
> to allow both mappings in principle but effectively rule out the 'incorrect'
> one in practice.

You have succeeded :)
It is not too hard to create LSB-first implementation just by
translating of existing tables accurately but I do not think that
anybody who just need to write AES encryption routines will create
SBox based on it's formal specification and do not compare the result
with the table in the FIPS.

I do not think too that it is a real problem. I agree it would be
useful to add to FIPS-197 _and_ other cryptographic specifications a
_recommendation_ for mapping of octets into bit strings in systems
where octets are a basic communication type but it must not be a
requirement - it must be clear that the basic interface types of AES
are unformatted bit blocks.

BTW I think that FIPS-197 is of an exemplary quality.