Arrg Cryptographers are not good coders!
Tom St Denis
I've been trying to find some portable code for IDEA.... not a happening
thing. Even the IDEA "paper" from Media-crypt doesn't specify things like
which endianess to use. Their example code isn't even portable since it
just blindly loads values like
unsigned short x = (unsigned short *buf)[0];
etc....
I had a similar experience with the Blowfish [and all of the AES
submissions, and most of Gladman's code] from counterpane.
Is it just me or is every cipher designer inventign their own coding
standards and calling conventions? Alot of people using random cryptic
typedefs, wierd
indentation styles, often they don't think to put the key in a structure and
blindly accept
encrypt(unsigned short *pt, unsigned short *ct, unsigned short *keys)
as a valid and useful calling convention.... For the most part IDEA looks
simple to implement [except the inverse key schedule might be tricky...].
Could someone please tell me which endianess it uses? My hunch is that its
little endian like the x86 series...
Thanks,
Tom
Bryan Olson
Tom St Denis wrote:
> I think I'm going to write a book on this one.
>
> I've been trying to find some portable code for IDEA.... not a happening
> thing. Even the IDEA "paper" from Media-crypt doesn't specify things
like
> which endianess to use. Their example code isn't even portable since it
> just blindly loads values like
>
> unsigned short x = (unsigned short *buf)[0];
>
> etc....
>
> I had a similar experience with the Blowfish [and all of the AES
> submissions, and most of Gladman's code] from counterpane.
Uh, Tom, didn't you release endian-dependent Blowfish code in your CB
toolkit? You know a lot more today than you did back then. No question
about it: your programming skills are far beyond what I'd expect from a
first semester CS student. By the time you graduate, you'll be far
better still. You've always been a fast learner, provided someone can
convince you there something you don't know.
> Is it just me or is every cipher designer inventign their own coding
> standards and calling conventions? Alot of people using random cryptic
> typedefs,
Tom, you didn't use typedef at all in your latest code release. Of
course it'll be cryptic if you don't really understand it.
> wierd indentation styles
You have a 322-character-long line in your mycrypt.h file, and in other
files you have lines that practically scream to be split.
Then again, I've seen worse code, some written by professionals. No one
expects a freshman to know what declarations are better typedef'ed and
exactly what should be declared const. For a library designer, those
things should be too basic to mention. And maybe hold off on that book.
> as a valid and useful calling convention.... For the most part IDEA
looks
> simple to implement [except the inverse key schedule might be tricky...].
> Could someone please tell me which endianess it uses? My hunch is
that its
> little endian like the x86 series...
Actually it's big-endian. You're right that the specifications are poor.
--Bryan
Tom St Denis
"Bryan Olson" <non...@nowhere.org> wrote in message
news:3C282366...@nowhere.org...
>
> Tom St Denis wrote:
>
> > I think I'm going to write a book on this one.
> >
> > I've been trying to find some portable code for IDEA.... not a
happening
> > thing. Even the IDEA "paper" from Media-crypt doesn't specify things
> like
> > which endianess to use. Their example code isn't even portable since
it
> > just blindly loads values like
> >
> > unsigned short x = (unsigned short *buf)[0];
> >
> > etc....
> >
> > I had a similar experience with the Blowfish [and all of the AES
> > submissions, and most of Gladman's code] from counterpane.
>
> Uh, Tom, didn't you release endian-dependent Blowfish code in your CB
> toolkit? You know a lot more today than you did back then. No question
> about it: your programming skills are far beyond what I'd expect from a
> first semester CS student. By the time you graduate, you'll be far
> better still. You've always been a fast learner, provided someone can
> convince you there something you don't know.
You're right I have improved and yes often I need someone to show me the
light [so to speak...]
> > Is it just me or is every cipher designer inventign their own coding
> > standards and calling conventions? Alot of people using random cryptic
> > typedefs,
>
> Tom, you didn't use typedef at all in your latest code release. Of
> course it'll be cryptic if you don't really understand it.
I know what typedef is, I just don't want to use it because its annoying
[annoying == tom has todo work].
I think for the next release I will fix that. That means the API will
change and the manual will have to be editted...
> > wierd indentation styles
>
> You have a 322-character-long line in your mycrypt.h file, and in other
> files you have lines that practically scream to be split.
You're not supposed to look at mycrypt.h... :-) that's what crypt.pdf is
for!
> Then again, I've seen worse code, some written by professionals. No one
> expects a freshman to know what declarations are better typedef'ed and
> exactly what should be declared const. For a library designer, those
> things should be too basic to mention. And maybe hold off on that book.
> > as a valid and useful calling convention.... For the most part IDEA
> looks
> > simple to implement [except the inverse key schedule might be
tricky...].
> > Could someone please tell me which endianess it uses? My hunch is
> that its
> > little endian like the x86 series...
>
> Actually it's big-endian. You're right that the specifications are poor.
Oh ok. Thanks.
Tom
Douglas A. Gwyn
> I know what typedef is, I just don't want to use it because
> its annoying
If you think that then you don't really grok typedef.
Tom St Denis
"Douglas A. Gwyn" <DAG...@null.net> wrote in message
news:3C294198...@null.net...
[hint: I've ported my library over to a typedef version....I heed your
suggestions!]
Tom
Anish
I am sorry but I dont think I could agree to the fact totally
.Cryptographers have excellent logic :-) I am sure no one has doubts
on that .As for there coding skills the only reason why they wont be
interested would be the fact that once some one could put down things
as an algo there are lot of people around who could code .
In industry those of them who implement crypto primitives are
usually called security engineers...
Anish
Brian Gladman
news:L7PV7.116667$KT.29...@news4.rdc1.on.home.com...
> I think I'm going to write a book on this one.
>
> I've been trying to find some portable code for IDEA.... not a happening
> thing. Even the IDEA "paper" from Media-crypt doesn't specify things like
> which endianess to use. Their example code isn't even portable since it
> just blindly loads values like
>
> unsigned short x = (unsigned short *buf)[0];
>
> etc....
>
> I had a similar experience with the Blowfish [and all of the AES
> submissions, and most of Gladman's code] from counterpane.
My code for the 15 original AES algorithms did not handle endian issues well
simply because a significant number of the original cipher specifications
were ambiguous or even wrong in their descriptions of such details. Hence
this was not a coding problem as such but rather a specification problem,
one on which I provided a paper for the AES effort.
> Is it just me or is every cipher designer inventign their own coding
> standards and calling conventions? Alot of people using random cryptic
> typedefs, wierd
> indentation styles, often they don't think to put the key in a structure
and
> blindly accept
In my view it is inevitable that there will be many conventions, the real
issue not being one of trying to limit what people do but rather one of
getting them to document the interfaces that they do use in an unambiguous
and complete way.
Fortunately AES (Rijndael) is completely byte oriented (even though the FIPS
specification is not quite so) and this means that it is much easier to
avoid endian issues by using byte arrays at its external interfaces.
But even in Rijndael there are some subtle issues since the two critical
enumerations - the enumeration of bits within bytes and the enumeration of
bytes within arrays of bytes - are often implicitly assumed to be those of
the processor on which the code will run but this is not necessarily the
case.
Brian Gladman
Douglas A. Gwyn
> But even in Rijndael there are some subtle issues since the two
> critical enumerations - the enumeration of bits within bytes and
> the enumeration of bytes within arrays of bytes - are often
> implicitly assumed to be those of the processor on which the code
> will run but this is not necessarily the case.
The specification (of AES) should not use "bit numbers" without
first explaining the convention. Having done so, any implementation
in C will work unchanged on any platform (so far as this issue goes).
#define BIT(i) (1<<(i)) /* or (1<<(7-(i))) depending on the spec */
If the AES specification is really byte (octet) oriented, then there
is no platform dependence due to designation of array members:
In C, a[i] selects byte number i from the array designated by a.
Brian Gladman
> Brian Gladman wrote:
> > But even in Rijndael there are some subtle issues since the two
> > critical enumerations - the enumeration of bits within bytes and
> > the enumeration of bytes within arrays of bytes - are often
> > implicitly assumed to be those of the processor on which the code
> > will run but this is not necessarily the case.
>
> The specification (of AES) should not use "bit numbers" without
> first explaining the convention.
I agree. And a real implementation should then document how it maps these
abstract 'aes bits' to the 'real world bits' that it uses to represent them.
> Having done so, any implementation
> in C will work unchanged on any platform (so far as this issue goes).
> #define BIT(i) (1<<(i)) /* or (1<<(7-(i))) depending on the spec */
In fact either can be used irrespective of the specification since the
mapping of 'AES bits' to 'C bits' (or to 'machine bits') is not defined in
the FIPS.
It might be considered perverse to map bits in anything but the 'obvious'
way but alternative mappings cannot be described as incorrect since the
specification does not prevent these from being used (or even require that
they should be defined in any implementation).
> If the AES specification is really byte (octet) oriented, then there
> is no platform dependence due to designation of array members:
> In C, a[i] selects byte number i from the array designated by a.
This should be true if the implementor uses the 'obvious' mapping. However
they are free to do otherwise if they wish.
My experience with specifications for defence software has convinced me that
relying on implicit assumptions (e.g. everyone is mapping aes_byte[i] to
c_byte[i] because this is the 'obvious' thing to do) can be extremely
hazardous.
Brian Gladman
Mok-Kong Shen
Brian Gladman wrote:
>
> My experience with specifications for defence software has convinced me that
> relying on implicit assumptions (e.g. everyone is mapping aes_byte[i] to
> c_byte[i] because this is the 'obvious' thing to do) can be extremely
> hazardous.
Very true. One should never 'interpret' standards in
the sense pieces of music are being interpreted.
M. K. Shen
John E. Gwyn family
> "Douglas A. Gwyn" <DAG...@null.net> wrote...
> > The specification (of AES) should not use "bit numbers" without
> > first explaining the convention.
> I agree. And a real implementation should then document how it maps
> these abstract 'aes bits' to the 'real world bits' that it uses to
> represent them.
I disagree. The whole point of AES explaining the convention is so
that it is not necessary to establish a second mapping. If, for
example, "bit number 0 shall mean the least significant bit of the
octet", then no further specification is needed; in C one can
c = getc();
if (c & 1)
... // least significant bit (AES 0) was set
> > In C, a[i] selects byte number i from the array designated by a.
> This should be true if the implementor uses the 'obvious' mapping.
> However they are free to do otherwise if they wish.
No, they are not free to do so; it would not conform to the standard.
SCOTT19U.ZIP_GUY
<3C2CC704...@compuserve.com>:
>Brian Gladman wrote:
>> "Douglas A. Gwyn" <DAG...@null.net> wrote...
>> > The specification (of AES) should not use "bit numbers" without
>> > first explaining the convention.
>> I agree. And a real implementation should then document how it maps
>> these abstract 'aes bits' to the 'real world bits' that it uses to
>> represent them.
>
>I disagree. The whole point of AES explaining the convention is so
>that it is not necessary to establish a second mapping. If, for
>example, "bit number 0 shall mean the least significant bit of the
>octet", then no further specification is needed; in C one can
> c = getc();
> if (c & 1)
> ... // least significant bit (AES 0) was set
Depends on the defination of octet. Is the least significant bit
on the left side or the right side? Are you think of numbers
as two complement or ones complement?
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Crypto code http://radiusnet.net/crypto/archive/scott/
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
Tom St Denis
"SCOTT19U.ZIP_GUY" <david_...@emailv.com> wrote in message
news:918570DFBH110W...@207.126.101.92...
> JEG...@compuserve.com (John E. Gwyn family) wrote in
> <3C2CC704...@compuserve.com>:
>
> >Brian Gladman wrote:
> >> "Douglas A. Gwyn" <DAG...@null.net> wrote...
> >> > The specification (of AES) should not use "bit numbers" without
> >> > first explaining the convention.
> >> I agree. And a real implementation should then document how it maps
> >> these abstract 'aes bits' to the 'real world bits' that it uses to
> >> represent them.
> >
> >I disagree. The whole point of AES explaining the convention is so
> >that it is not necessary to establish a second mapping. If, for
> >example, "bit number 0 shall mean the least significant bit of the
> >octet", then no further specification is needed; in C one can
> > c = getc();
> > if (c & 1)
> > ... // least significant bit (AES 0) was set
>
>
> Depends on the defination of octet. Is the least significant bit
> on the left side or the right side? Are you think of numbers
> as two complement or ones complement?
Endianess only applies to byte order ...
0x12345678
is
78 56 34 12 on a x86
and
12 34 56 78 on a 68K
Bit zero [the lsb] is the same for both platforms [and please don't anybody
quote some 40 yr old computer that nobody in their right mind would use that
loads the bits in some esoteric order like 3 7 4 1 2 5 0 6 because that's
just useless trivia]
Tom
John E. Gwyn family
> Depends on the defination of octet. Is the least significant bit
> on the left side or the right side? Are you think of numbers
> as two complement or ones complement?
No, it does not depend. The least-significant bit has value 1.
"Left" and "right" are irrelevant since they depend on how you
draw the pictures. Also, representation is irrelevant since C
allows only twos-complement, ones-complement, or sign-magnitude
representation, in all of which the value "1" is represented by
the same single bit. However, to avoid sign-extension issues
it is wise in C code to always perform bit manipulations on
*unsigned* integer types, and especially type "unsigned char"
which is guaranteed to have no padding (non-value) bits.
John E. Gwyn family
> Bit zero [the lsb] is the same for both platforms [and please don't
Actually, which bit is designated by the computer maker as "bit 0"
in their documentation depends on the computer maker, and varies
even today. That is why specifications should always tie the bit
numbering convention to "least significant" or "most significant"
since those have clear meaning within programs using the data.
Mok-Kong Shen
In fact the DES specification numbers the bits of the
block being processed.
M. K. Shen
Rudi Chiarito
> Endianess only applies to byte order ...
Not true.
> Bit zero [the lsb] is the same for both platforms [and please don't anybody
> quote some 40 yr old computer that nobody in their right mind would use that
> loads the bits in some esoteric order like 3 7 4 1 2 5 0 6 because that's
> just useless trivia]
Bit zero is the same for x86 and 68K, but not for PPC. The PowerPC
architecture, which supports both big- and little-endian byte order,
defines bit zero as the msb. I.e. the value of a 32bit memory location
or register with bit 0 set will be 2^31, not 1 (2^0). This is quite
confusing for assembly programmers who are used e.g. to consider
setting bit N and ORing 2^N as equivalent operations. On the other
hand, if you look closely at data stored in memory using a big-endian
byte ordering scheme, this kind of bit numbering makes sense and is
very consistent indeed (bit numbers and memory addresses always grow
in the same direction).
As far as I know this convention was inherited from previous IBM
architectures. I don't think anybody of us in the Motorola camp used
to the 68k really liked it on first impact.
BTW, I'd hardly consider PPC as a "40 yr old" architecture. ;)
--
"Perfection is achieved, not when there is nothing more to add,
but when there is nothing left to take away" (Antoine de Saint-Exupery)
Rudi Chiarito ru...@amiga.com
Tom St Denis
"Rudi Chiarito" <ru...@amiga.com> wrote in message
news:m31yhfj...@amiga.com...
> "Tom St Denis" <tomst...@yahoo.com> writes:
> > Endianess only applies to byte order ...
>
> Not true.
>
> > Bit zero [the lsb] is the same for both platforms [and please don't
anybody
> > quote some 40 yr old computer that nobody in their right mind would use
that
> > loads the bits in some esoteric order like 3 7 4 1 2 5 0 6 because
that's
> > just useless trivia]
>
Ok I stand corrected.
Again this shows off how fucking stupid sci.crypt people are however.
Out of all the posts I've sent today, the only one that get replies are the
ones where people can quip of "you're wrong" posts.
I'm trying to write a library not only to teach myself good
coding/documentation styles but to provide something. A few people in this
group seem to appreciate my efforts.
However, when I actually need help on something serious and just not OT
bullshit like this thread [irony] I get zero replies.
I still need help fixing my ECC code and its driving me up the wall...
please if you can help out!
Tom
Brian Gladman
news:3C2CC704...@compuserve.com...
> Brian Gladman wrote:
> > "Douglas A. Gwyn" <DAG...@null.net> wrote...
> > > The specification (of AES) should not use "bit numbers" without
> > > first explaining the convention.
> > I agree. And a real implementation should then document how it maps
> > these abstract 'aes bits' to the 'real world bits' that it uses to
> > represent them.
>
> I disagree. The whole point of AES explaining the convention is so
> that it is not necessary to establish a second mapping. If, for
> example, "bit number 0 shall mean the least significant bit of the
> octet", then no further specification is needed; in C one can
> c = getc();
> if (c & 1)
> ... // least significant bit (AES 0) was set
The fact that bit 0 in an "aes octet" is the least significant bit does not
mean that this bit has the be mapped to be the least significant bit in a "C
octet".
If you believe otherwise please point out precisely where in the AES FIPS it
says that the AES conventions for bits, bytes and array enumerations must be
implemented by mapping them to the corresponding conventions that exist in
any implementation environment.
> > > In C, a[i] selects byte number i from the array designated by a.
> > This should be true if the implementor uses the 'obvious' mapping.
> > However they are free to do otherwise if they wish.
>
> No, they are not free to do so; it would not conform to the standard.
There is nothing in the FIPS that requires the enumeration of aes bytes
within arrays to be mapped to a corresponding enumeration in any
implementation environment.
For example, it is perfectly aceptable to define aes_bit[i] as c_byte[i]
with zero/non-zero byte values representing the aes bit values 0/1. And in
this mapping one aes byte maps to eight C bytes.
This is a mapping that might well be used for AES in situations where bit
manipulation is very expensive.
Brian Gladman
Mok-Kong Shen
Rudi Chiarito wrote:
>
> Bit zero is the same for x86 and 68K, but not for PPC. The PowerPC
> architecture, which supports both big- and little-endian byte order,
> defines bit zero as the msb. I.e. the value of a 32bit memory location
> or register with bit 0 set will be 2^31, not 1 (2^0). This is quite
> confusing for assembly programmers who are used e.g. to consider
> setting bit N and ORing 2^N as equivalent operations. On the other
> hand, if you look closely at data stored in memory using a big-endian
> byte ordering scheme, this kind of bit numbering makes sense and is
> very consistent indeed (bit numbers and memory addresses always grow
> in the same direction).
Sorry for my ignorance. But isn't this an issue
of how one visualizes the memory bits being arranged?
If one considers the bits to extend to the left, then
bit numbers and memory address can grow in the same
direction with the rightmost bit of a word having
the value 2^0. On the other hand, one can look at
the sequence from the other side. Then the sequence
appears to be extending to the right. If one
retains the correspondence of the aforementioned
bit with the value 2^0, then the (now) leftmost
bit has that value. What is wrong in this viewpoint?
Thanks.
M. K. Shen
Brian Gladman
>
> "SCOTT19U.ZIP_GUY" <david_...@emailv.com> wrote in message
> news:918570DFBH110W...@207.126.101.92...
> > JEG...@compuserve.com (John E. Gwyn family) wrote in
> > <3C2CC704...@compuserve.com>:
> >
> > >Brian Gladman wrote:
> > >> "Douglas A. Gwyn" <DAG...@null.net> wrote...
> > >> > The specification (of AES) should not use "bit numbers" without
> > >> > first explaining the convention.
> > >> I agree. And a real implementation should then document how it maps
> > >> these abstract 'aes bits' to the 'real world bits' that it uses to
> > >> represent them.
> > >
> > >I disagree. The whole point of AES explaining the convention is so
> > >that it is not necessary to establish a second mapping. If, for
> > >example, "bit number 0 shall mean the least significant bit of the
> > >octet", then no further specification is needed; in C one can
> > > c = getc();
> > > if (c & 1)
> > > ... // least significant bit (AES 0) was set
> >
> >
> > Depends on the defination of octet. Is the least significant bit
> > on the left side or the right side? Are you think of numbers
> > as two complement or ones complement?
>
> Endianess only applies to byte order ...
It applies to any composition of entities into larger entities in situations
where one or more ordering relationships between the individual component
entities are given significance by some defined convention (numeric
significance, memory address order, ...).
> Bit zero [the lsb] is the same for both platforms [and please don't
anybody
> quote some 40 yr old computer that nobody in their right mind would use
that
> loads the bits in some esoteric order like 3 7 4 1 2 5 0 6 because that's
> just useless trivia]
We don't need to go back in time to find a counter example.
In the Motorola 68K architecture, bit field instructions map bit numbers
starting from zero at the most significant end of addressed entities. Since
numeric instuctions map the least significant bit as bit 0, we hence have a
current architetcture in which two different conventions are in use at the
same time.
I might add that I don't consider such details to be trivial since I have
seen the very serious consequences of wrongly assuming that bit numbering
and ordering is that which we we are predisposed to expect.
Brian Gladman
Brian Gladman
>
> "Rudi Chiarito" <ru...@amiga.com> wrote in message
> news:m31yhfj...@amiga.com...
> > "Tom St Denis" <tomst...@yahoo.com> writes:
> > > Endianess only applies to byte order ...
> >
> > Not true.
> >
> > > Bit zero [the lsb] is the same for both platforms [and please don't
> anybody
> > > quote some 40 yr old computer that nobody in their right mind would
use
> that
> > > loads the bits in some esoteric order like 3 7 4 1 2 5 0 6 because
> that's
> > > just useless trivia]
> >
> > BTW, I'd hardly consider PPC as a "40 yr old" architecture. ;)
>
> Ok I stand corrected.
>
> Again this shows off how fucking stupid sci.crypt people are however.
Is this all sci.crypt people or just some of us?
Moreover, is it really necessary to use such bad language to make your
point?
> Out of all the posts I've sent today, the only one that get replies are
the
> ones where people can quip of "you're wrong" posts.
>
> I'm trying to write a library not only to teach myself good
> coding/documentation styles but to provide something. A few people in
this
> group seem to appreciate my efforts.
>
> However, when I actually need help on something serious and just not OT
> bullshit like this thread [irony] I get zero replies.
The very fact that you consider this thread to be 'OT bullshit' suggests to
me that you really don't understand the importance of the issues being
discussed.
Which is truly ironic given the 'plus points' I had originally given you for
starting it.
Brian Gladman
Rudi Chiarito
> Sorry for my ignorance. But isn't this an issue
> of how one visualizes the memory bits being arranged?
> If one considers the bits to extend to the left, then
> bit numbers and memory address can grow in the same
> direction with the rightmost bit of a word having
> the value 2^0.
Such arrangement is very elegant, but would be considered by pretty
much everybody in the Western world as "backwards". :(
Furthermore, it still suffers from another mismatch with another
cultural convention, as explained below.
> On the other hand, one can look at
> the sequence from the other side. Then the sequence
> appears to be extending to the right. If one
> retains the correspondence of the aforementioned
> bit with the value 2^0, then the (now) leftmost
> bit has that value. What is wrong in this viewpoint?
The only "wrong" thing is that now the MSB is on the right side. With
68k, x86 and PPC the MSB is always on the left side - only the
numbering is different. That's consistent with the fact that when you
write using e.g. Hindu-Arabic numerals, the most significant digit
comes first. We're talking about sequences of binary digits, after
all.
Thus, the "problem" is that historically we write using digits in
decreasing order of significance, while intuitively we often find it
more useful to see other things in increasing order (e.g. memory
addresses). There's bound to be a point somewhere where the two views
mismatch.
Tom St Denis
"Brian Gladman" <b...@gladman.uk.net> wrote in message
news:Vq7X7.4663$XN3.248304@wards...
> "Tom St Denis" <tomst...@yahoo.com> wrote in message
> news:3C5X7.130406$KT.34...@news4.rdc1.on.home.com...
> >
> > "Rudi Chiarito" <ru...@amiga.com> wrote in message
> > news:m31yhfj...@amiga.com...
> > > "Tom St Denis" <tomst...@yahoo.com> writes:
> > > > Endianess only applies to byte order ...
> > >
> > > Not true.
> > >
> > > > Bit zero [the lsb] is the same for both platforms [and please don't
> > anybody
> > > > quote some 40 yr old computer that nobody in their right mind would
> use
> > that
> > > > loads the bits in some esoteric order like 3 7 4 1 2 5 0 6 because
> > that's
> > > > just useless trivia]
> > >
> > > BTW, I'd hardly consider PPC as a "40 yr old" architecture. ;)
> >
> > Ok I stand corrected.
> >
> > Again this shows off how fucking stupid sci.crypt people are however.
>
> Is this all sci.crypt people or just some of us?
>
> Moreover, is it really necessary to use such bad language to make your
> point?
You're right, I'm just fed up. My ECC code doesn't work despite checking 3
difference sources for formulae. I mean I can implement DH or RSA over Z in
like 5 mins... but getting just a ECC add function to work is for some
reason beyond me... [eventhough its all of 20 lines of code!]
I'm sorry for being rude, but I'm sick of these non-ending non-cryptographic
related threads going on when real questions are floating around.
>
> > Out of all the posts I've sent today, the only one that get replies are
> the
> > ones where people can quip of "you're wrong" posts.
> >
> > I'm trying to write a library not only to teach myself good
> > coding/documentation styles but to provide something. A few people in
> this
> > group seem to appreciate my efforts.
> >
> > However, when I actually need help on something serious and just not OT
> > bullshit like this thread [irony] I get zero replies.
>
> The very fact that you consider this thread to be 'OT bullshit' suggests
to
> me that you really don't understand the importance of the issues being
> discussed.
>
> Which is truly ironic given the 'plus points' I had originally given you
for
> starting it.
The thread is not only off-topic but gets rehashed every 3 weeks anyways...
Tom
Brian Gladman
In fact a great deal of effort in writing the AES FIPS was devoted to
AVOIDING any concept of numeric significance because all AES bytes represent
finite field elements and this means that they (and their component bits)
have no numeric interpretation and hence no numeric significance of any
kind.
The critical section of the FIPS in this respect (3.2 in the FIPS, 1.2 in my
FIPS input) took several weeks to get right precisely because Joan Daemen
and Vincent Rijmen wanted to ensure that there was no possible numeric
interpretation of this critical definition of a 'byte'. As a result this
section was worded in a way that ensures that it is bit enumeration alone
that identifies AES bits. Hence, for example, this section does not refer
to the most/least significant nibble (4-bits) in a byte but instead to the 4
bits with the highest/lowest enumerations.
Also in referring to shifts in my input I used the term 'up shift' and 'down
shift' rather than 'left shift' or 'right shift' because what matters is
whether a bit (or a byte) moves to a higher or lower numbered position, not
whether it moves to a position of higher or lower numeric significance.
By avoiding numeric significance (and concepts of left or right) this
ensures that the specification is endian neutral and allows up shifts on
bytes within words to be mapped to left shifts on x86 and right shifts on
MC68k without implying that either mapping is preferred. The FIPS did not
go this far but left right concepts are used pretty sparingly.
Brian Gladman
Brian Gladman
>
> >
> > Is this all sci.crypt people or just some of us?
> >
> > Moreover, is it really necessary to use such bad language to make your
> > point?
>
> You're right, I'm just fed up. My ECC code doesn't work despite checking
3
> difference sources for formulae. I mean I can implement DH or RSA over Z
in
> like 5 mins... but getting just a ECC add function to work is for some
> reason beyond me... [eventhough its all of 20 lines of code!]
I understand your frustration but I would not want to put you in my kill
file, something I always do for anyone who makes a habit of using such
language.
> I'm sorry for being rude, but I'm sick of these non-ending
non-cryptographic
> related threads going on when real questions are floating around.
You named it as an OT thread but it just happens to be right on topic since
this issue was critical in writing certain parts of the AES FIPS
specification.
Brian Gladman
Tom St Denis
> "Tom St Denis" <tomst...@yahoo.com> wrote in message
> news:aR7X7.131570$KT.34...@news4.rdc1.on.home.com...
> >
> > >
> > > Is this all sci.crypt people or just some of us?
> > >
> > > Moreover, is it really necessary to use such bad language to make your
> > > point?
> >
> > You're right, I'm just fed up. My ECC code doesn't work despite
checking
> 3
> > difference sources for formulae. I mean I can implement DH or RSA over
Z
> in
> > like 5 mins... but getting just a ECC add function to work is for some
> > reason beyond me... [eventhough its all of 20 lines of code!]
>
> I understand your frustration but I would not want to put you in my kill
> file, something I always do for anyone who makes a habit of using such
> language.
Sorry I didn't mean to offend you. Actually I value your posts since you're
on the spot to help out.
Anyways I've managed to fix my ECC code so I am a bit euphoric right now...
[giddy more like]. I'm in the midst of adding full ECC DH support to my
library [and fixing other DH over Z/pZ bugs I found in the process].
> > I'm sorry for being rude, but I'm sick of these non-ending
> non-cryptographic
> > related threads going on when real questions are floating around.
>
> You named it as an OT thread but it just happens to be right on topic
since
> this issue was critical in writing certain parts of the AES FIPS
> specification.
The thread started off as me whining about the horrible coding standards
almost typical of cryptographers [Schneier is by far the worst, no offense
of course, he writes good books and essays, just can't program worth
beans!].
Giddy.... hmm
Here's a divergent question. What are typical "safe" sizes of ECC keys over
Z/pZ when the order of a point is maximal [i.e very close to 'p']?
Tom
Douglas A. Gwyn
> In fact a great deal of effort in writing the AES FIPS was devoted to
> AVOIDING any concept of numeric significance because all AES bytes represent
> finite field elements and this means that they (and their component bits)
> have no numeric interpretation and hence no numeric significance of any
> kind.
> The critical section of the FIPS in this respect (3.2 in the FIPS, 1.2 in my
> FIPS input) took several weeks to get right precisely because Joan Daemen
> and Vincent Rijmen wanted to ensure that there was no possible numeric
> interpretation of this critical definition of a 'byte'. As a result this
> section was worded in a way that ensures that it is bit enumeration alone
> that identifies AES bits. Hence, for example, this section does not refer
> to the most/least significant nibble (4-bits) in a byte but instead to the 4
> bits with the highest/lowest enumerations.
Unless it ties this to the rest of the world, which amounts to
identifying where the least-significant bit of the integers used
for "enumeration" will fall with respect to everything else on
a computer (e.g. which one goes first in time when transmitting
an octet over a serial communications line), there is poor
interoperability. I suppose it is *possible* that AES is totally
symmetric w.r.t. which end of the octet is taken as the l.-s. bit,
in which case it doesn't matter that it's unspecified; otherwise
it would be a serious mistake for a datacom *standard*.
Douglas A. Gwyn
> > > > In C, a[i] selects byte number i from the array designated by a.
> > > This should be true if the implementor uses the 'obvious' mapping.
> > > However they are free to do otherwise if they wish.
> > No, they are not free to do so; it would not conform to the
> > standard.
> There is nothing in the FIPS that requires the enumeration of aes
> bytes within arrays to be mapped to a corresponding enumeration in
> any implementation environment.
Ahh, I see -- to me, when the terms "implementation" and "standard"
are used in a discussion of how C code has to work, I assume that
the *C* implementation and standard are meant, whereas you were
referring to AES.. I agree that there are all sorts of ways to
map AES into C. The real question is, if somebody sends me:
AES USED IN ECB MODE; KEY: BIT 0 = 1, BIT 1 = 0, ...;
CIPHER BLOCK # 0: BIT 0 = 0, BIT 1 = 0, BIT 2 = 1, ...
the AES spec ought to be sufficiently clear that I can recover
the original plaintext without trial-and-error.
For data interchange purposes, it is also necessary to nail down
which bit is which in any related information that is stored or
transmitted. I finessed that above by spelling out each individual
bit, but more usually they are packed into octets and stored on
a disk drive or transmitted on a communication circuit. The
sequence of storage or transmission of those octets is not an
issue these days (after all, when I type UNIX here you don't see
NUXI on your end). So if the description is truly in terms of
8-bit units, the only thing we really need to know is where the
AES bit 0 of a set of 8 falls within a computing-industry de facto
standard 8-bit "byte" (stored or transmitted container for an octet):
it it the l.-s. or m.-s. bit? Other (scrambled) bit orderings
within the byte would serve no useful purpose.
Mok-Kong Shen
Rudi Chiarito wrote:
>
> Mok-Kong Shen <mok-ko...@t-online.de> writes:
> > On the other hand, one can look at
> > the sequence from the other side. Then the sequence
> > appears to be extending to the right. If one
> > retains the correspondence of the aforementioned
> > bit with the value 2^0, then the (now) leftmost
> > bit has that value. What is wrong in this viewpoint?
>
> The only "wrong" thing is that now the MSB is on the right side. With
> 68k, x86 and PPC the MSB is always on the left side - only the
> numbering is different. That's consistent with the fact that when you
> write using e.g. Hindu-Arabic numerals, the most significant digit
> comes first. We're talking about sequences of binary digits, after
> all.
I believe there is a misunderstanding between us.
I was saying that one can make the convention that
bit numbering AND word/byte numbering all increase
in the same direction, and one 'chooses' to VIEW the
bit sequence on the one side such that it APPEARS
to extend to the left (we ignore the possibility to
look from the back side where the sequence would
appear to extent to the right). Then for a word, the
rightmost bit has the value 2^0 and everything is
natural and satisfactory, isn't it? (Thus I don't
understand the points you made in a previous post.)
M. K. Shen
Mok-Kong Shen
"Douglas A. Gwyn" wrote:
>
[snip]
> The real question is, if somebody sends me:
> AES USED IN ECB MODE; KEY: BIT 0 = 1, BIT 1 = 0, ...;
> CIPHER BLOCK # 0: BIT 0 = 0, BIT 1 = 0, BIT 2 = 1, ...
> the AES spec ought to be sufficiently clear that I can recover
> the original plaintext without trial-and-error.
I am confused and hence a trivial question: In normal
numbers written on paper, the most significant digit
is on the left. What's the difficulty of having the
universal convention that for a block of plain/ciphertext
AND for a key the binary sequence is defined to be
such that the MSB (higher numbered) bit is on the left?
If a computer architecture is such that it needs to
do some extra operations in order to be conform to
that convention, because e.g. it stores the given
bit sequence in its own different (maybe even bizzare)
way, then that's the problem of the person who chooses
to use that odd computer architecture. For a standard
specification one should only use the 'natural' ordering
of bits and it is to be THE ordering even if not
explicitly mentioned.
M. K. Shen
Bryan Olson
Mok-Kong Shen wrote:
> I am confused and hence a trivial question: In normal
> numbers written on paper, the most significant digit
> is on the left. What's the difficulty of having the
> universal convention that for a block of plain/ciphertext
> AND for a key the binary sequence is defined to be
> such that the MSB (higher numbered) bit is on the left?
Good question and the answer is somewhat sad.
If you check most any crypto spec, your convention works. DES is
defined on a 64-bit block, and everyone agrees that given the input in
the form of eight octets, the first bit in the 64-bit DES block is the
high order bit in the first octet.
But alas, it doesn't always work. When sending octets across a serial
line (meaning bit-serial), the low order bit is almost always first.
Thus the bit order one uses on stored octets is not the bit order one
sees in a serial transmission of those same octets.
I know of no crypto algorithm specifications which violate your
convention. I would not be surprised if someone can point one out.
Other specifications, for example CRC calculations, are definitely a
problem. ATM (Asynchronous Transfer Mode, not the bank machines) uses
the standard CRC-32, as does GZIP. When both compute CRC-32 on the same
octets in the same order, they get different results (usually). ATM is
computing the CRC on the serial line, with least significant bit first,
and thus the higher-exponent term in the polynomial. GZIP is computing
it on the stored octets, most significant bit first.
My advice: If reading a crypto specification that does not specify
otherwise, the first bit in a block is probably the high-order bit in
the octet that is "first" ("first" possibly according to a given endian
convention). If writing a specification, always use the
high-order-bit-of-byte-first convention, AND state the convention
explicitly.
--Bryan
Brian Gladman
You seem to be suggesting that numeric significance is the only ordering
principle that can be used to map an abstract ordering property into the
real world.
For numeric values it makes sense to use numeric significance ordering but
this is often not the best ordering property for other entities. And as
indicated above, the AES (Rijndael) specification uses enumeration ordering
rather than numeric significance ordering precisely because AES bytes are
finite field elements and not numbers. For AES, as long as we know where
bit 0 is located within each byte, it simply does not matter whether it is
at one end or the other (or even somewhere in between).
There are many ways of mapping an abstract ordering into the real world,
there being no case for always preferring numeric significance for this. In
many circumstances ordering by enumeration, by memory address or by time (as
you suggest) will be a more sensible choice.
Brian Gladman
Brian Gladman
"Mok-Kong Shen" <mok-ko...@t-online.de> wrote in message
news:3C2DA9BD...@t-online.de...
>
>
> "Douglas A. Gwyn" wrote:
> >
> [snip]
> > The real question is, if somebody sends me:
> > AES USED IN ECB MODE; KEY: BIT 0 = 1, BIT 1 = 0, ...;
> > CIPHER BLOCK # 0: BIT 0 = 0, BIT 1 = 0, BIT 2 = 1, ...
> > the AES spec ought to be sufficiently clear that I can recover
> > the original plaintext without trial-and-error.
>
> I am confused and hence a trivial question: In normal
> numbers written on paper, the most significant digit
> is on the left. What's the difficulty of having the
> universal convention that for a block of plain/ciphertext
> AND for a key the binary sequence is defined to be
> such that the MSB (higher numbered) bit is on the left?
The immediate problem here is that you are confusing two different ordering
relationships. There is no case for assuming that the more (numerically)
significant bits will always be those with higher bit numbers.
> If a computer architecture is such that it needs to
> do some extra operations in order to be conform to
> that convention, because e.g. it stores the given
> bit sequence in its own different (maybe even bizzare)
> way, then that's the problem of the person who chooses
> to use that odd computer architecture. For a standard
> specification one should only use the 'natural' ordering
> of bits and it is to be THE ordering even if not
> explicitly mentioned.
Is THE ordering that you wish to impose going to be by bit number or by
numeric significance, remembering that these won't always give the same
result?
In my view any attempt to impose a standard here is certain to fail. What
we should be seeking to ensure is that any ordering principle used should
always be explicitly and unambiguously defined
Brian Gladman
Mok-Kong Shen
Brian Gladman wrote:
>
> Is THE ordering that you wish to impose going to be by bit number or by
> numeric significance, remembering that these won't always give the same
> result?
>
> In my view any attempt to impose a standard here is certain to fail. What
> we should be seeking to ensure is that any ordering principle used should
> always be explicitly and unambiguously defined
Suppose one sees in a literature a binary number
displayed as a sequence of 1's and 0's, would there
be any dispute as to which is MSB and which is LSB?
M. K. Shen
Brian Gladman
I would assume that the most significant bit was to the left but I would
have no idea about bit numbers.
If I assumed it to be a binary integer I would expect the highest numbered
bit to be on the left.
Hence I would interpret 110 as 1 * 2^2 + 1*2^1 + 0*2^0 (6 decimal) with the
bits numbered 0, 1 and 2 from right to left - that is, the bit number is the
power of 2 involved for each bit.
If I assumed it to be a binary fraction I would anticipate that the highest
numbered bit would be on the right.
Hence I would interpret 110 as 1*2^-1 + 1*2^-2 + 0*2^-3 (0.75 decimal) with
the bits numbered 1, 2, 3 from left to right - that is, the bit number is
the negative power of 2 involved for each bit.
If it is a bit sequence and not a number, I would assume that the bit number
increases from left to right.
In all cases, however, I would not want to assume anything. I would expect
in technical specifications that the convention employed would always be
described so that I did not have to guess what the originator intended.
Brian Gladman
Mok-Kong Shen
Brian Gladman wrote:
>
> "Mok-Kong Shen" <mok-ko...@t-online.de> wrote:
> > Suppose one sees in a literature a binary number
> > displayed as a sequence of 1's and 0's, would there
> > be any dispute as to which is MSB and which is LSB?
>
> I would assume that the most significant bit was to the left but I would
> have no idea about bit numbers.
>
> If I assumed it to be a binary integer I would expect the highest numbered
> bit to be on the left.
>
> Hence I would interpret 110 as 1 * 2^2 + 1*2^1 + 0*2^0 (6 decimal) with the
> bits numbered 0, 1 and 2 from right to left - that is, the bit number is the
> power of 2 involved for each bit.
>
> If I assumed it to be a binary fraction I would anticipate that the highest
> numbered bit would be on the right.
>
> Hence I would interpret 110 as 1*2^-1 + 1*2^-2 + 0*2^-3 (0.75 decimal) with
> the bits numbered 1, 2, 3 from left to right - that is, the bit number is
> the negative power of 2 involved for each bit.
>
> If it is a bit sequence and not a number, I would assume that the bit number
> increases from left to right.
>
> In all cases, however, I would not want to assume anything. I would expect
> in technical specifications that the convention employed would always be
> described so that I did not have to guess what the originator intended.
O.k. There was a tiny flaw in what I wrote. A number
could be a fraction and could even be negative etc.
But in crypto we are dealing with binary whole numbers.
In that case the convention that the rightmost bit
is associated with 2^0, the next bit is associated
with 2^1, etc. is universally accepted, isn't it?
We should not let the fact that some computer
architectures store the bits of a binary number in a
different way to force us to do any extra stuff in
writing a (in principle abstract) specification that
deals with essentially math. The compiler writer or
programmer using such odd architectures have to take
the trouble to do their jobs right with reference to
the abstract specification. To use an analogy, a math
textbook can e.g. describe how to solve a system of
linear equations with Guassian elimination. It doesn't
say how the elements of the matrix of the system are to
be put in the computer storage. Fortran stores the
elements columnwise, while a number of other PLs store
the elements rowwise. It is apparently futile for the
math textbook to bother with such storage issues,
isn't it?
M. K. Shen
Douglas A. Gwyn
> You seem to be suggesting that numeric significance is the only
> ordering principle that can be used to map an abstract ordering
> property into the real world.
No, but it's the one we already have in place.
> ... as indicated above, the AES (Rijndael) specification uses
> enumeration ordering rather than numeric significance ordering
> precisely because AES bytes are finite field elements and not
> numbers.
Excuse me, but elements of a finite field are too numbers.
Douglas A. Gwyn
> But alas, it doesn't always work. When sending octets across a serial
> line (meaning bit-serial), the low order bit is almost always first.
> Thus the bit order one uses on stored octets is not the bit order one
> sees in a serial transmission of those same octets.
But they are reassembled at the other end into the same representation
as they had on the transmitting side, which is all that matters.
Douglas A. Gwyn
> Suppose one sees in a literature a binary number
> displayed as a sequence of 1's and 0's, would there
> be any dispute as to which is MSB and which is LSB?
There is no such thing as MSB and LSB until the collection of bits
is interpreted as representing the value of an integer, and there
are two more or less equally common but different ways currently
in use for bit order in integer representations.
If the bits are supposed to be indexed #0, #1, #2, etc. then the
only natural way to transmit the set of bits is to send bit #0
first, bit #1 next, etc. If the receiving party writes the bits
down in the order received, in most of the Western world bit #0
will be written on the left.
To interpret bit #0 as having a numerical position value, if
"little-endian" representation is used then its value is 2^0.
If using "big-endian" representation, its value is 2^(N-1)
where N is the "word" (or block) size. Because little-endian
representation is independent of word size, it works better in
call-by-reference since a procedure taking a narrow integer
parameter will work okay when the actual argument is a wider
integer, so long as its value is small. DEC PDP-11 FORTRAN
took advantage of this, even though it meant shuffling around
the native FP11 hardware representation for doubleword integers.
(The FP11 designer placed the two 16-bit words in big endian
order, apparently thinking IBM-like as he did when laying out
the floating-point formats. Since each PDP-11 word treated its
bytes as in little-endian order, this meant that the byte order
was 1032 rather than 3210 as one would have wanted, where here
I have written the entire doubleword with MSB on the left.
Whether it appears on the left when you read it depends on
whether you're in the habit of reading English text upside-
down or mirrored :-)
Douglas A. Gwyn
> We should not let the fact that some computer
> architectures store the bits of a binary number in a
> different way to force us to do any extra stuff in
> writing a (in principle abstract) specification that
> deals with essentially math. The compiler writer or
> programmer using such odd architectures have to take
> the trouble to do their jobs right with reference to
> the abstract specification. To use an analogy, a math
> textbook can e.g. describe how to solve a system of
> linear equations with Guassian elimination. It doesn't
> say how the elements of the matrix of the system are to
> be put in the computer storage. Fortran stores the
> elements columnwise, while a number of other PLs store
> the elements rowwise. It is apparently futile for the
> math textbook to bother with such storage issues,
> isn't it?
The issue is not in how an encryption specification is
implemented (so long as it is done correctly) but rather
whether the specification is incomplete in that it doesn't
tell the implementor enough to ensure that everybody else
also working from the specs will be able to decipher what
he enciphers (without trial and error), if they have the key.
David Hopwood
"Douglas A. Gwyn" wrote:
> Brian Gladman wrote:
> > In fact a great deal of effort in writing the AES FIPS was devoted to
> > AVOIDING any concept of numeric significance
Then all that effort has been counterproductive.
> > because all AES bytes represent
> > finite field elements and this means that they (and their component bits)
> > have no numeric interpretation and hence no numeric significance of any
> > kind.
> > The critical section of the FIPS in this respect (3.2 in the FIPS, 1.2 in
> > my FIPS input) took several weeks to get right precisely because Joan
> > Daemen and Vincent Rijmen wanted to ensure that there was no possible
> > numeric interpretation of this critical definition of a 'byte'.
Why on earth would they want that? An octet value is defined as an integer
between 0 and 255 inclusive, and 'byte' is a synonym for octet here. So a
numeric interpretation is absolutely essential for interoperability. All
architectures, protocols, and programming languages that use octets have
a well-defined mapping to this numeric definition [*], but most do not
specify any mapping to bit sequences.
The convention used for the hexadecimal notation implies that bit 0 is
intended to be the least significant bit within each octet (and that is
what the Rijndael reference implementation assumes). However, it's
impossible to specify the interface between AES and any real-world system
that uses octet strings without mapping the elements of GF(2^8) to integers,
and so this mapping should have been stated explicitly in the FIPS.
(A mapping to bit sequences is not needed at all, and is simply confusing:
for example if we use a serial comms protocol with little-endian bit ordering,
such as RS-232, a sensibly defined system will end up with the bits in each
octet being transmitted on the wire in the opposite order to that defined
in the draft FIPS.)
[*] Java uses a signed "byte" type, but its I/O and crypto libraries
consistently assume that octet values 128..255 are represented as the
integers -128..-1, i.e. using twos-complement.
In C and C++, most of the standard I/O library functions for binary
I/O take "void *" arguments, and casting "unsigned char *" to "void *"
is guaranteed to implement the correct mapping.
Neither Java, C, nor any other programming language I'm aware of,
define a mapping from bit sequences to their preferred types for
representing octets.
> > As a result this section was worded in a way that ensures that it is
> > bit enumeration alone that identifies AES bits. Hence, for example,
> > this section does not refer to the most/least significant nibble (4-bits)
> > in a byte but instead to the 4 bits with the highest/lowest enumerations.
>
> Unless it ties this to the rest of the world, which amounts to
> identifying where the least-significant bit of the integers used
> for "enumeration" will fall with respect to everything else on
> a computer (e.g. which one goes first in time when transmitting
> an octet over a serial communications line),
Which bit goes first in serial transmission is completely unimportant -
the relevant serial transmission standard determines that, not the AES
spec. The paper [Coh80] (which defined the terms "big-endian" and
"little-endian"), referring to bit transmission order, said:
# Wouldn't it be nice if we could encapsulate the byte-communication
# and forget all about the idiosyncrasies of the past [...]?
and in fact that is precisely what has been done in all modern protocols
(and also storage media): bit ordering is left to the physical layer,
and higher level protocols are defined in terms of octets/bytes.
To be compatible with this approach, what needs to be specified for AES
is how plaintext, ciphertext and key blocks correspond to sequences of
octet values, where each octet is an integer in the range 0..255.
In another post, Doug Gwyn wrote:
> So if the description is truly in terms of
> 8-bit units, the only thing we really need to know is where the
> AES bit 0 of a set of 8 falls within a computing-industry de facto
> standard 8-bit "byte" (stored or transmitted container for an octet):
> it it the l.-s. or m.-s. bit? Other (scrambled) bit orderings
> within the byte would serve no useful purpose.
Bit 0 is the LS bit. I.e. what the spec needed to say is that the field
element
b_7.x^7 + b_6.x^6 + b_5.x^5 + b_4.x^4 + b_3.x^3 + b_2.x^2 + b_1.x + b_0
corresponds to the octet value
b_7.2^7 + b_6.2^6 + b_5.2^5 + b_4.2^4 + b_3.2^3 + b_2.2^2 + b_1.2 + b_0
All the implementations of Rijndael I've seen assume this interpretation.
In fact the Rijndael documentation specified it implicitly in the example
in section 2.1:
# A byte b, consisting of bits b7 b6 b5 b4 b3 b2 b1 b0, is considered as
# a polynomial with coefficient in {0,1}:
#
# b_7.x^7 + b_6.x^6 + b_5.x^5 + b_4.x^4 + b_3.x^3 + b_2.x^2 + b_1.x + b_0
#
# Example: the byte with hexadecimal value '57' (binary 01010111)
# corresponds with polynomial
#
# x^6 + x^4 + x^2 + x + 1.
Here "hexadecimal value '57' (binary 01010111)" refers to the integer
0x57, which makes the intended mapping to octet values unambiguous
(although an explicit definition would have been better).
However, as Brian Gladman says, the FIPS carefully avoids defining any
such mapping, misguidedly IMO. Implementors shouldn't have to guess based
on the convention for writing field elements in hexadecimal. I hadn't
realised that this had changed from the Rijndael spec, otherwise I would
have made a comment to NIST.
[Coh80] Danny Cohen,
"On Holy Wars, and a Plea for Peace,"
IEN 137, 1 April 1980.
http://www.op.net/docs/RFCs/ien-137
- --
David Hopwood <david....@zetnet.co.uk>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
iQEVAwUBPC6Y+DkCAxeYt5gVAQFr9ggAkONr/tDAHQX/YwInlLQx8y2wNnbG9vsa
ajUgw+7GvhurkmO8Iz3Yhy1qVRR3LUG5z3YXbrCFD5bmZ2RlGuz9ruoo3MDhDnQ1
ohZOPA/1RYSATwITa/CHh/yQiND5lQbSvqqBBo5jmr0lb+t3podZLa2l+ohDx94D
RG3YcgtAAMpIoq/WWLSLcBBELNWe/6CVVuwYt+MIIboo0bf36JTsTkrQODCm8di5
m4l042F4hD4EvVWUZdgEaUS2+YID+f6oBYiQ7sotzl/rsIa2QhncctCMY+35rp6p
KYWgdO57+hwI4svE7ntSb/o4qdCwiIS/SjuJdfmJAPns90bZHo5hlQ==
=O1Nb
-----END PGP SIGNATURE-----
Bryan Olson
Having worked on the soft UART for a smart-card, to me it matters.
(And having been confused as to why ATM test vectors for CRC-32
didn't match zlib's implementation.)
The question was whether there is a universal convention, and no,
there isn't.
--Bryan
SCOTT19U.ZIP_GUY
<3C2E9908...@zetnet.co.uk>:
>Why on earth would they want that? An octet value is defined as an
>integer between 0 and 255 inclusive, and 'byte' is a synonym for octet
>here. So a numeric interpretation is absolutely essential for
>interoperability. All architectures, protocols, and programming
>languages that use octets have a well-defined mapping to this numeric
>definition [*], but most do not specify any mapping to bit sequences.
>
Its the US government do you really think they would do anything
that might be normal or helpful when they can go out of there way
to make it more obscure. Besides if they made it to way to
understand some 16 year kid hacker might come up with an easy
break. Just think how embarassing that would be.
>
>and in fact that is precisely what has been done in all modern protocols
>(and also storage media): bit ordering is left to the physical layer,
>and higher level protocols are defined in terms of octets/bytes.
>
>To be compatible with this approach, what needs to be specified for AES
>is how plaintext, ciphertext and key blocks correspond to sequences of
>octet values, where each octet is an integer in the range 0..255.
>
Yes this makes sense. No wonder they didn't do it that way.
>Here "hexadecimal value '57' (binary 01010111)" refers to the integer
>0x57, which makes the intended mapping to octet values unambiguous
>(although an explicit definition would have been better).
>
>However, as Brian Gladman says, the FIPS carefully avoids defining any
>such mapping, misguidedly IMO. Implementors shouldn't have to guess
>based on the convention for writing field elements in hexadecimal. I
>hadn't realised that this had changed from the Rijndael spec, otherwise
>I would have made a comment to NIST.
>
Hell I've made many comments to NIST and they didn't seem to
care a hill of beans. What makes you think they would rather hear
from a limey than a yank. Oh forget I know the answer and I still
will bye you a cold beer if you make it over here before islamic law
bans such things.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Crypto code http://radiusnet.net/crypto/archive/scott/
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
David Hopwood
Bryan Olson wrote:
> Mok-Kong Shen wrote:
>
> > I am confused and hence a trivial question: In normal
> > numbers written on paper, the most significant digit
> > is on the left. What's the difficulty of having the
> > universal convention that for a block of plain/ciphertext
> > AND for a key the binary sequence is defined to be
> > such that the MSB (higher numbered) bit is on the left?
>
> Good question and the answer is somewhat sad.
>
> If you check most any crypto spec, your convention works. DES is
> defined on a 64-bit block, and everyone agrees that given the input in
> the form of eight octets, the first bit in the 64-bit DES block is the
> high order bit in the first octet.
>
> But alas, it doesn't always work. When sending octets across a serial
> line (meaning bit-serial), the low order bit is almost always first.
> Thus the bit order one uses on stored octets is not the bit order one
> sees in a serial transmission of those same octets.
>
> I know of no crypto algorithm specifications which violate your
> convention. I would not be surprised if someone can point one out.
HAVAL, Panama and Tiger (and possibly RIPEMD-*, IIRC). These are all hash
functions that consider the least significant bit of an octet to be first
("little-bit-endian").
Note that the bit order of a hash function is not necessarily the same
as its byte order; notable exceptions are MD4 and MD5, which are
big-bit-endian and little-byte-endian. The original specification for
Tiger was also big-bit-endian and little-byte-endian, but it was then
changed incompatibly to be little-bit-endian.
Hashes that are big-bit-endian are always "left-justified", i.e. the
bits of the last partial octet are shifted to the most significant
end of the octet by the padding function. Hashes that are
little-bit-endian are always "right-justified".
Ciphers don't have any of these complexities because to a first
approximation, no-one uses them on bit strings (at least not without
the application protocol defining its own bit order). Actually no-one
uses hash functions on bit strings either, but they're defined that way
"for historical reasons" (i.e. a lousy idea in MD4 that other designers
copied).
> Other specifications, for example CRC calculations, are definitely a
> problem. ATM (Asynchronous Transfer Mode, not the bank machines) uses
> the standard CRC-32, as does GZIP. When both compute CRC-32 on the same
> octets in the same order, they get different results (usually). ATM is
> computing the CRC on the serial line, with least significant bit first,
> and thus the higher-exponent term in the polynomial. GZIP is computing
> it on the stored octets, most significant bit first.
>
> My advice: If reading a crypto specification that does not specify
> otherwise, the first bit in a block is probably the high-order bit in
> the octet that is "first" ("first" possibly according to a given endian
> convention).
I.e. "big-bit-endian". I disagree; you can't assume that.
My advice when writing specifications is not to define an externally
visible bit order at all; specify algorithms only on octet strings, and
make it clear that they are not defined on bit strings. This is much
simpler. When reading a specification, don't assume any bit order - you
won't need to if your protocol is defined in terms of octet strings, as
it should be.
Time to re-post my "suggestions to crypto algorithm designers"; I think -
see points 6, 8 and 9.
- -----
Here are some general suggestions to designers of cryptographic algorithms,
on how to promote interoperability and make life easier for implementors:
1. If an algorithm is a research contribution rather than intended for
serious use, or if a paper includes variants of an algorithm that
are defined for exposition only, say so clearly. The remainder of
these suggestions apply mainly to algorithms intended for serious use.
2. If a paper defines more than one algorithm, give each of them a distinct
name, and explain why an implementor might want to use one as opposed
to another.
3. For parameterised algorithms, specify precisely the set of allowable
values for each parameter, and give recommended values. Don't include
values that would be insecure in the allowable range.
4. Use consistent capitalisation and punctuation for algorithm names, and
define an unambiguous way to specify any parameters as part of the
name. Consider submitting the algorithm to SCAN (Standard Cryptographic
Algorithm Naming), and following the "name(parameter,...)" format used
there; see <http://www.users.zetnet.co.uk/hopwood/crypto/scan/>.
5. As far as possible, there should be sufficient information in the
paper defining the algorithm, that independent implementations that
are consistent with the paper will automatically interoperate.
(For network protocols and other algorithms involving two or more
parties, that might be unrealistic.)
6. Specify any binary inputs, outputs, keys, etc. as sequences of octets
(i.e. integers between 0 and 255 inclusive). Allowing arbitrary bit
sequences rather than octet sequences is more hassle than it is worth,
and very rarely used. Define octet-sequence representations for any
abstract mathematical objects that would need to be stored,
transmitted, etc. As far as possible, try to follow existing standards
(e.g. IEEE P1363) when doing this, but *don't* use ASN.1.
7. For public key algorithms, specify the distribution of key pairs that
should be used, and algorithms for validating keys. For protocols,
include explicit checks that received values are in the sets assumed
by the mathematical description.
8. Number sequences and indexed variables starting with zero. Number bits
within an integer so that bit i has weight 2^i, and coefficients of a
polynomial so that coefficient i has weight x^i. If there is a completely
arbitrary choice of byte order (i.e. the cost of byte order conversion,
if necessary, would be negligable for the proposed applications), use
big-endian. Don't use inconsistent byte order in different parts of an
algorithm (although this needn't prevent using auxiliary functions like
hashes, etc. that internally use a different byte order to the algorithm
being defined), and make it clear in the specification which order has
been used.
9. Write octet sequences as two hex characters per octet (most followed by
least significant nybble), and left-to-right as they would be stored in
memory or transmitted. This may sound obvious, but the documentation and
test vectors for at least three of the 1st round AES submissions (FROG,
SAFER+ and Serpent) used the opposite (right-to-left) convention.
10. Provide a C reference implementation that is byte-order independent,
uses only aligned memory accesses, does not depend on the sizes of
built-in C types or the signedness of 'char', does not assume that
signed types are twos-complement, and does not use compiler-specific
directives, or any other non-portable tricks. Test it with several
compilers on different platforms.
Ideally use <inttypes.h> for integer types, and provide a minimal
version of this (which can just be a few lines in most cases) for
compilers that don't have it. "Byte-order independent" means using code
that accesses individual bytes/octets, *not* BIG_ENDIAN and LITTLE_ENDIAN
conditional compilation and pointer casts. Use macros only where it
clarifies rather than obfuscates the code.
11. Provide an optimised C/assembler implementation. This may use
compiler-specific embedded assembler, conditional compilation of code
that works better on some machines, etc., but it should still act as a
plain C version when assembler for the target machine is not available.
12. In both reference and optimised C implementations, inputs, outputs,
keys etc. should normally be treated as arrays of an unsigned 8-bit type,
(preferably uint8_t from inttypes.h), to correspond with the mathematical
definition in terms of octets. Put test code that checks an implementation
against test vectors in a separate source file, that can be compiled with
either the reference or the optimised implementation.
13. Optionally provide a Java reference implementation that interoperates
with the C ones. For this treat inputs, outputs, keys etc. as byte arrays
(with the obvious two's-complement mapping between the Java 'byte' type
and octet values). Look at other optimised Java crypto code to see how
to fake unsigned types efficiently, and various other tricks. Put test
code in a separate class from the algorithm.
14. Put up a WWW page from which all of the papers, code, test vectors, etc.
relating to the algorithm are available. Post an announcement about this
page to at least sci.crypt. Keep the page up to date, and reference any
published cryptanalysis of the algorithm from it, including that by other
researchers. If the page is mirrored then use some method that ensures
that mirrors will be kept up to date.
15. Make available, at least as a text file and as C test code, test
vectors for *all variants* of the algorithm, and for a selection of
parameter choices (if it is a block cipher then this should cover all
block sizes, and a selection of numbers of rounds or key sizes, for
example). Include both values that are byte-order-invariant (e.g.
0x12343412 for 32-bit words), and values that are not, for each input
to the algorithm.
16. For the most common parameter combinations, also include a fully
worked out example with intermediate values at each stage of the
computation (including dumps of such things as scheduled keys).
Make sure that the test vectors are sufficient to test all parts of
the algorithm (e.g. encryption and decryption, or signing and verifying).
In the case of non-deterministic algorithms, e.g. a public key
algorithm with a randomised padding method, give test vectors that
use fixed values for the random input. For yes/no tests give both
values that should pass, and values that should fail for various
different reasons, if applicable.
17. Don't revise papers, implementations, test vectors, etc. without stating
that they have been revised, and when. Make sure that all on-line versions
are up-to-date, using Archie and Metacrawler to search for any copies
you might not otherwise know about. Also give a brief summary of what
has changed.
18. If an algorithm is modified incompatibly, give the modified version a
new name. Don't change the name for simple mistakes such as typographical
errors that are found soon after publication (but see 17). If the spec
and the reference implementation are found to be inconsistent, consider
carefully which one needs to be changed, or whether it is better to
define a new version, considering both disruption and security
consequences.
19. Make papers available on-line in at least PDF and Postscript formats,
and preferably also as the original source (e.g. LaTeX or whatever).
Use an HTML page that has an abstract of the paper and links to the
various formats, and recommend that links from other sites be made to
this page rather than directly to the .pdf/.ps files.
Some journals have restrictions on when a paper submitted to them
can be made publically available; in that case put it on-line as soon
as possible within those restrictions. Put a reference to the algorithm's
web page in the journal version.
20. If the algorithm is ever broken (perhaps not completely, but enough
that you no longer recommend its use), say so on the web page, and
post an announcement of that to sci.crypt.
- --
David Hopwood <david....@zetnet.co.uk>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
iQEVAwUBPC67kjkCAxeYt5gVAQGzwgf/V1Aw5xgrdO2+DswB7R6Bynn7vPbBUtDx
U5skopjad+f2zGBRpM+TlKqhQ2FagHsG8wAEv/nNT1NCxyIsGYLzzZn5uUS+KWo9
ZSMA2AExwgI/za8nFdHCDt9v18asPvyo8L93qzzga8xCb41Gb6kYWZ/k0S5vT7DM
RmgmDuGSKG2sU9QqrUvt2MGKu5ay2Ufjn7Aj77RxsYhj2zzrY06j06S8ZrMgRiMV
WJwpK23Wloj6g8hn6xDHgiBvz7NpqbcxolMYtindla2xeJFQxoh4Z9opJRzZSSXU
uLE/4keLuM86tvGGLCcEmhtLL2sz1GNwrQ3i/QUlbJl7GxNHOVDzpg==
=/hcB
-----END PGP SIGNATURE-----
Brian Gladman
news:3C2E9908...@zetnet.co.uk...
> -----BEGIN PGP SIGNED MESSAGE-----
>
> "Douglas A. Gwyn" wrote:
> > Brian Gladman wrote:
> > > In fact a great deal of effort in writing the AES FIPS was devoted to
> > > AVOIDING any concept of numeric significance
>
> Then all that effort has been counterproductive.
I don't think so unless you mean that this objective has not been achieved.
> > > because all AES bytes represent
> > > finite field elements and this means that they (and their component
bits)
> > > have no numeric interpretation and hence no numeric significance of
any
> > > kind.
> > > The critical section of the FIPS in this respect (3.2 in the FIPS, 1.2
in
> > > my FIPS input) took several weeks to get right precisely because Joan
> > > Daemen and Vincent Rijmen wanted to ensure that there was no possible
> > > numeric interpretation of this critical definition of a 'byte'.
>
> Why on earth would they want that? An octet value is defined as an integer
> between 0 and 255 inclusive, and 'byte' is a synonym for octet here. So a
> numeric interpretation is absolutely essential for interoperability. All
> architectures, protocols, and programming languages that use octets have
> a well-defined mapping to this numeric definition [*], but most do not
> specify any mapping to bit sequences.
At the AES cipher interfaces the term byte refers to an ordered sequence of
8 bits - nothing more and nothing less - this sequence is given no other
semantics of any kind. The term 'octet' was consciously avoided because it
carries too much semantic baggage.
External to the AES cipher it may be that this 'interface byte' will
actually be a character (or part of a string), an integer (or part of an
integer), part of a floating point number, an octet in a comms protocol,
...., or any of an effectively infinite number of possible semantic
interpretations. Internal to the AES cipher the semantics are defined as
those of a finite field.
Given that the internal and external semantics will almost always be
different the best solution in my view is not to attach any non-essential
semantics to interface bytes in their own right. Hence I believe that
treating them only as ordered sequences of 8 bits makes most sense.
Also AES must work in both hardware and software so we do not have the
luxury of leaving bits unordered (or unnamed), as some would seem to
advocate.
> The convention used for the hexadecimal notation implies that bit 0 is
> intended to be the least significant bit within each octet (and that is
> what the Rijndael reference implementation assumes). However, it's
> impossible to specify the interface between AES and any real-world system
> that uses octet strings without mapping the elements of GF(2^8) to
integers,
> and so this mapping should have been stated explicitly in the FIPS.
No. The FIPS does not know the external semantics since these will be set by
the application designer. The job of the FIPS is to specify the
***internal*** semantics applied to the bit sequences at the AES interfaces.
The AES interfaces provide a semantic transformation between the internal
and external semantics and any effort by the FIPS team to set the external
semantics would have gone beyond their mandate, which is for the internal
semantics alone.
> (A mapping to bit sequences is not needed at all, and is simply confusing:
> for example if we use a serial comms protocol with little-endian bit
ordering,
> such as RS-232, a sensibly defined system will end up with the bits in
each
> octet being transmitted on the wire in the opposite order to that defined
> in the draft FIPS.)
A mapping to bit sequences (or more strictly setting a unique identity for
each indiviual bit in the interface) is necessary to ensure that hardware
and software implementations can produce the same results.
[snip]
No, this is plain wrong since the AES specification covers the internal
semantics, which are those of a finite field. The value 0x57 does NOT refer
to an integer, it refers to a finite field element for which the polynomial
coefficients are determined by the notation set out in section 1.2 of the
FIPS. If you were to interpret this as an integer the algorithm would fail
because the semantics would be wrong. And the hexadecimal notation used is
carefully defined to avoid any possible interpretation as an integer
precisely because it is NOT an integer.
> However, as Brian Gladman says, the FIPS carefully avoids defining any
> such mapping, misguidedly IMO. Implementors shouldn't have to guess based
> on the convention for writing field elements in hexadecimal. I hadn't
> realised that this had changed from the Rijndael spec, otherwise I would
> have made a comment to NIST.
It did not change. The FIPS interpretation was that which both Joan Daemen
and Vincent Rijmen always intended.
Where I suspect we will agree is that the FIPS should have made this clear
by explicitly covering the issue. In my contribution to the draft FIPS I
wrote a section on this but it did not make it into the final document.
Brian Gladman
Brian Gladman
If you wish to debate whether or not finite field elements are, or are not,
numbers, I am happy to do so but I suggest that we do it off-line.
Since, in this debate, you have been advocating numeric significance as a
way of identifying bits, I was assuming that your numbers would have to be
entities that could be ordered in terms of their numeric significance, that
is, like integers.
But you will find if you look into the semantics of finite fields that their
elements cannot be ordered by their 'numeric significance' since they have
none. It is hence not possible to say (in any conventional sense) that one
such element is larger or smaller than another.
Hence, using FIPS-197 conventions, the finite field elements {00000010} and
{00000100} can only be said to be different - neither can be said to be
'larger' or 'smaller' than the other.
Which is why numeric significance is not a sensible way of identifying bits
in this context because the entities we are dealing with do not posess this
property.
Brian Gladman
Brian Gladman
>
> Brian Gladman wrote:
[snip]
> > In all cases, however, I would not want to assume anything. I would
expect
> > in technical specifications that the convention employed would always be
> > described so that I did not have to guess what the originator intended.
>
> O.k. There was a tiny flaw in what I wrote. A number
> could be a fraction and could even be negative etc.
> But in crypto we are dealing with binary whole numbers.
No. What is presented to an encryption algorithm might be a number but it
might equally be a string of characters, a finite field element, a user
defined data structure, ....., and so on. The algorithm designer has no
knowledge of the external (to the algorithm) semantics of what is presented.
In AES (and IIRC DES) the interface semantics are enumerated bit sequences,
not numbers.
> In that case the convention that the rightmost bit
> is associated with 2^0, the next bit is associated
> with 2^1, etc. is universally accepted, isn't it?
I don't know for certain whether this is true or not. Hence I would want it
explicitly stated in any specification - this does not cost much and avoids
the problem that there may be some culture where this convention does not
hold.
> We should not let the fact that some computer
> architectures store the bits of a binary number in a
> different way to force us to do any extra stuff in
> writing a (in principle abstract) specification that
> deals with essentially math.
As far as I am aware, no-one is trying to stop people writing numbers (as
this term is understood by the public) with the most significant digit on
the left.
The AES specification is an abstact specification in which the principal
entities involved are NOT integers but instead finite field elements. In
consequence we cannot sensibly attach the semantics of integers to them.
Since it seems unlikely that AES users will want to be told that they have
to convert all their data into finite field elements (which 99.99..% of
users won't even understand), it makes sense to remove these internal
semantics at the interface by simply designating the entities involved as
enumerated sequences of bits or bytes. Having done this, external users can
then 're-attach' their own semantics to these bit or byte sequences -
numbers, strings, octets or whatever.
[snip]
Brian Gladman
Mok-Kong Shen
Brian Gladman wrote:
>
[snip]
> The AES specification is an abstact specification in which the principal
> entities involved are NOT integers but instead finite field elements. In
> consequence we cannot sensibly attach the semantics of integers to them.
In other followups, there were mention of the issue
of bit ordering in bytes/octets etc. Would the following
way of (abstract) specifiction be sufficient for the
standard document? One declares that the block of
plaintext/ciphertext of 128 bits and the key of 128
bits (analogously for other key sizes) are considered
as binary (positve) integers to be denoted by
P[128]/C[128] and K[128], with index beginning at 0
(similar to C notation). For then any bit can be
unabiguiously referenced in the document and similary
for units of any size, e.g. the lowest plaintext byte
is identified as P[0..7]. How the computer store these
bits, bytes, etc., in particular what kind of 'endians'
they use, are of no more concern, isn't it?
M. K. Shen
Brian Gladman
You can specify that bit numbers will be set by the power of two that a bit
represents in a 128-bit unsigned integer. And then you can say that P[0..7]
is byte[0] and so on.
But there is no need to introduce integers because it is sufficient to
number the bits in all the blocks.
In order to understand cipher specification it is necessary to distinguish
between the operations going on inside the cipher - controlled by the
internal semantics - and those going on outside the cipher - controlled by
the external semantics. The cipher interface is a slightly permeable
chinese wall between these two worlds - just slightly permeable because we
do allow the semantics of enumerated bit sequences to pass from one side to
the other.
Given a complete enumeration of the bits in the plaintext, the ciphertext
and the key, the internal semantics of a cipher can be completely specified
(in principle) by decribing how each ciphertext bit is dependent on each
plaintext and each key bit.
Hence if X{i} is the i'th bit in bit sequence X:
C{0} = Function0(P{0},P{1},...,P{127}, K{0},K{1},...,K{127})
C{1} = Function1(P{0},P{1},...,P{127}, K{0},K{1},...,K{127})
....
C{127} = Function127(P{0},P{1},...,P{127}, K{0},K{1},...,K{127})
We do not need to do any more than this since, for example, introducing
integers would imply relationships between bits (for example, numeric
significance) that are not necessarily present. AES, for example, does not
involve integer semantics in its internal handling of bit sequences.
And the external semantics are outside the scope of the cipher
specification. If you want the external semantics of integers (or octets,
or whatever else takes your fancy) simply specify how the semantics for
these entities are to be mapped onto the bit sequence semantics at the
cipher interfaces.
Brian Gladman
Mok-Kong Shen
Brian Gladman wrote:
>
Agreed. (I was thinking invoking the concept of an integer
could be a easily comprehensible way of specifying the
ordering of bits.) One should hence simply say in the
specification that the block of bits are numbered from 0
at the right end till 127 at the left end and similarly
for the key and leave all the storage issues/problems to
the persons doing the implementation, whatever these
may be.
M. K. Shen
David Hopwood
> Brian Gladman wrote:
> > You can specify that bit numbers will be set by the power of two that a
> > bit represents in a 128-bit unsigned integer.
But the AES FIPS does not specify anything like that. If it did (for 8-bit
rather than 128-bit integers), there would be no problem.
> > And then you can say that P[0..7] is byte[0] and so on.
> >
> > But there is no need to introduce integers because it is sufficient to
> > number the bits in all the blocks.
It is not sufficient to number all the bits. Cipher interfaces are not
defined in terms of bit sequences; they are defined in terms of octet
sequences [*]. An interface defined using bit sequences isn't directly
useful - we can't store a bit sequence in a file, or transmit it using
network protocols above the physical layer, without first representing
it as an octet sequence. For almost every other commonly used cipher
(including DES and the other AES candidates) [*], and also for every hash
function and MAC that I know of, the mapping of plaintexts, ciphertexts
and keys to octet sequences is part of the algorithm specification.
[*] Except for some stream ciphers, e.g. SEAL and several variants of
WAKE, which specify plaintexts and ciphertexts as sequences of 32-bit
words (although they still specify keys as octet sequences).
In practice this means that there are big- and little-endian variants
of SEAL and WAKE that do not interoperate. For these ciphers, though,
there is some justification in that the big-endian (resp. little-endian)
variants avoid byte order conversion on big-endian (resp. little-endian)
architectures.
For Rijndael/AES, OTOH, there is no benefit whatsoever in failing to
specify the mapping to octets - it doesn't have any effect on
efficiency.
The definition of AES would be complete if FIPS 197 did any of the
following things:
- give a bijection between polynomials in GF(2^8) and integers 0..255.
The correct bijection is:
b_7.x^7 + b_6.x^6 + b_5.x^5 + b_4.x^4 + b_3.x^3 + b_2.x^2 + b_1.x + b_0
<->
b_7.2^7 + b_6.2^6 + b_5.2^5 + b_4.2^4 + b_3.2^3 + b_2.2^2 + b_1.2 + b_0
- give the order of bits within an octet; i.e. whether the first bit
in an octet, written on the left in the FIPS, is most significant
("big-bit-endian") or least significant ("little-bit-endian").
The answer is big-bit-endian.
- say which bit numbers in an octet are most and least significant.
The answer is bits 7 and 0 respectively.
- say which bit of a *block* corresponds to the MS bit of the first
octet. The answer is the first bit, numbered 0.
- say whether the hexadecimal representation 'HL' corresponds to
the integer 0xHL. It does.
- say whether the binary representation {A B C D E F G H}
corresponds to the integer ABCDEFGH in binary. It does.
However, the FIPS does not specify any of this, despite the fact that all
current Rijndael implementations assume (and rely on) the answers I've
just given.
> > Given a complete enumeration of the bits in the plaintext, the ciphertext
> > and the key, the internal semantics of a cipher can be completely specified
> > (in principle) by decribing how each ciphertext bit is dependent on each
> > plaintext and each key bit.
> >
> > Hence if X{i} is the i'th bit in bit sequence X:
> >
> > C{0} = Function0(P{0},P{1},...,P{127}, K{0},K{1},...,K{127})
> > C{1} = Function1(P{0},P{1},...,P{127}, K{0},K{1},...,K{127})
> > ....
> > C{127} = Function127(P{0},P{1},...,P{127}, K{0},K{1},...,K{127})
> >
> > We do not need to do any more than this since, for example, introducing
> > integers would imply relationships between bits (for example, numeric
> > significance) that are not necessarily present.
One of the purposes of a standard is to define things that would otherwise
be arbitrary, whenever that is needed to ensure interoperability. There are
enough variants of Rijndael already, without multiplying that number by
two for frivolous reasons.
> > AES, for example, does not
> > involve integer semantics in its internal handling of bit sequences.
What relevance does that have? Serpent doesn't use integer operations
internally either (only XORs, shifts and S-boxes), but it specifies
mappings to integers for input and output.
> > And the external semantics are outside the scope of the cipher
> > specification.
They weren't outside the scope of DES, or any of the other AES candidates.
AES is supposed to be a replacement for DES and 3DES, so it had better have
the same form of interface (as far as possible, given the necessary changes
to block and key sizes).
> > If you want the external semantics of integers (or octets,
> > or whatever else takes your fancy) simply specify how the semantics for
> > these entities are to be mapped onto the bit sequence semantics at the
> > cipher interfaces.
There is only one correct, interoperable way of doing this for Rijndael/AES.
The opposite ordering is wrong, and NIST should say that it is wrong.
PS. I don't seem to be receiving any of your posts except quoted in
follow-ups. Please cc: any replies in this thread.
- --
David Hopwood <david....@zetnet.co.uk>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
iQEVAwUBPC/pIzkCAxeYt5gVAQFuwwgAiDjk8Bwj5eHsbFAq5qP5n9z3TM5mJUAq
car8ESu9QP/8miwJHme46rXMqII/2OGo6xkgAp0aFbytdzal5tH4eVYKLEs709Ym
1vrkOzRMFvN5HgsD50F+FgL3vkOMT7oQ2rQrD2W7y9hnVAmcRpdjLNKKvFZmVp2f
eAhDwZiU5EaDYsELuKP09G1ZM5Zi2mn8xz5JkZs9cruELzDPkUH72NqFLyAa0Jc8
D+BOPc0J8U+AZeKViPRiZfblf+MSs8GZDqv01CtoMdImHaWlgvJm1ywjhxBKJun3
3OQGGHY9+JDIuT13oV7hUReM0OAXHpSaF+VmS/QFzuGfc685F4kfiA==
=cRGR
-----END PGP SIGNATURE-----
Douglas A. Gwyn
> ... If you were to interpret this as an integer the algorithm would
> fail because the semantics would be wrong.
Nobody is saying, replace the finite field with integers for
computation. What we're saying is that there is a need, for
information interchange purposes, to know the representation
of the field elements. An obvious mapping is to map the hex
AES notation to integer values in the usual way. Of course
there are a large number of *possible* mappings, but it is
less than clear that it is useful to allow them all.
Douglas A. Gwyn
> Since it seems unlikely that AES users will want to be told that they
> have to convert all their data into finite field elements (which
> 99.99..% of users won't even understand), it makes sense to remove
> these internal semantics at the interface by simply designating the
> entities involved as enumerated sequences of bits or bytes. Having
> done this, external users can then 're-attach' their own semantics to
> these bit or byte sequences - numbers, strings, octets or whatever.
It's not a matter of "users" understanding or not, it's the simple fact
that abstractions don't exist as such in the computer, thus they have
to be concretely *represented* using bit values. Collections of bits
are just collections of bits, but we still need to know where each bit
should be placed.
Brian Gladman
Which is what cipher users do when they specify the semantics of their
external (to the cipher) entities at the cipher interface.
Brian Gladman
Brian Gladman
> Brian Gladman wrote:
> > ... If you were to interpret this as an integer the algorithm would
> > fail because the semantics would be wrong.
>
> Nobody is saying, replace the finite field with integers for
> computation. What we're saying is that there is a need, for
> information interchange purposes, to know the representation
> of the field elements.
If the information exchanges you are considering are conducted by parties
that are all external to the operation of the cipher (outside rather than
inside the cipher interface) then the internal representation of the finite
field elements is completely irrelevant. External users don't even need to
know that finite fields are involved.
All that matters in this case is that that the exact original plaintext bit
sequence is recovered by decryption. If these bits were ordered in some way
before encryption, then this same order will reappear after decryption
without imposing any bit order constraints on the internal workings of the
cipher. The 'encryption followed by decryption' operation must recover any
order that exists in the original plaintext since to do otherwise would mean
that some of the original plaintext bits would have to be put in the wrong
positions.
I may be wrong but it seems to me that people are getting confused between
the internal and external semantics of the cipher interface. Except for the
shared semantics of enumerated bit sequences, the internal and external
semantics can be completely decoupled.
If an application involving interoperability requires bits to be ordered
then it must define a bit order. On the other hand if an application does
not care about bit order it does not need to do this. AES (Rijndael) will
serve either equally well since this is an application issue, not one for
any cipher that may be in use.
Brian Gladman
Brian Gladman
Apologies for answering twice but I have realised that I missed something in
your comment.
It is important to note that the entities we are dealing with are NOT
'collections of bits' but 'enumerated collections of bits'.
In other words we don't just require that we have N bits but we also require
that we can uniquely identify each of the individual bits in the collection.
In the case of AES (Rijndael) we 'name' each bit using an enumeration.
And once we have named each bit we then have sufficient information to
completely and unambigously define the way in which each bit is represented
in any implementation.
Brian Gladman
Mok-Kong Shen
Brian Gladman wrote:
>
> If the information exchanges you are considering are conducted by parties
> that are all external to the operation of the cipher (outside rather than
> inside the cipher interface) then the internal representation of the finite
> field elements is completely irrelevant. External users don't even need to
> know that finite fields are involved.
>
> All that matters in this case is that that the exact original plaintext bit
> sequence is recovered by decryption. If these bits were ordered in some way
> before encryption, then this same order will reappear after decryption
> without imposing any bit order constraints on the internal workings of the
> cipher. The 'encryption followed by decryption' operation must recover any
> order that exists in the original plaintext since to do otherwise would mean
> that some of the original plaintext bits would have to be put in the wrong
> positions.
You are right. A fancy AES could even be a blackbox with
128 pins for input of the plaintext block ordered on a
circle or in any random positions. There need only be a
numbering of 0-127 for these. Internally, the specification
would say that the bits numbered 0-7 are the coefficients
of a polynomial constituting an element of GF(2^8), etc.
M. K. Shen
David Hopwood
"Douglas A. Gwyn" wrote:
> Brian Gladman wrote:
> > Since it seems unlikely that AES users will want to be told that they
> > have to convert all their data into finite field elements (which
> > 99.99..% of users won't even understand), it makes sense to remove
> > these internal semantics at the interface by simply designating the
> > entities involved as enumerated sequences of bits or bytes.
Indeed it does. So which interface should be defined: bit sequences,
byte (=octet) sequences, or both?
FIPS 197 flatly and intentionally refuses [<anthropomorphising wildly>]
to specify an octet-sequence interface, despite that being the more
useful type of interface in practice. There would be nothing to prevent
it from defining both types (although that is not ideal; see below).
Bit-sequence interfaces tend to be very rarely used even when they are
defined, as we can see from the example of hash functions: most
cryptographic hashes (with the exceptions of GOST-Hash and Snefru, IIRC),
define bit-sequence interfaces, but very few implementations of those
hashes support them.
I said that defining both types of interface isn't ideal; here's an
example of what can go wrong. P1363a defines a Message Authentication
Code construction called MAC1, based on HMAC. MAC1 is specified as
follows:
- if the input is given as an octet string, convert it to a bit string
using the primitive OS2BSP (which assumes big-bit-endian order).
- apply the version of HMAC defined in X9.71 (which treats everything
as bit sequences).
There's no ambiguity here: the bit order to be used is clearly specified.
However, suppose I want to use a little-bit-endian hash function, such as
RIPEMD-160, with MAC1. I have to reverse the order of bits in every octet!
There is no other way to implement it, because RIPEMD-160 uses integer
operations internally. Bit reordering is not a particularly efficient
operation in software: the fastest practical way I can see to implement
it requires a lookup in a 256-element table for each octet of the message.
Even worse, for a little-bit-endian hash, MAC1 is incompatible with the
original version of HMAC in RFC 2104, which uses octet-sequence operations
exclusively. Note that it is incompatible even when used by a scheme that
only gives it octet-sequence inputs.
If there were no little-bit-endian hashes like RIPEMD-128/160, HAVAL, or
Tiger, then this kind of problem wouldn't arise. However, RIPEMD-128/160
uses little-endian ordering of octets within words (for speed on x86
processors), and it is little-bit-endian for consistency with that choice.
The designers of Tiger thought that this consistency between bit and
octet ordering was so important that they even changed their algorithm
incompatibly (from big- to little-bit-endian) in order to obtain it.
Presumably, the same arguments could be applied by designers of new
ciphers, if it became popular to define bit-sequence interfaces for them.
My considered conclusion is that bit-oriented protocols (that is, those
that are defined in terms of bit-sequence interfaces) are simply a bad
idea, and should not be encouraged - given the computing infrastructure
we have now where almost all existing protocols are octet-oriented.
An effective way of discouraging them is to only define octet-sequence
interfaces for new algorithms, which is one reason why the "suggestions
to crypto algorithm designers" I posted recommends that.
In any case, given that the AES FIPS has already been published with a
bit-sequence interface, the least bad option now is to define an
octet-sequence interface to AES as well. Clearly this should be the
interface that is already being used by Rijndael implementations, i.e.
the one where 'HL' maps to 0xHL.
> > Having done this, external users can then 're-attach' their own
> > semantics to these bit or byte sequences - numbers, strings, octets
> > or whatever.
That's exactly what MAC1 does (attach octet semantics to a bit-
sequence). This is *not* equivalent to having the most useful form of
interface specified once-and-for-all for each algorithm; it is strictly
worse: more hassle and potential for error, more non-interoperable
options that protocol designers may choose differently, and less efficient
in some cases.
Note that a bit-sequence interface cannot be more efficient than an
octet-sequence interface. (A word-sequence interface potentially could be
more efficient if it happened to fit the implementation architecture
well, although not for Rijndael/AES, because Rijndael is
neutral-octet-endian: it does not use any arithmetic operations on words.)
Doug Gwyn wrote:
> It's not a matter of "users" understanding [finite fields] or not, it's
> the simple fact that abstractions don't exist as such in the computer,
> thus they have to be concretely *represented* using bit values.
> Collections of bits are just collections of bits, but we still need to
> know where each bit should be placed.
There is a subtle but important difference between this argument and the
one I made above. Abstractions have to be represented concretely, yes,
but we do not need to, and SHOULD NOT, have an algorithm or protocol
standard require specific internal representations. [*]
The issue with the AES FIPS is one of external representation. ("External"
doesn't necessarily mean on-the-wire or in a file format; it can include
interfaces between components of a system, such as between a crypto library
and an application.) It's not that the FIPS doesn't define an external
representation for AES blocks and keys, it's that it defines the *wrong
type* of representation - literally, for the programming language/type
theory definition of "type".
[*] Giving non-normative advice about efficient representations in an
appendix of a specification is fine, as is noting cases where the
choice of representation may make a difference to security against
side channel attacks.
In practice it often makes sense to use an internal representation
that is the same as, or corresponds very directly to, the external
representation (for example, implementing the Rijndael S-box using the
same mapping between GF(2^8) and {0..255} as the external mapping).
The decision of whether to do that, or to use a different internal
representation, can safely be left up to implementors.
In another article, Brian Gladman wrote:
> David Hopwood wrote:
> > > Brian Gladman wrote:
> > > > AES, for example, does not
> > > > involve integer semantics in its internal handling of bit sequences.
> >
> > What relevance does that have?
>
> It is important in all specifications not to specify things that don't need
> to be specified. If we did not adopt this strategy, specifications would
> become full superfluous and confusing details which would obscure those that
> are truly necessary. I can assure you that AES (Rijndael) does not require
> bits to be ordered, it only requires that they be identified. Hence if we
> were to impose an unecessary ordering relationship we may well constrain
> implementors to maintain a property - bit ordering - that does not need to
> be maintained.
The current FIPS defines the order of bits within a block. *That* is arguably
the overspecification, since octet-oriented protocols have no need to know
that order. What needs to be specified is the order of octets within a block,
and the values of the octets.
Either type of interface is sufficient to fully specify the algorithm for
protocols that use that interface. The difference is in how the bits are
labelled. An octet-sequence interface (for an algorithm with 128-bit blocks)
labels the plaintext or ciphertext bits like this:
bits {0..7} of octet 0 }
bits {0..7} of octet 1 } block 0
: }
bits {0..7} of octet 15 }
bits {0..7} of octet 16 }
bits {0..7} of octet 17 } block 1
: }
bits {0..7} of octet 23 }
Note that "{0..7}" here represents a set of bit numbers, not a sequence
of bit numbers. I.e. a convention is defined for labelling bits (bit 0
being the least significant), but there is no need to specify which bit
is "first" within an octet. This is consistent with the semantics of
Internet protocols, most other network protocols, flat files in Unix-derived
filesystems, integer types in all programming languages that I know of, and
the APIs of all *portable* crypto libraries (that is, libraries that make
some attempt to work consistently across platforms).
A bit-sequence interface labels bits like this:
bit 0 of block 0
bit 1 of block 0
:
bit 127 of block 0
bit 0 of block 1
bit 1 of block 1
:
bit 127 of block 1
This is consistent with the BIT SEQUENCE type in ASN.1, and is used by
a few ISO and ANSI crypto protocols (e.g. the X9.71 protocol mentioned
above), but that's about all: hardly any commonly used standards support
or depend on representing bit sequences directly.
In hardware, it makes no substantive difference which type of interface is
used - the only effect is on how the 'wires' are labelled. In software,
however, or when interfacing between software and hardware, a standardised
octet-sequence interface is desirable in order to avoid ever having to
reverse the order of bits within octets.
> My own implementation
<http://fp.gladman.plus.com/cryptography_technology/rijndael/index.htm>
> makes use of this freedom by mapping shifts to higher index positions to
> left shifts on little-endian machines and to right shifts on big-endian
> machines [in the key scheduling code].
You're mistaken about the reason why this works. The FIPS talks about 32-bit
words in the description of key scheduling, but what it actually means by a
"word" is a sequence of 4 octets - <x[0], x[1], x[2], x[3]>, say. Since no
arithmetic operations are used on "words", Rijndael and AES are
neutral-octet-endian. However, it's still possible to pack the 4 octets into
a 32-bit processor register with x[0] in either the most significant or least
significant 8 bits, whichever is more convenient for optimising the memory
accesses and shifts. This is purely an internal representation choice, and
has no interaction with the cipher interface.
Another way to see this is to look at the code that verifies test vectors:
all the test vectors have 'HL' mapping to 0xHL. The change I'm suggesting
is simply to require that mapping, and so your implementation would still
be conformant (assuming it is conformant now; I haven't looked at all of the
code in detail).
> By doing this I avoid the input/output order
> conversion that would have to be done on one of the two architectures and
> hence obtain the same speed on both architectures.
That has nothing to do with bit order. Your implementation uses the same
octet-sequence interface to Rijndael on both architecture types. If it
didn't, it wouldn't pass the test vectors, which you've interpreted
(correctly) as being big-bit-endian regardless of architecture.
> An advantage of Rijndael is hence that it is 'endian neutral' and we would
> loose this advantage if we imposed an unnecessary endian convention in the
> specification.
Rijndael can be neutral-bit-endian (that is, the order of bits within octets
does not matter) if-and-only-if it is specified as having only an octet-sequence
interface, *or* only a bit-sequence interface. An algorithm that has both
cannot possibly be neutral-bit-endian. The octet-sequence interface is far
more important, so if the designers considered the neutral-bit-endian property
to be desirable, then only that interface should have been specified.
Rijndael is neutral-octet-endian (the order of octets within words does not
matter) regardless of what is done about the bit order issue. It is the
neutral-octet-endian property that implies that Rijndael is equally
efficient on big-endian (i.e. big-octet-endian) and little-endian (i.e.
little-octet-endian) processor architectures.
> > There is only one correct, interoperable way of [mapping blocks and
> > keys to octet sequences] for Rijndael/AES.
> > The opposite ordering is wrong, and NIST should say that it is wrong.
>
> I dont agree. I see no basis for saying that one bit ordering convention
> is correct and another is wrong.
We're talking specifically about AES here, not bit ordering in general.
If all the existing implementations use that convention (they do), and if
there is no advantage to using the other convention (there isn't), then
why not specify the octet-sequence interface properly, instead of leaving
implementors to guess what it should be?
> This is like saying that all processors must be little-endian.
No. There are three possible options that allow for the kind of
interoperability that we currently have between different architectures,
network protocols, and stored data:
A. Make all protocols and architectures appear consistently little-endian.
B. Make all protocols and architectures appear consistently big-endian.
C. Represent all data externally as sequences of integers of a
standardized chunk size, and make all memory architectures
chunk-addressable.
As pointed out in IEN 137 (cited in a previous article), if A or B is chosen,
then C isn't necessary. However, if neither A nor B is chosen, then it's
essential to standardise the chunk size, because that provides a way of
transferring arbitrary data between systems that use different orderings
of chunks within words, or of bits within chunks.
What actually happened is that option C was chosen, with a chunk size of
8 bits. If none of the options had been chosen, we would have had a complete
mess, and something like the Internet would not have been possible without
first resolving that mess.
> Moreover I am not aware of any authority that has the absolute power
> required to impose one particular bit ordering convention.
NIST is the authority for the specification of AES. There is another version
of AES, though, that was designed by people from a mirror Earth orbiting on
the opposite side of the Sun, where numbers are written down least significant
digit first. If the two versions of AES ever meet, they will annihilate each
other in a flash of broken and non-interoperable protocols. Unfortunately
some insurgents from the mirror Earth seem to have infiltrated the NIST on
our own Earth, with the aim of making sure that both versions are allowed by
the standard...
[please cc: any replies]
- --
David Hopwood <david....@zetnet.co.uk>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
iQEVAwUBPDJG2TkCAxeYt5gVAQFp0Af+LAApOcH0GwY4tpI+UADoiE/C9sXVQ0MZ
dx0+VmT6nZx4VN+OeXqZUV1VlKnJ1w2IwZqm02/iT7FiAFDVS7/d+lZyJrh7Wwk/
0nMWkbP/k6W76zuFzT4ps0/bcshh6RBdPoS+4c0UE5tBVcRdNqfkbJ35ymKvc75o
u/yCnR/IYYd8bDrH+LjZQwnelPMwSpPMJIo/2cywRWIMMoHZFjadjyd7M1BqdQ+h
vhEjcTQWpSOKfHamn9hZtXdVNP09lZZ1jVYnktt3X7G/KZaC+uSvKD+UlP8zXsal
a9caDbgxkhPiuib7JWnGoH7wSci8VdBFxYo+5mWILJ7cgou5nqYlWw==
=5zxf
-----END PGP SIGNATURE-----
David Hopwood
David Hopwood wrote:
> Brian Gladman wrote:
> > My own implementation
>
> <http://fp.gladman.plus.com/cryptography_technology/rijndael/index.htm>
>
> > makes use of this freedom by mapping shifts to higher index positions to
> > left shifts on little-endian machines and to right shifts on big-endian
> > machines
> [in the key scheduling code].
On closer inspection this is not just in the key scheduling code. That
makes no difference to my argument (that specifying the bit order has no
effect on this optimisation), though.
I also noticed the following in aes.h:
a) when PACKED_IO is not defined, EXTERNAL_BYTE_ORDER *must* be set to
the byte order of the underlying platform. Also this option strictly
speaking invokes undefined (not just implementation-defined) behaviour
according to Standard C, and may cause problems in practice with
unaligned memory accesses on some platforms.
b) when PACKED_IO is defined, EXTERNAL_BYTE_ORDER *must* be set to the
same value as INTERNAL_BYTE_ORDER. (That is, the definition
"#define word_in(x) bytes2word((x)[3], (x)[2], (x)[1], (x)[0])"
and the following definition in aes.h are always incorrect if they
are used.)
The documentation in aes.h and aes.c doesn't make this sufficiently clear,
IMHO. I also don't think that a) should be the default, as it appears to be.
May I suggest replacing the end of aes.h (starting from
"#if (INTERNAL_BYTE_ORDER == EXTERNAL_BYTE_ORDER)") with the following:
#if defined(PLATFORM_BYTE_ORDER)
/* Note that this may invoke undefined behaviour on some platforms.
* To conform to Standard C, do not define PLATFORM_BYTE_ORDER. */
#if (INTERNAL_BYTE_ORDER == PLATFORM_BYTE_ORDER)
#define word_in(x) *(t_name(word)*)(x)
#define word_out(x,v) *(t_name(word)*)(x) = (v)
#else
#define word_in(x) byte_swap(*(t_name(word)*)(x))
#define word_out(x,v) *(t_name(word)*)(x) = byte_swap(v)
#endif
#else
/* !defined(PLATFORM_BYTE_ORDER), so use byte-order-independent code. */
#define word_in(x) bytes2word((x)[0], (x)[1], (x)[2], (x)[3])
#define word_out(x,v) { (x)[0] = bval(v,0); (x)[1] = bval(v,1); \
(x)[2] = bval(v,2); (x)[3] = bval(v,3); }
#endif
where PLATFORM_BYTE_ORDER would not be defined by default. This needs
thorough testing for all options and platforms, of course, but I'm pretty
sure it is correct.
Another request: it would be nice if the code compiled cleanly with
"gcc -Wall -pedantic" (it is quite close already).
- --
David Hopwood <david....@zetnet.co.uk>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
iQEVAwUBPDJxwTkCAxeYt5gVAQFRXwf/eC6n7JmzQcqRLm+EtlE9ORP4dtvofi7d
6NWUv4AN/B1+Pvy6H+wy9lWUHBhl+4yjXFLi4YHQpDK47HFandZxq0OMfjrrbAbI
kL8G7UBPTw0hdc7dHx9z1IRakQn4aMBXpUvSPp98izChfwJEXpVGssqyfWE1nGxP
gs6exrV9DRXZcmxpTCXN/C8KpInK77EgRN++PtoDCI0DV6lgkm+RxWpSp2i+yolJ
DAAGVuPfxw3JlAeYILjfJLgGT2iz9Dsyl1ZnRxUS6UYwWoiZoikVlqclEA7GDFnK
3SiNHjrICfyRpeZ0k8jmeWe4d7djuijeDFxIoALBETysTfVLQ0YdGA==
=BkwS
-----END PGP SIGNATURE-----
Brian Gladman
> -----BEGIN PGP SIGNED MESSAGE-----
>
> "Douglas A. Gwyn" wrote:
> > Brian Gladman wrote:
> > > Since it seems unlikely that AES users will want to be told that they
> > > have to convert all their data into finite field elements (which
> > > 99.99..% of users won't even understand), it makes sense to remove
> > > these internal semantics at the interface by simply designating the
> > > entities involved as enumerated sequences of bits or bytes.
>
> Indeed it does. So which interface should be defined: bit sequences,
> byte (=octet) sequences, or both?
This is good since we now seem to be agreeing that this is an issue of
defining the external semantics of the interface not the internal semantics.
Since section 1.2 of the FIPS deals with internal semantics, its contents
are not directly relevant to this issue.
This is a big step forward from where the debate was a week ago since people
now seem to understand that the internal and external semantics of the
cipher interface can be set largely (although not entirely) independently.
Hence the essential issue we are debating is that of whether there should
have been explicit coverage of the external semantics of the cipher
interface in the FIPS and, if so, what the FIPS should have said. I think
we agree on the first point in - i.e. that this should have been covered
explicitly - but not on the second - i.e. what should have been said.
> FIPS 197 flatly and intentionally refuses [<anthropomorphising wildly>]
> to specify an octet-sequence interface, despite that being the more
> useful type of interface in practice. There would be nothing to prevent
> it from defining both types (although that is not ideal; see below).
> Bit-sequence interfaces tend to be very rarely used even when they are
> defined, as we can see from the example of hash functions: most
> cryptographic hashes (with the exceptions of GOST-Hash and Snefru, IIRC),
> define bit-sequence interfaces, but very few implementations of those
> hashes support them.
>
> I said that defining both types of interface isn't ideal; here's an
> example of what can go wrong. P1363a defines a Message Authentication
> Code construction called MAC1, based on HMAC. MAC1 is specified as
> follows:
Defining both is the worst possible option since it inevitably leads to
ambiguities. It was this situation that caused so much trouble when I was
first involved in implementing the original 15 AES candidiates. IIRC they
adopted six different conventions between them, several of which were
ambiguous because they could not make up their mind whether to use
enumeration order or numerical significance order so they used both for good
measure!
[snip]
> My considered conclusion is that bit-oriented protocols (that is, those
> that are defined in terms of bit-sequence interfaces) are simply a bad
> idea, and should not be encouraged - given the computing infrastructure
> we have now where almost all existing protocols are octet-oriented.
> An effective way of discouraging them is to only define octet-sequence
> interfaces for new algorithms, which is one reason why the "suggestions
> to crypto algorithm designers" I posted recommends that.
I prefer bit level interfaces as, in my view, these provide less opportunity
for ambiguity and error.
In my view we need to three named entities - a key, a plaintext and a
ciphetext. And within each of which we need to name 128 bits (I'll consider
only 128 bit keys for simplicity). Now I simply want to say:
(a) key.bit[i], plaintext.bit[i] and ciphertext.bit[i] for i = 0 to 127,
where the enumeration is used ONLY to name bits, not to order them.
whereas you want to say:
(b) key.octet[i].bit[j], plaintext.octet[i].bit[j],
ciphertext.octet[i].bit[j] for i = 0 to 15 and j = 0 to 7 where the
enumerations are for naming bits and octets (and, possibly, also for
ordering them?)
Both of these can do all that is required but, in my view, (a) is simpler
and hence less likely to be interpreted wrongly.
I agree that a major danger of all enumerations when used only for naming
purposes is that they strongly imply ordering as well. This is why I would
have much preferred this issue to be explicitly covered in the FIPS to make
it clear that the FIPS bit and byte enumerations are being used only for
bit/byte naming and not for bit/byte ordering.
I would also have liked a statement in the FIPS requiring that
implementations should contain a statement setting out how they represent
'aes bits' at the external cipher interface.
> In any case, given that the AES FIPS has already been published with a
> bit-sequence interface, the least bad option now is to define an
> octet-sequence interface to AES as well. Clearly this should be the
> interface that is already being used by Rijndael implementations, i.e.
> the one where 'HL' maps to 0xHL.
>
> > > Having done this, external users can then 're-attach' their own
> > > semantics to these bit or byte sequences - numbers, strings, octets
> > > or whatever.
>
> That's exactly what MAC1 does (attach octet semantics to a bit-
> sequence). This is *not* equivalent to having the most useful form of
> interface specified once-and-for-all for each algorithm; it is strictly
> worse: more hassle and potential for error, more non-interoperable
> options that protocol designers may choose differently, and less efficient
> in some cases.
>
> Note that a bit-sequence interface cannot be more efficient than an
> octet-sequence interface. (A word-sequence interface potentially could be
> more efficient if it happened to fit the implementation architecture
> well, although not for Rijndael/AES, because Rijndael is
> neutral-octet-endian: it does not use any arithmetic operations on words.)
I agree - the issue is that of whether we specify need to specify some form
of bit order as a part of the external semantics of the cipher interface.
In my view, if an application requires bits to be ordered (e.g. encrypting
an integer or transmitting something in a comms protocol) then this should
be specified as a part of the semantics of the application. Equally if an
application does not depend on bit order then it does not need to specify
this. Trying to transfer an application responsibility onto a lower level
cipher is not the right way of handling this in my view. Things should be
specified close to where they matter, not in places where they don't.
> Doug Gwyn wrote:
> > It's not a matter of "users" understanding [finite fields] or not, it's
> > the simple fact that abstractions don't exist as such in the computer,
> > thus they have to be concretely *represented* using bit values.
> > Collections of bits are just collections of bits, but we still need to
> > know where each bit should be placed.
>
> There is a subtle but important difference between this argument and the
> one I made above. Abstractions have to be represented concretely, yes,
> but we do not need to, and SHOULD NOT, have an algorithm or protocol
> standard require specific internal representations. [*]
>
> The issue with the AES FIPS is one of external representation. ("External"
> doesn't necessarily mean on-the-wire or in a file format; it can include
> interfaces between components of a system, such as between a crypto
library
> and an application.) It's not that the FIPS doesn't define an external
> representation for AES blocks and keys, it's that it defines the *wrong
> type* of representation - literally, for the programming language/type
> theory definition of "type".
I agree with most of what you say here. It is important to see the cipher
interface as the dividing line between the 'internal' and 'external' world
in this debate. But I do not, of course, agree that the wrong representation
was chosen.
[snip]
So numeric significance has been chosen to order bits in octets within this
context. In other contexts people are free to make alternative choices.
[snip discussion of my AES code]
This is a different issue. You said there was only one correct way of doing
this, and I simply repeat that I disagree. There are two 'obvious' ways of
doing this and I see no reason for designating one as universally correct
and the other as universally incorrect.
If an octet level interface is used for bit naming and not for bit ordering,
then we are asked to choose between the names '0' to '127' and '0:0' to
'15:7'. In my view the first is simpler than the second. But you seem to
want the second and I have to assume that this is because you want to do
more than just name the bits. But then the interface becomes over specified
(as I think you have said elsewhere) since bit naming alone is sufficient to
completely specify the cipher interface.
> No. There are three possible options that allow for the kind of
> interoperability that we currently have between different architectures,
> network protocols, and stored data:
>
> A. Make all protocols and architectures appear consistently
little-endian.
> B. Make all protocols and architectures appear consistently big-endian.
> C. Represent all data externally as sequences of integers of a
> standardized chunk size, and make all memory architectures
> chunk-addressable.
>
> As pointed out in IEN 137 (cited in a previous article), if A or B is
chosen,
> then C isn't necessary. However, if neither A nor B is chosen, then it's
> essential to standardise the chunk size, because that provides a way of
> transferring arbitrary data between systems that use different orderings
> of chunks within words, or of bits within chunks.
>
> What actually happened is that option C was chosen, with a chunk size of
> 8 bits. If none of the options had been chosen, we would have had a
complete
> mess, and something like the Internet would not have been possible without
> first resolving that mess.
I assume that you mean that C was chosen in this particular applications
context.
> > Moreover I am not aware of any authority that has the absolute power
> > required to impose one particular bit ordering convention.
>
> NIST is the authority for the specification of AES. There is another
version
> of AES, though, that was designed by people from a mirror Earth orbiting
on
> the opposite side of the Sun, where numbers are written down least
significant
> digit first. If the two versions of AES ever meet, they will annihilate
each
> other in a flash of broken and non-interoperable protocols. Unfortunately
> some insurgents from the mirror Earth seem to have infiltrated the NIST on
> our own Earth, with the aim of making sure that both versions are allowed
by
> the standard...
I have to assume that the two communities understand all the issues that we
have been discussing. I also have to assume that they are trying to
interpret just one FIPS document.
This leads me to believe that before they agree to 'connect' their AES boxes
to each other, they will agree a way of ensuring that these connections are
made between bits with the same names.
Brian Gladman
Douglas A. Gwyn
> Doug Gwyn wrote:
> > It's not a matter of "users" understanding [finite fields] or not, it's
> > the simple fact that abstractions don't exist as such in the computer,
> > thus they have to be concretely *represented* using bit values.
> > Collections of bits are just collections of bits, but we still need to
> > know where each bit should be placed.
> There is a subtle but important difference between this argument and the
> one I made above. Abstractions have to be represented concretely, yes,
> but we do not need to, and SHOULD NOT, have an algorithm or protocol
> standard require specific internal representations. [*]
I was of course not talking about internals of an implementation,
but rather what is needed for standardizing *data interchange*.
The *main* reason for establishing a standard for encryption is
to facilitate the use of a "good enough" algorithm *among
communicants*, which implies data interchange.
If I am to hand a bunch of bits to you for you to decipher (using
an agreed-upon shared key), I need to know how to package and
transmit the bits that fell out of my encryptor, and you need to
know the convese for the bits you receive and your decryptor.
Therefore the interface between the crypto algorithm and external
storage is something that such a standard *should* specify.
Otherwise, we're still missing some of the necessary specification.