Subject: Re: RFC 4009 (again)

From: Alfred Hönes <[email-masked]>
Date: Mon, 7 Mar 2005 01:30:57 +0100 (MEZ)

Hello again,
and thanks for your quick response.

Meanwhile, I've tried to figure out in detail what's wrong with
the formulas for SSi by applying my version and your version to
a few examples (calculated by hand).

In the course of this effort, again going through the text, I have
detected additional issues with the RFC text.

[ I continue the enumeration from my first mail. ]

(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.

Best regards,
  Alfred Hönes.

-- 

+------------------------+--------------------------------------------+
| TR-Sys Alfred Hoenes   |  Alfred Hoenes   Dipl.-Math., Dipl.-Phys.  |
| Gerlinger Strasse 12   |  Phone: (+49)7156/9635-0, Fax: -18         |
| D-71254  Ditzingen     |  E-Mail:  [email-masked]                     |
+------------------------+--------------------------------------------+

On Fri, 4 Mar 2005 17:07:24 +0900, "Sungjae Lee" <[email-masked]> wrote:
>
> Hello,
>
> We, authors, agree with you.
>
> But SS-box are defined as follows:
>
>   SS0(X0) = {S1(X0) & m3} || {S1(X0) & m2} || {S1(X0) & m1} || {S1(X0) & m0}
>   SS1(X1) = {S2(X1) & m0} || {S2(X1) & m3} || {S2(X1) & m2} || {S2(X1) & m1}
>   SS2(X2) = {S1(X2) & m1} || {S1(X2) & m0} || {S1(X2) & m3} || {S1(X2) & m2}
>   SS3(X3) = {S2(X3) & m2} || {S2(X3) & m1} || {S2(X3) & m0} || {S2(X3) & m3}
>
> If you agree with my arguments, we will immediately submit an errata note
> for these issues to the RFC Editor for publication on the RFC Errata web
> page.
>
> Thank you for your concernings and contributions.
>
> Best Regards,
>
> -----Original Message-----
> From: Alfred Hönes [mailto:[email-masked]]
> Sent: Monday, February 28, 2005 6:09 PM
> To: [email-masked]; [email-masked]; [email-masked]; [email-masked]
> Cc: [email-masked]
> Subject: RFC 4009
>
>
> Hello,
>
> I just picked up and read the new RFC 4009 authored by you, to find
> significant concerns with section 2.2. (on pages 3 and 4 of the RFC):
>
>
> (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}
>   "
>
>
> Please check and comment.
>
>
> If you agree with my arguments, we should immediately submit an errata note
> for these issues to the RFC Editor for publication on the RFC Errata web
> page.
>
> 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) [?].
>
>
> Best Regards,
>   Alfred Hönes.
>
> -- 
>
> +------------------------+--------------------------------------------+
> | TR-Sys Alfred Hoenes   |  Alfred Hoenes   Dipl.-Math., Dipl.-Phys.  |
> | Gerlinger Strasse 12   |  Phone: (+49)7156/9635-0, Fax: -18         |
> | D-71254  Ditzingen     |  E-Mail:  [email-masked]                     |
> +------------------------+--------------------------------------------+