RFC Errata


Errata Search

 
Source of RFC  
Summary Table Full Records

Found 3 records.

Status: Held for Document Update (3)

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: 751

Status: Held for Document Update
Type: Technical

Reported By: Alfred Hoenes
Date Reported: 2005-02-28
Held for Document Update by: Russ Housley

 

(A)
>
> Unfortunately, within a few lines in the RFC text, the variable name 'X'
> gets used for two very distinct purposes and contexts:
>
>   o   X = X0 || X1 || X2 || X3                            (2)
>       ... the 32 bit wide input to the function G
>
>   o   X used as formal argument in the defining equations for
>       the 'SS-boxes' SS0 ... SS3
>       ... a single octet (8 bit wide entity),
>           [application of the formulas - see (3) below - will
>            substitute X0, ..., X3 in turn for the arguments]
>
> Perhaps, it would have been better to use another symbol, e.g. 'x', for the
> latter purpose.
>
>
> (B)
>
> As far as I can see, feeding the definition of the SS-boxes given in the
> last 4 text/formule lines on page 3 into the formula on top of page 4,
>
>      Z = SS0(X0) ^ SS1(X1) ^ SS2(X2) ^ SS3(X3)            (3)
>
> does ***NOT*** yield the same result as using the primary defining formulas
> given for Z0  ... Z3  in the first formula block of section 2.2., together
> with
>
>      Z = Z0 || Z1 || Z2 || Z3                             (1).
>
> I suspect a mis-ordering in the use of m0 ... m3 in the equations defining
> SS0 ... SS3 :
>
> With regard to the formulas (1), (2), and (3) (as numbered above), the
> 'matrix' pattern of the 4x4 terms in braces { ... } , obtained from the
> formula block defining SS0 ... SS3 by substitution of Xi for the argument of
> SSi (i=0,1,2,3) - as required in (3) -, should be the matrix transpose of
> the pattern of the same terms in braces appearing in the formula block
> defining Z0 ... Z3 , e. g. the first 'column' of {...} terms for SSi()
> should contain the {...} terms appearing in the formula for Z0.
> But this is not the case.
>
> Therefore, I suspect that the last 6 text/formula lines on page 3 of RFC
> 4009 should in fact read (including the enhancement from (A)
> above):
>
>   "
>   To increase the efficiency of the G function, four extended S-boxes
>   'SS-box' (See Appendix A.2) are defined as follows:
>
>    SS0(x)= {S1(x) & m0} || {S1(x) & m1} || {S1(x) & m2} || {S1(x) & m3}
>    SS1(x)= {S2(x) & m1} || {S2(x) & m2} || {S2(x) & m3} || {S2(x) & m0}
>    SS2(x)= {S1(x) & m2} || {S1(x) & m3} || {S1(x) & m0} || {S1(x) & m1}
>    SS3(x)= {S2(x) & m3} || {S2(x) & m0} || {S2(x) & m1} || {S2(x) & m2}
>   "
>
>

> In this case, I also recommend to include a textual enhancement for the
> first sentence of section 2.3., replacing:
>
>     "The key schedule generates each round subkeys."
> by:
>     "The key schedule generates subkeys for each round."
>
> And finally, for completeness, it would have been useful as well to give
> additional Informational Reference(s) for the seedMAC (and the
> [seed]CBC) algorithm(s)/construct(s) mentioned in section 2.5. - e.g.  RFC
> 3610 (and RFC 2451 / NIST SP 800-38A) [?].

It should say:

[see above]

Notes:

from pending

Errata ID: 752

Status: Held for Document Update
Type: Technical

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

Errata ID: 197

Status: Held for Document Update
Type: Editorial

Reported By: Alfred Hoenes
Date Reported: 2005-03-06
Held for Document Update by: Russ Housley

Section 2.5 says:

 seedCDCParameter ::= OCTET STRING  -- 128-bit Initialization Vector

It should say:

seedCDCParameter ::= OCTET STRING (SIZE(16))
                       -- 128-bit Initialization Vector

Report New Errata