Re: draft-costello-rfc3492bis

"Martin v. Löwis" <[email protected]> wrote:

> > http://www.ietf.org/internet-drafts/draft-costello-rfc3492bis-00.txt
>
> "NOT OPTIONAL" is not a keyword of RFC2119. "OPTIONAL" is, and it is a
> synonym of "MAY".  The usage of "NOT OPTIONAL" is redundant with the
> "MUST".

Maybe I got carried away with the emphasis.  I wouldn't mind removing
all instances of "NOT OPTIONAL", leaving just "MUST" and "REQUIRED".

> It's not immediately obvious why some operations (e.g. inside adapt)
> don't perform overflow checking, but (without further review) I assume
> there is some guarantee that it can't overflow.

You raise an interesting question.

In the main encoding and decoding functions, for any values of maxint
and the constants (base, tmin, tmax, etc), you can make overflow happen
by providing a long enough input.

In adapt(), on the other hand, the possibility of overflow can be ruled
out regardless of the input, if the constants aren't too extreme.

adapt() cannot overflow if

    (base - tmin + 1) * ((base - tmin) * tmax) div 2) <= maxint

and

    base * (log(maxint) - log(0.5 * tmax)) / log(base - tmin)
    + base - tmin <= maxint

The former condition can be rewritten to avoid overflow in the condition
itself:

    base - tmin <= ( (maxint div (base - tmin + 1)) * 2 + 1 ) div tmax

This is the first time I've carried the analysis to this level of
detail, so watch out for errors.  (I would welcome independent analyses
for comparison.)

For Punycode, this boils down to maxint >= 16380, and I've never
heard of a platform with maxint smaller than 32767.  For other
parameterizations of Bootstring, it could be more of a concern.  In any
case, those checks can be performed once per platform; there is no need
for a runtime check.

Perhaps the draft should discuss this.

By the way, I just noticed that the conditions on tmin and tmax in
section 4 are insufficient.  It currently says:

    0 <= tmin <= tmax <= base-1

We need to strengthen that in order to avoid infinite loops.

    0 <= tmin <= base-2
    1 <= tmax <= base-1
    tmin <= tmax

I suppose that's a technical change in Bootstring, but it has no effect
on Punycode, whose parameters already obey the stronger constraints.

AMC