Subject: [EAI] The Worms of Punycode

From: "Charles Lindsey" <[email-masked]>
Date: Sun, 16 Jul 2006 14:54:24 +0100

Worm #1
-------

Punycode is defined in RFC 3492. I would describe it as a triumph of  
ingenuity over common sense. Moreover, RFC 3492 is incredibly badly  
written (essentially, it describes the protocol bottom-up, which means you  
cannot begin to understand the significance of any of its many concepts  
until you have already worked out what they all do without the slightest  
idea of what each is trying to achieve). But there it is.

Firstly, it is NOT an encoding algorithm. It is essentially a compression  
algorithm which just happens to produce an output composed entirely of  
ASCII (or, to be more precise, of <atext>s). The output consists, in  
essence, of
    a) The genuine ASCII characters extracted out of the input;
    b) a delimiter '-';
    c) a sequence of integers.
The integers are apparently represented in Base 36 (so each 'digit' can be  
represented by one of 26 letters - case insensitive -  plus 10 decimal  
digits); except that on further examination you discover that the base  
changes with each digit that is output (though it always lies between 1  
and 36).

Worm #2
-------

The algorithm is normatively defined using a pseudocode, but there is also  
a model implementation in C set out in Appendix C, which purports to  
achieve the effects defined by the pseudocode. But the model omits some  
features (checks) defined by the pseudocode which are provably  
unnecessary, but OTOH it also introduces some additional "features" not  
present in the pseudocode. It will be necessary for us to understand  
exactly what those "features" do and do not do in order to describe how  
the algorithm is to be used for <local-part>s in UTF8smtp.

Worm #3
-------

The algorithm was designed to work in an environment where the input had  
already been preprocessed, e.g. by Nameprep. Nameprep, which disallows  
various inadmissable Unicode Codepoints, and does case folding (to  
lowercase AIUI) for those alphabets (including ASCII) in which "case" is a  
meaningful concept. So not only would Nameprep change "Example" to  
"example", but it would also change "Éxample" to "éxample". It may be the  
case that if you can assume the input has been pre-processed (by whatever  
*-prep is in use) some further checks can be omitted from the model  
implementation.

But as regards case folding, it needs to be recogised that RFC 3492 is  
written in the expectation that cases will have been folded, and hence it  
contains remarks (non-normative) which are misleading unless you  
appreciate where it is coming from.

In fact, the normative algorithm defined by the pseudocode is completely  
blind to case (and hence is in fact perfectly suited to our purpose). Not  
so the model implementation (and one expects that many implementors are  
going to use that model implementation without necessarily understanding  
it). The model implementation is indeed aware of "case" - it's those  
afforementioned "features", and therefore it is necessary to understand  
how to turn them "off".

Worm #4
-------

In fact, the model implementation is only aware of case in ASCII  
characters. Thus it knows that "E" and "e" are two versions of the same  
letter, but it is totally unaware that "É" and "é" are related in any way.  
So the first bit of good news is that those two will be correctly  
translated into Punycode whatever happens (and the only reason this does  
not confuse the present IDNA (which is case insensitive) is that the  
preprocessing by Nameprep will have already got rid of any "É").

Now, if you translate "éxample" into Punycode, there are many legitimate  
ways of doing it using the model implementation:

original	Punycode	case_flags
--------	--------	----------
éxample	xample-9ua	0000000
		xAmPlE-9ua	0010101
		xAmPlE-9uA	1010101
		XAMPLE-9uA	1111111

Here, the "case_flags" are a bit-vector provided as a parameter to  
punycode-encode. It causes the bit of the output corresponding to each  
character to be rendered in uppper or lower case (even within the integer  
sequence that encodes the non-ASCII characters).

Now if you are using "éxample" as part of a domain name, then it does not  
matter which of those outputs you get (DNS doesn't care), but obviously  
choosing 'all-zeroes' or 'all-ones' are the only sensible options. BUT, it  
you are so minded (and you can rely that the case of letters in domain  
names will not get changed en route, which is not 100% certain), then you  
can run a covert channel alongside your email carrying (in this example) 7  
bits of information (and punycode-decode in the model implementation will  
kindly hand your bit-vector back to you at the far end). You *might* even  
use these bit-vectors to encde the original (pre-Nameprep) case of your  
domain name, so that you could restore it to its former glory (this seems  
to be what the writers of RFC 3492 had in mind, as outlined in Appendix A  
- they even took the trouble to frig the basic parameters of the algorithm  
so that it could be guaranteed that the final "digit" of each integer in  
the sequence would be a letter rather than a digit).

Now that all looks like Good Clean Fun, but it is, of course, totally  
irrelevant for our purpose which is to convey <local-part>s with their  
cases intact. And for that, you MUST NOT provide any bit-vectors. Just set  
the relevant parameter of punycode_[en,de]code to NULL (which is NOT the  
same as 'all-zeroes') and none of that nonsense will happen (as indeed it  
would never have happened in the first place if you had just read the  
normative pseudocode which says, quite plainly, "copy [the basic code  
points] to the output in order, followed by a delimiter if ...". No  
mention at all of case folding during the "copy".

Conclusion: the underlying Punycode algorithm will copy case-sensitively  
perfectly satisfactorily (even using their model implementation)  
*in*spite* of the attempts by the authors of RFC 3492 to confuse you into  
believing otherwise -:( .

Worm #5
-------

Punycode may fail. Obviously, if given invalid input, or an insufficient  
buffer to contain its output, that is fair enough. But it can also run  
into an overflow (and the model implementation carefully checks for this).  
In IDNA, the longest component of a domain name can have only 63  
characters; moreover the range of Unicode Codepoints is (0..10FFFF). With  
those restrictions, you can show that overflow will never happen if you do  
your arithmetic with 26-bit unsigned arithmetic (well, that's what they  
say, but from their formula I make it 27-bits).

What is the longest allowed <local-part>? Well, assuming you do not use a  
<quoted-string> with folded whitespace inside it, it is determined by the  
overall 998 byte limit on a header line (less a bit for the header name, a  
domain name, and other bits and pieces). So it turns out that it can be  
done in 31 unsigned bits. Or to put it another way, if you can do 32-bit  
unsigned arithmetic (and most machines these days can), you could have a  
<local-part> 3600 characters long. I think that will suffice :-) .

Worm #6
-------

We have to indicate that Punycode has been applied. In IDNA, this is done  
by prefixing it with 'xn--'. We are agreed that we need a different prefix  
for <local-part>s.

We are proposing an experimental protocol, which we hope people will start  
to implement pretty soon (indeed, it has already started). Therefore, I  
think we should choose our prefix *now*, and not rely on the RFC Editor to  
consult an oracle such as the New York Stock Exchange.

It needs to be similar to the IDNA prefix, so that it will be immediately  
recognizable for what it is. I therefore propose 'yn--' - it is evidently  
similar, and 'y' is a pretty obvious progression from 'x', so if you can  
remember the one, you should have no difficulty in remembering the other.

The IDNA prefix was chosen because it could not possibly be a legal domain  
name. We do not have that assurance, so if 'yn--xample-9ua' is seen as a  
<local part>, how you you know that it was not a genuine ASCII  
<local-part>?

You don't, but then how did you know that someone who provided the Subject

     Subject: =?iso-8859-1?Q?=C9xample?=

didn't actually mean exactly that? You don't, but its a pretty safe bet  
that he didn't, and I think it is a pretty safe bet that 'yn--xample-9ua'  
was not intended to be taken as literally that. But then, the delivery  
agent can always try to look it up in its  
address-list/-algorith/-whatever, and if it finds it is genuine, then good  
luck to it!

And on top of that, if there is a header such as

     Header-Content: downgraded

present, then that would give a further clue. I think this is a risk we  
just have to take.

Worm #7
-------

The syntax of <local-part> is

     dot-atom / quoted-string

(assuming we can ignore the obs-local-part). In UTF8smtp, both the  
<dot-atom> and the <quoted-string> can have UTF8 in them (but you still  
need to use a <quoted-string> if there are any (ASCII) <specials> in  
there. What comes out after Punycoding must still be a syntactically  
correct <local-part>, but this time according to strict RFC 2822. So if  
you start with

     "éxample avec une SP"@éxample.com

and just apply Punycode blindly, you will get

     yn--"xample avec une SP"[email-masked]

But now you do not have a syntactically correct RFC 2822 <local-part>.

So the ACE rule must be

     If the (UTF8smtp) <local-part> is a <quoted-string>, remove the  
initial and final DQOTEs and convert what remains using Punycode (without  
any bit-vector and with prefix 'yn--'), then enclose the result of that  
within DQUOTEs; if it was originally a <dot-atom>, then simply convert it.

So that example would come out  as

     "yn--xample avec une SP-9vb"xample avec une SP-9vb

Worm #8

If you convert something that is already pure ASCII, it is *not* a nullop.  
For example, the Punycode of 'ABCD' is 'ABCD-' (or 'yn--ABCD-' after  
prefixing). So the rule also needs to instruct you not to appy the ACE to  
something that is already pure ASCII.

For people who want to experiment further, I have attached two C program  
texts. 'rfc3492.c' is just the model implementation taken direct from  
Appendix C, but without the "wrapper" at the end for testing it.  
'tounicode.c' is a program which #includes the first one.

Set yout locale to use whatever charset you fancy (UTF8 or whatever). Call  
'tounicode' and give it strings (one on each line) in your charset. It  
will convert them to UTF-32 and print out the Codepoints, followed by the  
representation in Punycode. After that, it decodes the Punycode, and  
prints it out again as Codepoints and in your original charset. It ought  
to print out finally exactly what you input originally.

-- 
Charles H. Lindsey ---------At Home, doing my own thing------------------------
Tel: +44 161 436 6131                       
   Web: http://www.cs.man.ac.uk/~chl
Email: [email-masked]      Snail: 5 Clerewood Ave, CHEADLE, SK8 3JU, U.K.
PGP: 2C15F1A9      Fingerprint: 73 6D C2 51 93 A0 01 E7 65 E8 64 7E 14 A4 AB A5

_______________________________________________
IMA mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ima

---

From: "Adam M. Costello" <[email-masked]>
Date: Sun, 16 Jul 2006 22:43:25 +0000

I haven't been following this mailing list (too busy with other things),
but the word Punycode in the subject line caught my eye.

Charles Lindsey <[email-masked]> wrote:

> RFC 3492 is incredibly badly written (essentially, it describes the
> protocol bottom-up, which means you cannot begin to understand the
> significance of any of its many concepts until you have already worked
> out what they all do without the slightest idea of what each is trying
> to achieve).

Sorry, I guess I'm better at precision than clarity.  I would be glad
to discuss the algorithm, the pseudocode, the C code, and ways to
improve the document.  There was a draft-costello-rfc3492bis-02, which
is still available (minus the RFC boilerplate) here:

http://www.nicemice.net/idn/

Follow the link to the "slightly clarified version".  The clarifications
really are slight, but suggestions for more are welcome.

> Firstly, it is NOT an encoding algorithm.  It is essentially a
> compression algorithm which just happens to produce an output composed
> entirely of ASCII (or, to be more precise, of <atext>s).

The second statement is correct, but I don't see how it implies the
first.  Would you claim that Huffman coding is not an encoding?

> The algorithm is normatively defined using a pseudocode, but there is
> also a model implementation in C set out in Appendix C, which purports
> to achieve the effects defined by the pseudocode. But the model omits
> some features (checks) defined by the pseudocode which are provably
> unnecessary,

The pseudocode puts {braces} around checks that might not be needed,
and the C code puts /* comment delimiters */ around the corresponding
checks.

By the way, the C code in the slightly clarified draft has a cleaner
interface (inspired by GNU libidn) and slightly clearer comments.

> but OTOH it also introduces some additional "features" not present in
> the pseudocode.

Yes, the case_flags.  If you pass in NULL for case_flags, the C code
will behave exactly like the pseudocode.  The case_flags are an
implementation of the mixed-case annotation described in appendix A.

> The algorithm was designed to work in an environment where the input
> had already been preprocessed, e.g. by Nameprep.

It was designed to be more general than that. "Although the only
restriction Punycode imposes on the input integers is that they be
nonnegative,these parameters are especially designed to work well with
Unicode [UNICODE] code points".  The input doesn't have to be Nameprep'd
or even valid Unicode, and you'll still get it back unscathed.

> But as regards case folding, it needs to be recognised that RFC 3492
> is written in the expectation that cases will have been folded, and
> hence it contains remarks (non-normative) which are misleading unless
> you appreciate where it is coming from.

Please tell me which remarks are misleading; I'd like to clarify them.

> In fact, the normative algorithm defined by the pseudocode is
> completely blind to case (and hence is in fact perfectly suited to
> our purpose). Not so the model implementation (and one expects that
> many implementors are going to use that model implementation without
> necessarily understanding it). The model implementation is indeed
> aware of "case" - it's those afforementioned "features", and therefore
> it is necessary to understand how to turn them "off".

The only added feature is mixed-case annotation (from appendix A), which
can be turned off by passing NULL for case_flags.  I've added a todo
item to clarify that in the comments in the C code.

> characters. Thus it knows that "E" and "e" are two versions of the
> same letter, but it is totally unaware that "É" and "é" are related
> in any way.  So the first bit of good news is that those two will
> be correctly translated into Punycode whatever happens (and the
> only reason this does not confuse the present IDNA (which is case
> insensitive) is that the preprocessing by Nameprep will have already
> got rid of any "É").

Yes, in IDNA, case insensitivity is handled entirely by Nameprep, not by
Punycode.

> Conclusion: the underlying Punycode algorithm will copy               
> case-sensitively perfectly satisfactorily (even using their model     
> implementation)                                                       

Right.  I designed Punycode to work for case-sensitive text,
case-insensitive text, and case-insensitive case-preserving text.  IDNA
cares only about the second category (although it could be extended to
use the third).  The mixed-case annotation is applicable only to the
third category.

> *in*spite* of the attempts by the authors of RFC 3492 to confuse you
> into believing otherwise -:( .

Sorry for the confusion.  How could this be made clearer?

> In IDNA, the longest component of a domain name can have only
> 63 characters; moreover the range of Unicode Codepoints is
> (0..10FFFF). With those restrictions, you can show that overflow
> will never happen if you do your arithmetic with 26-bit unsigned
> arithmetic (well, that's what they say, but from their formula I make
> it 27-bits).

You probably didn't take into account that 4 of the 63 bytes are
consumed by the ACE prefix, so an ACE label cannot represent more than
59 code points.

(0x10FFFF - 128) * (59 + 1) = 66838980
                    1 << 26 = 67108864

> We have to indicate that Punycode has been applied. In IDNA, this
> is done by prefixing it with 'xn--'. We are agreed that we need a
> different prefix for <local-part>s.

Yes, if you don't apply Nameprep, then you definitely need a different
prefix.  Even if you did apply Nameprep, you might still want to use
a different prefix (think about what happens when domain names are
embedded in local parts, or when email addresses are embedded in domain
labels).

> The IDNA prefix was chosen because it could not possibly be a legal
> domain name.

All we knew was that it did not exist in the second level under the
gTLDs.  We had no assurance for the ccTLDs, nor for the gTLDs at any
levels below the second.

AMC