RFC Errata
RFC 4009, "The SEED Encryption Algorithm", February 2005
Note: This RFC has been obsoleted by RFC 4269
Source of RFC: IETF - NON WORKING GROUP
Errata ID: 752
Status: Held for Document Update
Type: Technical
Publication Format(s) : TEXT
Reported By: Alfred Hoenes
Date Reported: 2005-02-28
Held for Document Update by: Russ Housley
(C)
First, a formal issue with the ASN.1 given in the RFC text:
In the ASN.1 definitions in section 2.5., it would perhaps be more
natural and consistent with the requirements from the text (and the
ASN.1 comment already present there!) to give an explicit SIZE
restriction in the definition of the syntax of the initialization
vector for SEED in CBC mode (which indeed *MUST* be 16 octets long).
To this end, I recommend to replace the 7th text line of section 2.5.,
"seedCDCParameter ::= OCTET STRING -- 128-bit Initialization Vector"
by:
| "seedCDCParameter ::= OCTET STRING (SIZE(16))
| -- 128-bit Initialization Vector"
(D)
The text in section 2.2. talks about two basic 8x8 S-boxes, named
"S1" and "S2". Contrary to that, Appendix A.1. (on page 7) gives
tables for "S-Box S0" and "S-Box S1".
It would be easier to change the headlines in Appendix A.1.,
but, given the numbering style of all other formula elements,
it is certainly be more appropriate and consistent to modify the
equations in section 2.2., replacing "S1" by "S0", and "S2" by "S1".
I'll give a full replacement text for section 2.2. below, covering
this issue as well.
[ Now, returning to the open issue ... ]
(B)
In short, sorry, I do NOT agree with your definition of the SS-boxes.
It does not conform with the primary definition of the function G.
Below, I'll give you a detailed step-by-step explanation, using a
concrete example, for the reasoning already presented in my first
mail.
Note: For brevity and due to the email line length restriction,
in the subsequent reasoning, I will omit the braces '{ ... }'
around the ANDed terms, making use of the usual precedence rule
for multiplication over addition and the facts that
- the '^' operation is the normal addition in the 8 / 32 dimensional
vector spaces over GF(2) we are working on,
- '&' representing the 8 / 32 fold tensor product of the scalar
multiplication over GF(2) .
I repeat and extend the numeration of the formulas from my first
email, already applying item (D).
X = X0 || X1 || X2 || X3 (2)
... the 32 bit wide input to the function G;
Z = Z0 || Z1 || Z2 || Z3 (1)
... the 32 bit wide output of the function G applied to X;
with the 8-bit wide components computed by the application
of the two S-Boxes S0 and S1 via the equations:
Z0 = S0(X0) & m0 ^ S1(X1) & m1 ^ S0(X2) & m2 ^ S1(X3) & m3 (1.0)
Z1 = S0(X0) & m1 ^ S1(X1) & m2 ^ S0(X2) & m3 ^ S1(X3) & m0 (1.1)
Z2 = S0(X0) & m2 ^ S1(X1) & m3 ^ S0(X2) & m0 ^ S1(X3) & m1 (1.2)
Z3 = S0(X0) & m3 ^ S1(X1) & m0 ^ S0(X2) & m1 ^ S1(X3) & m2 (1.3)
with m0 = 0xFC , m1 = 0xF3 , m2 = 0xCF , and m3 = 0x3F (1.4)
The alternate description of the Function G is to be
Z = SS0(X0) ^ SS1(X1) ^ SS2(X2) ^ SS3(X3) (3)
where, below, I'll try "my" version of the SS-Box definition ...
SS0(x) = S0(x) & m0 || S0(x) & m1 || S0(x) & m2 || S0(x) & m3 (4.0)
SS1(x) = S1(x) & m1 || S1(x) & m2 || S1(x) & m3 || S1(x) & m0 (4.1)
SS2(x) = S0(x) & m2 || S0(x) & m3 || S0(x) & m0 || S0(x) & m1 (4.2)
SS3(x) = S1(x) & m3 || S1(x) & m0 || S1(x) & m1 || S1(x) & m2 (4.3)
... and the version from the text (with the formal changes already
discussed properly applied) ...
SS0(x) = S0(x) & m3 || S0(x) & m2 || S0(x) & m1 || S0(x) & m0 (5.0)
SS1(x) = S1(x) & m0 || S1(x) & m3 || S1(x) & m2 || S1(x) & m1 (5.1)
SS2(x) = S0(x) & m1 || S0(x) & m0 || S0(x) & m3 || S0(x) & m2 (5.2)
SS3(x) = S1(x) & m2 || S1(x) & m1 || S1(x) & m0 || S1(x) & m3 (5.3)
With these notations, let's challenge the example octet sequence
X0 = 0x09 , X1 = 0x11 , X2 = 0xE1 , X3 = 0xF9 (6a)
i.e., by (2) : X = (0x) 09 11 E1 F9 (6b)
Applying the tables from Appendix A.1., we obtain (*) :
S0(X0) = 0x43 ,
S1(X1) = 0x62 ,
S0(X2) = 0xB9 ,
S1(X3) = 0x4C .
To first compute Z with the original definition of G, substituting
(*) and (1.4) into (1.0) .. (1.3), we obtain, step by step:
Z0 = S0(X0) & m0 ^ S1(X1) & m1 ^ S0(X2) & m2 ^ S1(X3) & m3 (1.0)
= 0x43 & 0xFC ^ 0x62 & 0xF3 ^ 0xB9 & 0xCF ^ 0x4C & 0x3F
= 0x40 ^ 0x62 ^ 0x89 ^ 0x0C
==>
Z0 = 0xA7 (7.0)
Z1 = S0(X0) & m1 ^ S1(X1) & m2 ^ S0(X2) & m3 ^ S1(X3) & m0 (1.1)
= 0x43 & 0xF3 ^ 0x62 & 0xCF ^ 0xB9 & 0x3F ^ 0x4C & 0xFC
= 0x43 ^ 0x42 ^ 0x39 ^ 0x4C
==>
Z1 = 0x74 (7.1)
Z2 = S0(X0) & m2 ^ S1(X1) & m3 ^ S0(X2) & m0 ^ S1(X3) & m1 (1.2)
= 0x43 & 0xCF ^ 0x62 & 0x3F ^ 0xB9 & 0xFC ^ 0x4C & 0xF3
= 0x43 ^ 0x22 ^ 0xB8 ^ 0x40
==>
Z2 = 0x99 (7.2)
Z3 = S0(X0) & m3 ^ S1(X1) & m0 ^ S0(X2) & m1 ^ S1(X3) & m2 (1.3)
= 0x43 & 0x3F ^ 0x62 & 0xFC ^ 0xB9 & 0xF3 ^ 0x4C & 0xCF
= 0x03 ^ 0x60 ^ 0xB1 ^ 0x4C
==>
Z3 = 0x9E (7.3)
Putting (7.0) .. (7.3) together using (1), we get the byte sequence
Z = Z0 || Z1 || Z2 || Z3 (1)
==>
Z = (0x) A7 74 99 9E (7)
Now let's see what happens when we apply "my" definition of the
SS-Boxes, substituting (6a), (*), and (1.4) into (4.0) .. (4.3) :
SS0(X0) = S0(X0) & m0 || S0(X0) & m1 || S0(X0) & m2 || S0(X0) & m3
= 0x43 & 0xFC || 0x43 & 0xF3 || 0x43 & 0xCF || 0x43 & 0x3F
= 0x40 || 0x43 || 0x43 || 0x03
==>
SS0(X0) = (0x) 40 43 43 03 (8.0)
SS1(X1) = S1(X1) & m1 || S1(X1) & m2 || S1(X1) & m3 || S1(X1) & m0
= 0x62 & 0xF3 || 0x62 & 0xCF || 0x62 & 0x3F || 0x62 & 0xFC
= 0x62 || 0x42 || 0x22 || 0x60
==>
SS1(X1) = (0x) 62 42 22 60 (8.1)
SS2(X2) = S0(X2) & m2 || S0(X2) & m3 || S0(X2) & m0 || S0(X2) & m1
= 0xB9 & 0xCF || 0xB9 & 0x3F || 0xB9 & 0xFC || 0xB9 & 0xF3
= 0x89 || 0x39 || 0xB8 || 0xB1
==>
SS2(X2) = (0x) 89 39 B8 B1 (8.2)
SS3(X3) = S1(X3) & m3 || S1(X3) & m0 || S1(X3) & m1 || S1(X3) & m2
= 0x4C & 0x3F || 0x4C & 0xFC || 0x4C & 0xF3 || 0x4C & 0xCF
= 0x0C || 0x4C || 0x40 || 0x4C
==>
SS3(X3) = (0x) 0C 4C 40 4C (8.3)
Note: Please observe that the terms in (8.0) .. (8.3) are indeed
the same terms as in (7.0) .. (7.3), but in 4x4 matrix transposed
order -- as stated abstractly in my first email.
Summing up (8.0) .. (8.3) according to (3), we get what should be
the alternate definition of G(X) :
Z = SS0(X0) ^ SS1(X1) ^ SS2(X2) ^ SS3(X3) (3)
= (0x) 40 43 43 03 ^ -- from (8.0)
(0x) 62 42 22 60 ^ -- from (8.1)
(0x) 89 39 B8 B1 ^ -- from (8.2)
(0x) 0C 4C 40 4C -- from (8.3)
==> -----------
Z = (0x) A7 74 99 9E (8)
Obviously, (8) indeed is identical to (7).
Finally, let's look for what we get with your definition of the
SS-Boxes, substituting (6a), (*), and (1.4) into (5.0) .. (5.3) :
SS0(X0) = S0(X0) & m3 || S0(X0) & m2 || S0(X0) & m1 || S0(X0) & m0
= 0x43 & 0x3F || 0x43 & 0xCF || 0x43 & 0xF3 || 0x43 & 0xFC
= 0x03 || 0x43 || 0x43 || 0x40
==>
SS0(X0) = (0x) 03 43 43 40 (9.0)
SS1(X1) = S1(X1) & m0 || S1(X1) & m3 || S1(X1) & m2 || S1(X1) & m1
= 0x62 & 0xFC || 0x62 & 0x3F || 0x62 & 0xCF || 0x62 & 0xF3
= 0x60 || 0x22 || 0x42 || 0x62
==>
SS1(X1) = (0x) 60 22 42 62 (9.1)
SS2(X2) = S0(X2) & m1 || S0(X2) & m0 || S0(X2) & m3 || S0(X2) & m2
= 0xB9 & 0xF3 || 0xB9 & 0xFC || 0xB9 & 0x3F || 0xB9 & 0xCF
= 0xB1 || 0xB8 || 0x39 || 0x89
==>
SS2(X2) = (0x) B1 B8 39 89 (9.2)
SS3(X3) = S1(X3) & m2 || S1(X3) & m1 || S1(X3) & m0 || S1(X3) & m3
= 0x4C & 0xCF || 0x4C & 0xF3 || 0x4C & 0xFC || 0x4C & 0x3F
= 0x4C || 0x40 || 0x4C || 0x0C
==>
SS3(X3) = (0x) 4C 40 4C 0C (8.3)
Summing up (9.0) .. (9.3) according to (3), we get
Z = SS0(X0) ^ SS1(X1) ^ SS2(X2) ^ SS3(X3) (3)
= (0x) 03 43 43 40 ^ -- from (9.0)
(0x) 60 22 42 62 ^ -- from (9.1)
(0x) B1 B8 39 89 ^ -- from (9.2)
(0x) 4C 40 4C 0C -- from (9.3)
==> -----------
Z = (0x) 9E 99 74 A7 (9)
This is NOT the same as (7).
In fact, it is the byte-reversed sequence from (7) .
-- Bingo!
Taking a closer look at (5.0) .. (5.3), I now see that indeed the
terms in these equations are in the reverse concatenation sequence
compared to (4.0) .. (4.3) !
After a detailed inspection of the tables given in Appendix A.2.
of RFC 4009, it now becomes clear that -- disregarding the IETF
conventions to represent all binary data in network byte order,
and without any further notice of this fact -- these tables do NOT
represent octect sequences (as expected from the presentation of
above formula using octet concatenation, not arithmetic left-shift
or multiply-by-256 operations), BUT the hexadecimal representation
of the proper 4-octet sequences improperly cast into 32 bit numbers
on a 'little endian' processor, i.e., without using the ntohl()
intrinsic!
I suspect that your definition of the SS-boxes (5.0) .. (5.3) has
been inadvertently retrofitted to match the values given in the
tables in Appendix A.2., again re-formulating the printed byte
order (which is NOT the storage byte order [= octet concatenation
order] in a little endian processor) using the octet concatenation
notation / formalism.
Because definition of the function G according to section 2.2. does
not make use of 32-bit integer arithmetic operations, I recommend
to clarify the situation by
o giving formula (4.0) .. (4.3) for the SS-Boxes, consistent
with the other formulas, and
o stating explicitely in Appendix A.2. that these tables give
byte reversed presentations of the octet sequences to be
used as the output of the SS-boxes.
To catch up, here's my proposed replacement text for the whole
section 2.2. of RFC 4009, covering the issues (A), (B), and (D)
mentioned so far:
---------------- cut here -------------------------------
2.2. The Function G
The function G has two layers: a layer of two 8x8 S-boxes, S0 and
S1, and a layer of block permutation of sixteen 8-bit sub-blocks.
The output octet sequence Z (= Z0 || Z1 || Z2 || Z3) of the
function G with the four-octet input X (= X0 || X1 || X2 || X3)
is as follows:
Z0 = {S0(X0) & m0} ^ {S1(X1) & m1} ^ {S0(X2) & m2} ^ {S1(X3) & m3}
Z1 = {S0(X0) & m1} ^ {S1(X1) & m2} ^ {S0(X2) & m3} ^ {S1(X3) & m0}
Z2 = {S0(X0) & m2} ^ {S1(X1) & m3} ^ {S0(X2) & m0} ^ {S1(X3) & m1}
Z3 = {S0(X0) & m3} ^ {S1(X1) & m0} ^ {S0(X2) & m1} ^ {S1(X3) & m2}
where m0 = 0xFC , m1 = 0xF3 , m2 = 0xCF , and m3 = 0x3F .
To increase the efficiency of the calculation of the function G, four
extended S-boxes with 4-octet output ('SS-boxes', see Appendix A.2.)
are defined as follows:
SS0(x) = {S0(x) & m0} || {S0(x) & m1} || {S0(x) & m2} || {S0(x) & m3}
SS1(x) = {S1(x) & m1} || {S1(x) & m2} || {S1(x) & m3} || {S1(x) & m0}
SS2(x) = {S0(x) & m2} || {S0(x) & m3} || {S0(x) & m0} || {S0(x) & m1}
SS3(x) = {S1(x) & m3} || {S1(x) & m0} || {S1(x) & m1} || {S1(x) & m2}
Hereby, the function G can be defined as follows:
Z = G(X) = SS0(X0) ^ SS1(X1) ^ SS2(X2) ^ SS3(X3) .
This alternate definition of the function G is faster than the
original definition but it takes 16 times the memory to store
the four SS-boxes compared to the two original S-boxes.
---------------- cut here -------------------------------
Immediately below the headline of Appendix A.2., on page 8,
I propose to insert the following text (or similar):
"The following tables specify the byte-reversed SS-box values,
i.e., the first octet to be returned from the function G
(named Z0 in section 2.2.), is obtained by XORing together
the rightmost bytes from the appropriate entries looked up
in the following four tables, etc."
(E)
The above discussion, and the observed deviation from the IETF
standard ('network') byte ordering convention, immediately raises
additional byte ordering concerns for
- the definition of the round function F in section 2.1., and
- the Key Schedule definition given in section 2.3.
The function G -- as defined in section 2.2. -- operates on a four-
octet sequence and returns a four-octet sequence, according to the
formulae labelled (1) and (2) above.
The definition of the round function F and the key schedule make use of
several multi-byte INTEGER arithmetic operations, in particular 32-bit
(mod 2^32) addition and subtraction, on input and output values of the
function G, and the key schedule uses circular shift operations on
concatenated (64 bit) intermediate key blocks.
With regard to the observations made above, I now suspect that some
of the implicit 'cast' operations (between octet sequences and multi-
byte integers) involved in the round functions and the key schedule
might also be formulated in a little-endian centric way, omitting the
necessary application of the htonl() and ntohl() intrinsics when
producing the test cases in Appendix B. (I did not have the time
to verify that.)
For the sake of interoperability, it SHOULD be clarified whether the
formulae given for R0' and R1' in section 2.1., and for Ki0 and Ki1
in section 2.3., as well as the constant's values tabulated in the
latter section, are specified according to IEFT standard byte ordering
rules, or with implicit little-endian byte order in mind.
It should say:
[see above]
Notes:
from pending