Subject: RFC 2152 - UTF-7 clarification

From: "A. Rothman" <[email-masked]>
Date: Wed, 7 Oct 2015 11:21:49 +0300

Hi,

I hope this is the right place to discuss RFC 2152 - I couldn't find a
conclusive answer as to where and how one should comment on a specific
Request For Comments (which is a bit unsettling :-) )

I'd like to raise an issue with the UTF-7 decoding process as described
in the RFC with respect to trailing padding bits:

"Next, the octet stream is encoded by applying the Base64 content
transfer encoding algorithm as defined in RFC 2045, modified to
omit the "=" pad character. Instead, when encoding, zero bits are
added to pad to a Base64 character boundary. When decoding, any
bits at the end of the Modified Base64 sequence that do not
constitute a complete 16-bit Unicode character are discarded. If
such discarded bits are non-zero the sequence is ill-formed."

The way I understand this is that after decoding the modified-base64
data and grouping the resulting octets into 16-bit Unicode characters,
any remaining zero bits at the end (up to 15 bits, theoretically) should
simply be ignored. I'm not sure why an encoder would want to add extra
zero bits at the end beyond the minimum necessary, but it is arguably
allowed to pad 'to *a* Base64 character boundary', not specifically *the
next* boundary. Perhaps an encoder would use some version of a standard
Base64 routine and then replace the padding '=' characters with 'A'
characters (which are then decoded to all zero bits). Such encoding
would obviously be less space-efficient since it adds unnecessary octets
to the encoding - but it seems like there are valid reasons to do so.

The issue is with the decoding though, and the reason it came up is that
I've checked various existing UTF-7 decoder implementations and
resources (e.g. iconv, uconv, icu, jutf7, jcharset, Wikipedia, etc.) and
they seem to disagree about this issue. Some generate an error after
a maximum number of trailing zero bits (the maximum changes between
implementations), and some agree with my interpretation above where any
leftover partial group of zero bits is discarded and it's always valid.

So, since there is such discrepancy in practice in how this is being
interpreted, I submit that the description is not clear enough to make
this unambiguous. Could someone please clarify what is officially
valid/invalid according to the RFC regarding trailing zero bits? Can we
add errata that clarifies it in either case?

Finally, if it helps, here are some concrete test cases to consider:

+A-
+AA-
+AAA-
+AAAA-
+AAAAA-
+AAAAAA-
+AAAAAAA-

Which of these are valid inputs? Which are invalid? How many 0x0000
16-bit characters should each one be decoded into?

Thanks!

Amichai

---

From: <[email-masked]>
Date: Thu, 8 Oct 2015 06:01:53 +0000

The best place to raise this erratum for formal consideration would be
https://www.rfc-editor.org/errata.php

Lloyd Wood
http://about.me/lloydwood
________________________________________
From: ietf <[email-masked]> on behalf of A. Rothman <[email-masked]>
Sent: Wednesday, 7 October 2015 7:21 PM
To: [email-masked]
Subject: RFC 2152 - UTF-7 clarification

Hi,

+A-
+AA-
+AAA-
+AAAA-
+AAAAA-
+AAAAAA-
+AAAAAAA-

Thanks!

Amichai

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 8 Oct 2015 06:53:01 +0000

> such discarded bits are non-zero the sequence is ill-formed."

It seems to me that the encoder's behaviour is specified clearly
enough.  Namely, the encoder outputs an unpadded base64 encoding
of the input octet-stream that is zero padded with 0, 2 or 4 bits
(an odd padding length can't happen) to ensure that the total number
of bits is a multiple of 6, allowing each 6 bits to be encoded as
base64 output character.

The decoder's job is then to reverse this process.  The base64
input produces a stream of 6-bit blocks, which in total yields 16q
+ 2r bits where 0 <= r < 8.  The "q" groups of 16 bits are the
decoded text.  The "2r" extra bits must be zero and are discarded.

An encoder should never generate 6 <= 2r <= 14 extra bits, since
0, 2 or 4 is enough, however it seems that an encoder can get away
with up to 10 "extra" padding bits so long as the total count is
less than 16.

> any remaining zero bits at the end (up to 15 bits, theoretically)

Well 14, due to an even bit count.

> should simply be ignored.

Correct, though in practice that count should always be 0, 2 or 4.
Encoders that produce 6, 8, 10, 12 or 14 padding bits are appending
extraneous "A" output octets to the base64 stream.

> I'm not sure why an encoder would want to add extra zero bits at the end
> beyond the minimum necessary, but it is arguably allowed to pad 'to *a*
> Base64 character boundary', not specifically *the next* boundary.

Correct, with 6, 8 or 10 extra bits, it would have been simpler
for the encoder to save one output "A" and emit 0, 2 or 4 padding
bits.  With 12 or 14, save outputting "AA" and emit 0 or 2 extra
bits.  What the extra "A" or "AA" might allow the encoder to do is
to "round-up" the base64 output to a multiple of 4 octets, which
simplifies decoding.  The only time the encoder can't do that is
when the input length in bits is 24q + 2|4|6|8 (1/3 of the time),
because this would require 16 or more padding bits.

I would not write an encoder that makes the base64 output an exact
multiple of 4 octets 2/3 of the time.  Too much trouble for incomplete
success, but it seems that the specification allows this.

> Perhaps an encoder would use some version of a standard
> characters (which are then decoded to all zero bits).

This does not work, because the total number of padding bits may
then equal or exceed 16.

> Such encoding

It would also be wrong, because it would not be able to represent
trailing zeros correctly.

> add errata that clarifies it in either case?

Admittedly, I am just applying logic.  Perhaps the specification
is not as logical as I expect.  If it is logical, then it should
be as noted above.

> Finally, if it helps, here are some concrete test cases to consider:

+A- 		: empty + 6 (unnecessary) padding bits

+AA-		: empty + 12 (unnecessary) padding bits
+AAA-		: \U+0000, and 2 (required) padding bits
+AAAA-		: \U+0000, and 8 (6 extra) padding bits
+AAAAA-		: \U+0000, and 14 (12 extra) padding bits
+AAAAAA-	: \U+0000\U+0000, and 4 (required) padding bits
+AAAAAAA-	: \U+0000\U+0000, and 10 (6 extra) padding bits

> 16-bit characters should each one be decoded into?

They are all valid, because any padding bits are zero in all of
them.  They decode to floor(6n/16) == floor(3n/8) 16-bit unicode
code points, where "n" is the length of the base64 input.

-- 
	Viktor.

---

From: Mark Andrews <[email-masked]>
Date: Thu, 08 Oct 2015 18:22:51 +1100

In message <[email-masked]
tlook.com>, [email-masked] writes:
> From: ietf <[email-masked]> on behalf of A. Rothman <amichai2@amicha=
> is.net>

It says omit, not replaced with 'A'.  In addition just replacing
'=' with 'A' can add a 0x0000 to the end of a unicode string as the
pad characters can cover 12 bits with 4 bits from the second character
of the 4 character base64 word.

e.g.
	AAAAAA== 0x0000, 0x0000 (discard 4 bits)
	AAAAAAAA 0x0000, 0x0000, 0x0000

Though I can see how you could think this was a valid strategy if
you only look at a single base64 word after encoding a single utf-16
character.

	AAA=	 0x0000	(discard 2 bits)
	AAAA	 0x0000	(discard 8 bits)

Now you could safely replace all the '=' pad characters with a
single 'A' but that would just be a perverse encoder and if you
were to use such a encoder I wouldn't blame the decoder for rejecting
the input.

> +A-			illegal	!modified base64
> +AA-			illegal	!a multiple of 16 bits in modified base64
> +AAA-			legal   0x0000 (last 2 bits zero)
> +AAAA-		illegal !a multiple of 16 bits in modified base64
> +AAAAA-		illegal	!modified base64
> +AAAAAA-		legal   0x0000, 0x0000 (last 4 bits zero)
> +AAAAAAA-		illegal !a multiple of 16 bits in modified base64
> 
-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: "A. Rothman" <[email-masked]>
Date: Thu, 8 Oct 2015 14:21:36 +0300

This reply by Mark and the previous one by Viktor both point out
correctly that the example of replacing '=' with 'A' is not a good one.
So let's ignore that part and assume an encoder decides to add padding
for some other unknown reason just because it can (this appears to be
allowed by the RFC with the current wording, as suggested earlier).

Everything else still stands. Specifically, the two replies beautifully
illustrate my point about ambiguousness - in their interpretation of the
actual test cases I submitted, one says that all inputs are valid, and
the other says some of them are invalid. That's exactly the problem I
saw when comparing libraries.

So before raising the erratum using the provided link, I thought this
would be the place to discuss what the desired outcome should be - i.e.
which of the two interpretation should be chosen as the correct one in
the errata.

As a starting point, my suggestion would be that an encoder SHOULD add
the minimal amount of padding necessary, which is likely what encoders
already do, while a decoder MUST accept and discard any amount of zero
padding (less than 16 bits of course), in line with being more lenient
on inputs, and simplifying/micro-optimizing the decoder by removing an
extra check+documentation and applying KISS. It would be nice to add one
of the test cases in the errata as well, to clarify the expected result.

Other suggestions are welcome - as long as there is a decision at the
end :-)

Amichai

---

From: John C Klensin <[email-masked]>
Date: Thu, 08 Oct 2015 09:29:12 -0400

--On Thursday, October 08, 2015 06:01 +0000 [email-masked]
wrote:

> The best place to raise this erratum for formal consideration
> would be https://www.rfc-editor.org/errata.php

Actually, Lloyd, probably not.  RFC 2152 may be informational,
but it is normatively referenced from a standards-track
document.  If an alteration or clarification to its definition
is required, the fix really ought to have community consensus
and the RFC errata process is not at all good for that.  Those
who are interested in ITF-7 and its applicability may want to
see the related discussion on the apps-discuss list.

    john

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 8 Oct 2015 16:06:00 +0000

> were to use such a encoder I wouldn't blame the decoder for rejecting

I don't read Mark's response as saying that non-minimal padding is
*invalid*.  He says the encoder is "perverse", and I agree that
the encoder would be better off not generating excess padding.  

He further says that he would not be surprised if some decoders
rejected non-minimally padded input, and frankly I would also not
be surprised, but that does not make the input invalid.  The
specification says that up to 14 (< 16) bits of zero padding is to
be discarded by decoders, it does not limit the discard bit count
to 4 (< 6).  

There are lots of lazy and fragile implementations of standards
out there, encoders need to try to avoid generating non-mainstream
outputs if they want most decoders to handle the result.

> saw when comparing libraries.

Perhaps Mark really does consider 8 to 14 bits of padding as
"invalid" (not just "perverse").  If so, then indeed the specification
is open to multiple interpretations.  As I see it, so far Mark and I
are on the same page.

> of the test cases in the errata as well, to clarify the expected result.

The only thing "missing" from the specification is advice (or a
requirement) to make the padding "minimal".  That is to pad only
to the *closest* base64 (i.e. multiple of 6 bit) boundary.

-- 
	Viktor.

---

From: "A. Rothman" <[email-masked]>
Date: Thu, 8 Oct 2015 21:40:25 +0300

Just in case someone missed it (I almost did): Mark added his own
detailed comments on the test cases, but they got buried within a long
quote from my original email so may have gone unnoticed. To recap, here
are the two interpretations:

+A-             empty + 6 (unnecessary) padding bits
+AA-            empty + 12 (unnecessary) padding bits
+AAA-           \U+0000, and 2 (required) padding bits
+AAAA-          \U+0000, and 8 (6 extra) padding bits
+AAAAA-         \U+0000, and 14 (12 extra) padding bits
+AAAAAA-        \U+0000\U+0000, and 4 (required) padding bits
+AAAAAAA-       \U+0000\U+0000, and 10 (6 extra) padding bits

Does anyone else want to vote or comment on the two interpretations above?

---

From: <[email-masked]>
Date: Fri, 9 Oct 2015 02:33:12 +0000

> RFC 2152 may be informational, but it is normatively referenced
> from a standards-track document.

(which one?)

well, that makes a mockery of the whole informational/standards-track distinction.

The RFC Editor errata process is really just for determining (formally) if there is an error.
After that, it can be pretty open; and community consensus is not formal.

Lloyd Wood
http://about.me/lloydwood
________________________________________
From: John C Klensin <[email-masked]>
Sent: Friday, 9 October 2015 12:29 AM
To: Wood L  Dr (Elec Electronic Eng); [email-masked]; [email-masked]
Subject: Re: RFC 2152 - UTF-7 clarification

    john

---

From: Robert Sparks <[email-masked]>
Date: Thu, 8 Oct 2015 22:10:10 -0500

>> from a standards-track document.
http://datatracker.ietf.org/doc/rfc2152/referencedby/

---

From: Viktor Dukhovni <[email-masked]>
Date: Fri, 9 Oct 2015 05:08:32 +0000

> Does anyone else want to vote or comment on the two interpretations above?

Thanks for pointing this out more clearly.  Yes, they disagree.
However, the manner in which they disagree is rather simple.

They agree in all the cases where the padding is *minimal*.

The first variant always tolerates non-minimal padding allowing
anything less than 16 bits per the specification.  The second
variant never tolerates non-minimal padding, because there's no
need to produce it.

It is clear that clients should produce minimal padding, and we
seem to disgree on  wether to apply Postel's principle to the
decoder or not.

This is not a major disagreement, such differences of interpretation
are endemic whether the standard is clear or not.  Many implementors
are lazy, and stop writing code when the expected cases work.

While this is no excuse for ambiguous specifications, in this case
I don't think a revision is warranted.  Encoders that generate
sensibly minimal padding will not run into any friction with
non-broken decoders.  Encoders that get creative might find that
some decoders object whether the standard allows their creativity
or not.

-- 
	Viktor.

---

From: John C Klensin <[email-masked]>
Date: Fri, 09 Oct 2015 01:18:40 -0400

--On Friday, October 09, 2015 02:33 +0000 [email-masked]
wrote:

>> RFC 2152 may be informational, but it is normatively
>> referenced from a standards-track document.
> 
> (which one?)

RFC 3501, the base IMAP4 Rev 1 document.

> well, that makes a mockery of the whole
> informational/standards-track distinction.

"Mockery" is a little strong, don't you think?   While I
personally believe we are almost always better off reclassifying
or reissuing/updating informational or lower-maturity-level
documents that are needed to support newer standards track ones,
we have, IIR, pretty much always had mechanisms for making
exceptions and allowing so-called "downward references".

> The RFC Editor errata process is really just for determining
> (formally) if there is an error. After that, it can be pretty
> open; and community consensus is not formal.

You may think so but that process assigns proposed errata to a
category.  The mechanism used to do that typically involves a
discussion with authors and/or a small number of expert and
then, for IETF Stream documents, a discussion within the iESG,
not the broader community.  In recent years, when an error has
not been completely obvious and/or trivial or changes the
technical subject matter of the spec, the tendency has been to
assign the category "hold for future revision", which is
completely useless as far as informing the user about what to
do.  

As has already been pointed out, it is clear that the text of
2152 is not as clear and precise as one might like.  The
question is what should be done about it in terms of what is
required and/or recommended.  The errata process, as now
constituted, is not good at answering questions like that.

   best,
    john

---

From: Harald Alvestrand <[email-masked]>
Date: Mon, 12 Oct 2015 17:23:25 +0200

> well, that makes a mockery of the whole informational/standards-track distinction.

If you believe that, a careful study of RFC 3967 and the page at
https://trac.tools.ietf.org/group/iesg/trac/wiki/DownrefRegistry might
leave you mighty unhappy.

The only unusual (well, slightly unusual) thing about this downref is
that we haven't gotten it into the list yet.

---

From: "A. Rothman" <[email-masked]>
Date: Wed, 14 Oct 2015 00:11:03 +0300

Ok, thanks for your analysis and for looking into this (Mark as well).

I shall change my decoder implementation to the lenient interpretation,
adjust my unit tests, and hope it is considered RFC-compliant by
everyone :-)

Amichai

---

From: Harald Alvestrand <[email-masked]>
Date: Wed, 14 Oct 2015 08:44:44 +0200

> adjust my unit tests, and hope it is considered RFC-compliant by

Note that this is a reprise of the UTF-8 "overlong encoding" debate,
where we ended up banning overlong encodings because of the security
issues it posed (see the UTF-8 RFC for more details on the security
issues found).

---

From: "A. Rothman" <[email-masked]>
Date: Wed, 14 Oct 2015 10:46:03 +0300

I'm not sure what the debate was - are you referring to having multiple
encoded representations of the same unicode character sequence? If so,
then the question of padding is moot since it's explicitly allowed to
have a whole lot of different representations in the UTF-7 encoding
(with or without an explicit trailing '-' to end a shift sequence, the
explicit optional set that may or may not be represented in a shift
sequence, any character of the direct set that may also be in a shift
sequence, whether to combine consecutive shift sequences into one or
not, etc.). There's an exponential number of valid encodings for a
character sequence.

Requiring the encoder to always use the minimal possible encoding is
quite a big change to the spec. Requiring a decoder to reject
non-minimal encodings would increase decoder complexity significantly.
Changing the behavior regarding padding bits is meaningless without
these two additional requirements.

That said, it would certainly be useful to add a warning in the security
considerations section about such issues, and recommend that all data be
decoded first before performing any validity checks, comparisons, etc.
(as detailed in RFC 3629 for UTF-8).

Is this what you meant?

---

From: Mark Andrews <[email-masked]>
Date: Wed, 14 Oct 2015 19:30:56 +1100

> non-minimal encodings would increase decoder complexity significantly.

Absolute garbage unless you think getting the length of a
sequence is hard.

You can decode the shifted seqence and if the byte count is not a
multiple of 2 or is zero then is non-minimal.

If you don't want to decode the entire shift sequence you can do
the analysis on the shifted characters.  If the length of the shifted
sequence * 3 / 4 is not even or zero it is non-minimal.

A		1 * 3 / 4 -> 0
AA		2 * 3 / 4 -> 1
AAA		3 * 3 / 4 -> 2	(minimal) (2 zero bits)
AAAA		4 * 3 / 4 -> 3
AAAAA		5 * 3 / 4 -> 3
AAAAAA		6 * 3 / 4 -> 4	(minimal) (4 zero bits)
AAAAAAA		7 * 3 / 4 -> 5
AAAAAAAA	8 * 3 / 4 -> 6  (minimal)

The (length * 3 / 4) % 6 / 2 defines what values are legal in the
last shifted character.

0 all base64 characters are legal
1 last 2 bits are zero  (base64[c - base64[0]] & 0x3) == 0
2 last 4 bits are zero  (base64[c - base64[0]] & 0xf) == 0

---

From: "A. Rothman" <[email-masked]>
Date: Wed, 14 Oct 2015 12:27:30 +0300

> 2 last 4 bits are zero  (base64[c - base64[0]] & 0xf) == 0

All well and good, but you seem to be talking about modified base64
shift sequences. I'm talking about full UTF-7 encoded strings, to which
the multiple-representations security consideration is relevant.

The way I understand rules 1-2, any character in the D-set or O-set
(e.g. ASCII alphanumerics) can be validly encoded either directly as an
ASCII byte, or as a modified base64 shift sequence between '+' and '-'
literals. IIRC there are no rules as to if/when adjacent shift sequences
must be combined into a single shift sequence - it's all valid.

So that's 2 ways to encode every single alphanumeric character, for 2^n
valid UTF-7 encodings of the same original Unicode character sequence.
And that's not counting the other variations (optional '-' in some
cases, combining adjacent shift sequences, etc.).

I don't see how the length of the decoded string nor of the encoded
representation can immediately tell you if it's minimal or not. While
there are some shortcuts, I'm guessing you'd have to decode the full
UTF-7 string, and then analyse the characters in a way that is not
unlike re-encoding it using a minimal encoder, before you can find out
if it was already minimal or not. I may be wrong.