[bind10-dev] flaws in reversed name-based approach for getting the "previous name"

[JINMEI Tatuya / 神明達哉]

In our current sqlite3 schema and manipulation interfaces, we used
"reversed" names to identify the "previous name" in the DNSSEC order
of a given name.  For example, database rows (of the "example.com"
zone) would have the following pair of name and reversed name:

example.com. com.example.
a.example.com. com.example.a.
ca.example.com. com.example.ca.
...

To get the "previous name" of a given name, the sqlite3 implementation
selects the rows whose reversed name is "equal to or smaller" 
(in terms of case-insensitive string comparison) than the reversed
name of the query name, sorts the result by the reversed name in the
descending order, and picks up the first row of the sort result.

So, in the above example, if "b.example.com." is queried, the sort
result would be:

com.example.a.
com.example.

and a.example.com. (whose reverse is com.example.a.) is correctly
selected.

This is a clever way and should work in most cases in practice, but
I've realized it doesn't work in some less common cases.

First, (especially when the name contains a non ascii character and)
when a label character is represented in the \DDD form, it will
confuse the above algorithm.  For example, the following sequence of
names (correctly sorted in the DNSSEC order):

\001.example.com.
a.example.com.
\200.example.com.

would be incorrectly sorted as follows:

\001.example.com.
\200.example.com.
a.example.com.

because in the ascii code '\' < 'a'.

Second, some of non alpha numeric characters will also confuse the
algorithm.  Consider these two:

b.a.example.com. (reverse: com.example.a.b.)
a-b.example.com. (reverse: com.example.a-b.)

In the DNSSEC order, the first name is smaller than the second.  But
our algorithm would sort it in the reverse order because '-' < '.'.

What should we do with these cases?  I can think of two possibilities
(there may be more):

1. ignore the problem as a minor case (or say "use in memory data
   source if your zone contains this problem")
2. use some normalized form that ensures the sorting result as a
   string is identical to the DNSSEC order.  For example, if we
   represent all characters in the "\DDD" form, that would work (note
   that '.' < '\' coincidentally, so there won't be a problem like '.'
   vs '-')

Option 2 is better in terms of correctness, of course, but it has its
own drawbacks: It requires more code, and it would be more difficult
to edit the zone in the database directly (i.e., not from our API).  I
personally still incline to go for option 2 (or any other way that
ensure the correct result) because I suspect the case with '-' is not
so uncommon, and also because to claim to be "reference
implementation" I believe we should generally not allow incorrect
behavior simply because it's minor.

Opinions?

---
JINMEI, Tatuya