Subject: flaws in RFC 4226

From: Alfred Hönes <[email-masked]>
Date: Wed, 18 Jan 2006 16:45:25 +0100 (MEZ)

Hello,
I'd like to submit a few comments on the recently published
RFC 4226.  (You are receiving this note because your email
address is given there as the primary contact address.)

There are a couple of textual flaws in the RFC text the correction
of which might be considered for posting an appropriate Errata Note
on the RFC Editor's web site.

The issues I've found are listed below in the order they appear in
the text.  Occasionally I have added change bars '|' in column 1 or
'^^^' style tags to point to the position of a textual flaw and/or
the proposed change within the citiations presented.
Where necessary, I also have re-formatted the text proposals to
match RFC formatting rules.

(1)  [ 2 typos ]

The text of Section 5.3, in the 2nd and 3rd paragraph on page 7,
says:

   The reason for masking the most significant bit of P is to avoid
   confusion about signed vs. unsigned modulo computations.  Different
   processors perform these operations differently, and masking out the
|  signed bit removes all ambiguity.
       ^^
   Implementations MUST extract a 6-digit code at a minimum and possibly
   7 and 8-digit code.  Depending on security requirements, Digit = 7 or
   more SHOULD be considered in order to extract a longer HOTP value.

It should say:

   The reason for masking the most significant bit of P is to avoid
   confusion about signed vs. unsigned modulo computations.  Different
   processors perform these operations differently, and masking out the
|  sign bit removes all ambiguity.

   Implementations MUST extract a 6-digit code at a minimum and possibly
|  7 and 8-digit codes.  Depending on security requirements, Digit = 7
   or more SHOULD be considered in order to extract a longer HOTP value.

(2)  [ inappropriate restriction specified + formatting flaw ]

On page 17, Appendix A.1 contains the text:

   Let IntDiv(a,b) denote the integer division algorithm that takes
|  input integers a, b where a >= b >= 1 and returns integers (q,r)
|
   the quotient and remainder, respectively, of the division of a by b.
   (Thus, a = bq + r and 0 <= r < b.)

The restriction  "a >= b"  is not necessary and in fact inappropriate;
the additional blank line seems to be an artifact of the editing
process.  Thus, the above text should better read:

   Let IntDiv(a,b) denote the integer division algorithm that takes
|  input integers a, b where  b >= 1  and returns integers (q,r), the
   quotient and remainder, respectively, of the division of a by b.
   (Thus, a = bq + r and 0 <= r < b.)

(3)  [ conflicting naming of variables ]

In Appendix A.3, unfortunately the necessary distinction between
the counter value kept with the user and the counter value kept
at the server is not preserved in the variable names introduced.
This leads to significant confusion.
I hereby propose a 'minimally invasive' text modification as
follows (Cf. Appendix E.3 for another notation) :

The text of the 2nd and 3rd paragraph of Appendix A.3, on page 18 :

   The scenario we are considering is that a user and server share a key
   K for ALG.  Both maintain a counter C, initially zero, and the user
   authenticates itself by sending ALG(K,C) to the server.  The latter
   accepts if this value is correct.

   In order to protect against accidental increment of the user counter,
   the server, upon receiving a value z, will accept as long as z equals
   ALG(K,i) for some i in the range C,...,C + s-1, where s is the
   resynchronization parameter and C is the server counter.  If it
   accepts with some value of i, it then increments its counter to i+1.
   If it does not accept, it does not change its counter value.

should be modified to say:

   The scenario we are considering is that a user and server share a key
|  K for ALG.  Both maintain a counter C and C', respectively, initially
   zero, and the user authenticates itself by sending ALG(K,C) to the
   server.  The latter accepts if this value is correct.

   In order to protect against accidental increment of the user counter,
   the server, upon receiving a value z, will accept as long as z equals
|  ALG(K,i) for some i in the range C',...,C' + s-1, where s is the
|  resynchronization parameter and C' is the server counter.  If it
   accepts with some value of i, it then increments its counter to i+1.
   If it does not accept, it does not change its counter value.

(4)  [ typo ]

Near the bottom of page 18, the 2nd-to-last paragraph of Appendix A.3
(on that page) says:

                                                    ...  It wins if the
   server accepts this accumulator.
                       ^^^^^^^^^^^
It should say instead:

                                                    ...  It wins if the
   server accepts this authenticator.

(5)  [ another typo, and continuation of (3) above ]

Still in Appendix A.3, the text on the upper half of page 19 contains
a wrong (undefined) variable name 'O' which should be 'A' instead,
and it should be adapted according to item (3) above.
The text says:

   Oracle AuthO()
   --------------
      A = ALG(K,C)
      C = C + 1
      Return O to B

   Oracle VerO(A)
   --------------
      i = C
      While (i <= C + s - 1 and Win == FALSE) do
         If A == ALG(K,i) then Win = TRUE; C = i + 1
         Else i = i + 1
      Return Win to B

It should say:

   Oracle AuthO()
   --------------
      A = ALG(K,C)
      C = C + 1
|     Return A to B

   Oracle VerO(A)
   --------------
|     i = C'
|     While (i <= C' + s - 1 and Win == FALSE) do
|        If A == ALG(K,i) then Win = TRUE; C' = i + 1
         Else i = i + 1
      Return Win to B

(6)  [ typos in mathematical text ]

Lemma 1 and its proof in Appendis A.4.1, on page 20, contains
several typos.

In Lemma 1, the line,

          P_{N,m}(z) = Pr [x mod m = z : x randomly pick in Z_{n}]
                                                              ^^^
should read:

          P_{N,m}(z) = Pr [x mod m = z : x randomly pick in Z_{N}]

This corrects the use of an undefined variable, n, by using the
variable N as expected from the LHS term.

In the Proof of Lemma 1, the case distinction for z contains an
improper relational operator at two places.
To adjust to the possible range of values (cf. item (2) above!),
the formula parts:

   P_{N,m}(z)  =  [ ... ]

                = mq/N * 1/m +
                   (N - mq)/N * 1 / (N - mq)     if 0 <= z < N - mq
|                  0                             if N - mq <= z <= m
                                                               ^^^^
                = q/N +
                   r/N * 1 / r                   if 0 <= z < N - mq
|                  0                             if r <= z <= m
                                                          ^^^^
should be modified to read:

   P_{N,m}(z)  =  [ ... ]

                = mq/N * 1/m +
                   (N - mq)/N * 1 / (N - mq)     if 0 <= z < N - mq
|                  0                             if N - mq <= z < m

                = q/N +
                   r/N * 1 / r                   if 0 <= z < N - mq
|                  0                             if r <= z < m

(7)  [ formatting flaw ]

Appendix A.4.3, on mid-page 22, contains improperly formatted text.
It says:

   Proposition 2 ------------- Suppose m = 10^Digit < 2^31, and let
   (q,r) = IntDiv(2^31,m).  Let B be any adversary attacking HOTP-IDEAL
   using v verification oracle queries and a <= 2^c - s authenticator
   oracle queries.  Then  [...]

It should say:

   Proposition 2
   -------------

   Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m).  Let B
   be any adversary attacking HOTP-IDEAL using v verification oracle
   queries and a <= 2^c - s authenticator oracle queries.  Then  [...]

(8)  [ typo ]

Within Appendix A.5, in the lower half of page 23, the text for
"Assumption 1" says:

   Let T denotes the time to perform one computation of H.  [...]
               ^
It should say:

   Let T denote the time to perform one computation of H.  [...]

(9)  [ formatting issue ]

In Appendix C, the source text in the upper half of page 28
contains an improperly formatted comment -- obviously intended
to illustrate the subsequent declaration, the comment must be
aligned with that declaration.
Thus, the lines:

       // These are used to calculate the check-sum digits.
|      //                                0  1  2  3  4  5  6  7  8  9
       private static final int[] doubleDigits =
                       { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };

should read:

       // These are used to calculate the check-sum digits.
|      //                0  1  2  3  4  5  6  7  8  9
       private static final int[] doubleDigits =
                       { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };

(10)  [ further formatting (indentation) issues ]

Still in Appendix C, the source code on page 30 (lower half) and
page 31 contains improperly indented lines.
The following three line groups should be indented by 6 more character
positions to make them conformant to RFC style 'nice' format:

- on page 30:

     String result = null;
     int digits = addChecksum ? (codeDigits + 1) : codeDigits;

- on page 30:

     if ( (0<=truncationOffset) &&
            (truncationOffset<(hash.length-4)) ) {
         offset = truncationOffset;
     }

- on page 31:

     if (addChecksum) {
         otp =  (otp * 10) + calcChecksum(otp, codeDigits);
     }
     result = Integer.toString(otp);
     while (result.length() < digits) {
         result = "0" + result;
     }
     return result;

(11)  [ variation of item (3) above ]

The enumeration in Appendix E.4, on page 34, contains inconsistent
variable namings (cf. issue (3) above!).
To make it self-consistent, the enumeration:

   1) C-client >= C-server
   2) C-client - C-server <= s
   3) Check that HOTP client is valid HOTP(K,C-Client)
   4) If true, the server sets C to C-client + 1 and client is
      authenticated                           ^^^
                              ^^^             ^^^
should read:

   1) C-client >= C-server
   2) C-client - C-server <= s
|  3) Check that HOTP client is valid HOTP(K,C-client)
|  4) If true, the server sets C-server to C-client + 1 and client is
      authenticated

Authors, please verify, and decide whith of these issues should be
dealt with by an Errata Note.

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]                     |
+------------------------+--------------------------------------------+