Subject: [dns-privacy] Issues with encoding keys in nameserver DNS names

From: Mukund Sivaraman <[email-masked]>
Date: Tue, 11 Dec 2018 11:08:06 +0530

There was some discussion in last night's meeting about encoding keys in
the DNS name of a nameserver, similar to DNSCurve. There are at least
some issues with it:

1. The RDATA of an NS record has to be a hostname, so it would limit the
amount of data that can be encoded within the NSDNAME. As an example,
base32 encoding is not possible.

2. It would have to work for nameservers that are within a domain with a
very long name already.

3. Let's assume it takes about 10 years for resolver->auth privacy
transport to trickle into widespread operational availability. It is
expected that quantum computers capable of obsoleting traditional crypto
will be available in as few as 15-20 years from now. It is unclear if
the limited length of keys that can be encoded into a subset of a DNS
name would be sufficient for post-quantum crypto algorithms.

4. NS records returned as part of delegations are unsigned, so for a
resolver to trust key information in the RDATA of such NS records in a
delegation, it would require the delegation to be returned using secure
transport to the parent-side nameserver of the zone cut. During last
night's conversation, there was some talk about fallback to plain
transports - it will not be useful unless the entire delegation from
root is followed with secure transports.

		Mukund

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 13 Dec 2018 13:50:39 -0500

> base32 encoding is not possible.

why is base32 encoding not possible for a hostname?

just for fun, i've stood up a new server.  It's not a DoT server, but
its name follows the guidance at:
https://knot-resolver.readthedocs.io/en/latest/modules.html#experimental-dns-over-tls-auto-discovery

https://longname.cmrg.net/
https://dot-fvyrmqvxe2yeialcpsu7xlbs6xefgd5rsa6mjwycewdrpeq2jcaq.nameservers.cmrg.net/

i had no trouble getting a certificate issued for it, and no problem
pointing NS records to the same name either (it's not running an
authoritative DNS server there, so it isn't fully connected, but that
has nothing to do with the name.

So the length of the name, and its ability to contain a base32-encoded
SHA256 digest is not an issue.

> 2. It would have to work for nameservers that are within a domain with a

what are the length limits that you're concerned about?  if we make a
system that works for all nameservers that are within zones that are up
to (for example) 100 octets, that would be a huge win.

Remember that we're also talking about the nameserver's name itself, not
the zones it can serve.  so even longer zones can still work, as long as
their nameservers aren't in-bailiwick.

> name would be sufficient for post-quantum crypto algorithms.

15 years ago, quantum computers were also 15-20 years away :)

I share your concerns about key length and post-quantum resistance, and
i wouldn't want to design a system that can *only* work with short keys.

However, at least one of the weird-naming-proposals on the table (the
knot-resolver experimental work above) is just stuffing a fixed-length
sha256 digest there -- that digest can cover PQ key material too.  If
the concern is an attack on sha256 itself, then we should think about
other ways to plan.

> root is followed with secure transports.

I agree with you that there is a security gap here, as with most steps
of indirection.

But i'd temper the "will not be useful" a little bit -- maybe "will not
defend against active attackers on first connection" is more accurate?

At any rate, the NS record could itself be DNSSEC-signed, and a
suitably-cautious client could ask the server for its own NS record and
associated RRSIG (QNAME-minimized, of course) before asking for anything
else.

Does this address your concerns about the feasibility of encoding
(hashes of) keys in nameserver DNS names?

        --dkg

---

From: Mukund Sivaraman <[email-masked]>
Date: Fri, 14 Dec 2018 02:22:12 +0530

Hi Daniel

First, thank you for replying. I wondered if I'd said something
completely wrong. :)

> why is base32 encoding not possible for a hostname?

The first and last octets of each label in a hostname must be an
alphabet or digit (first specified in RFC 952 and relaxed in RFC
1123). The other octets of the labels can be alphabet, digit or
hyphen(-).

As an example, for a 32-octet value that's sent through base32:

[muks@naina ~]$ echo -n "abcdefghijklmnopqrstuvwxyz789012" | base32
MFRGGZDFMZTWQ2LKNNWG23TPOBYXE43UOV3HO6DZPI3TQOJQGEZA====

The trailing '='s are part of the base32 encoding.

[muks@naina ~]$ echo -n "MFRGGZDFMZTWQ2LKNNWG23TPOBYXE43UOV3HO6DZPI3TQOJQGEZA====" | base32 -d
abcdefghijklmnopqrstuvwxyz789012[muks@naina ~]$ echo -n "MFRGGZDFMZTWQ2LKNNWG23TPOBYXE43UOV3HO6DZPI3TQOJQGEZA" | base32 -d
abcdefghijklmnopqrstuvwxyz7890base32: invalid input

This will not validate as a hostname label.

> to (for example) 100 octets, that would be a huge win.

Exhaust all the size of a DNS name except for a few characters and
imagine a nameserver belongs under that zone. A scheme has to work and
well for all extremes of DNS, not only a subset.

> the concern is an attack on sha256 itself, then we should think about

Nod, that may work too (how does one get the key then?) If it can be
demonstrated to work for near-future algorithms (next 2-3 decades), then
it's fine.

It is over 13 years since RFC 4035 and DNSSEC is still not in widespread
use. Features take time to be adopted and so if the proposed protocol
will need revision to make it support another algorithm, then it'll take
as many years from that time to be available, so we should future proof
it a bit.

> associated RRSIG (QNAME-minimized, of course) before asking for anything

Maybe.. I am just pointing out the issues. Perhaps there's some benefit
in signing them and the address glue anyway, to stop resolvers from
going off on wild chases due to some kinds of poisoning.

		Mukund

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 13 Dec 2018 21:11:52 +0000

> This will not validate as a hostname label.

That's only true if you use Base32 naively. If you know that you are always encoding a 256-bit value, you can drop the padding characters.

> well for all extremes of DNS, not only a subset.

That is not true for names that are targets of NS records. That is, if you want one or more of the nameservers for X to be able to use the cryptographic naming scheme, that name does not need to be under X: it can be under a more reasonable-length name. Again: these are optional extensions, not mandatory for name service.

> Nod, that may work too (how does one get the key then?)

There are many ways to get a key and then compare the hash of the key with the hash you get securely from the DNS.

> If it can be

SHA-256 is not near-future: it has been deployed for well over a decade.

> as many years from that time to be available, so we should future proof

256-bit hashes do not need to be "future proof": they are well-established. 256-bit keys do not need to be "future proof" either.

> going off on wild chases due to some kinds of poisoning.

NS records are signed; is is only the glue records that are not. The names being discussed here are in the NS records themselves.

--Paul Hoffman

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 13 Dec 2018 16:21:39 -0500

Hi Mukund--

thanks for your prompt followup!

> This will not validate as a hostname label.

ah! good call, thanks.  so a "trailing-=-stripped b32 encoding" would
work OK, right?

I did the generation in python with:

    base64.b32encode(hashlib.sha256(rawdata).digest()).decode('us-ascii').strip('=').lower()

it's not hard to re-add the = padding before re-decoding, based on the
length of the string, which will be a fixed length.

> well for all extremes of DNS, not only a subset.

i think i disagree.  for one thing, we've talked about the ability to do
opportunistic connections even in the absence of a signal.  so for
nameservers located within extremely huge zones, they might just have to
rely on opportunistic connections.  But in practice, even for a
nameserver that *serves* a huge zone, its name doesn't need to be in the
zone.

Let's look at this from another angle: what sorts of limits are we
talking about here?

 https://tools.ietf.org/html/rfc1035#section-2.3.4

establishes the limits, in particular:

    labels          63 octets or less
    names           255 octets or less

so we're saying that the terminal label will consume 57 octets (52 for
the b32, 4 for "dot-", and 1 for the dot).  this means that the zones
that can contain such a label are limited to 198 octets.

The longest name in the public suffix list (https://publicsuffix.org) is
41 octets (without the trailing dot):
s3.dualstack.ap-northeast-1.amazonaws.com

so even any long-named zone within that longest public suffix still
leaves 157 octets for the intervening sub-zones -- space remains for
more than two full-length 63-octet labels.

So i'm not worried -- there will be other problems with long domain
names long before we hit this one.

> Nod, that may work too (how does one get the key then?)

you get the key by connecting to the server and receiving it as part of
the server handshake.

> If it can be demonstrated to work for near-future algorithms (next 2-3
> decades), then it's fine.

i don't think anyone knows yet what the acceptable algorithms will be in
25 years.  We can guess of course, but as the saying goes: prediction is
hard, especially about the future.

> as many years from that time to be available, so we should future proof

sure, but i don't want to future-proof it out of existence. :) sometimes
too much complexity added too early on a what-if basis can kill a
protocol as easily as an unforseen change that does eventually happen.

> going off on wild chases due to some kinds of poisoning.

I appreciate your enumerating these concerns.  I hope my analysis is
helpful in giving some sort of reassurance that they're not a problem
for this sort of scheme.

        --dkg

---

From: Mukund Sivaraman <[email-masked]>
Date: Fri, 14 Dec 2018 03:09:07 +0530

Hi Paul

> SHA-256 is not near-future: it has been deployed for well over a decade.

Did you really mean to say this, to tell me that SHA-256 is deployed? It
seems belittling rather than address what's being discussed.

The "near-future" remark (and the whole topic) was for post-quantum
crypto algorithms such as the ones in the NIST competition. Some of
these seem to have rather large key sizes, so the RDATA of an NS record
will not be sufficiently long to hold key material. Perhaps it can hold
a digest, and then there has to be some other way to fetch a key.

> 256-bit hashes do not need to be "future proof": they are
> well-established. 256-bit keys do not need to be "future proof"
> either.

The discussion is not about specific schemes like hashes or keys or
256-bits.

> NS records are signed; is is only the glue records that are not. The
> names being discussed here are in the NS records themselves.

NS records in a delegation are not signed. If you want authoritative
signed NS records, you have to find them at the apex of the child
zone. But how would you contact the child zone's nameservers and ask it
for the signed NS at the zone's apex if you don't know how to make a
secure path to it?

		Mukund

---

From: Mukund Sivaraman <[email-masked]>
Date: Fri, 14 Dec 2018 03:30:29 +0530

> length of the string, which will be a fixed length.

Nod that'd work. :)

> names long before we hit this one.

I don't think this way. :) I think it will not support every RFC 1035
DNS name, but only a subset of it. It should work for every valid name,
because they are valid names and some application may want it. Why
settle for hacks when it can be designed elegantly?

> you get the key by connecting to the server and receiving it as part of

Nod. (can't help thinking that's another roundtrip, but perhaps that
can't be avoided.)

> hard, especially about the future.

That's not what I meant to say.. I'll explain. The NIST competition is
happening now and there'll be a "winner" soon, and there are many
choices of algorithms being proposed now. The system should be designed
to accomodate such algorithms, so that it will not be obsolete in the
next 2 decades *based on what we expect/know now*. It should be able to
accomodate perhaps this NIST competition "winner" that we currently
expect will be secure 20 years from now.. not some algorithm chosen 2-3
decades from now.

> protocol as easily as an unforseen change that does eventually happen.

Nod, I agree.

Also I'm just pointing out various items that need to be considered,
that's all. If it works fine with all that, then it works fine. +1. :)

> _______________________________________________
> dns-privacy mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dns-privacy

		Mukund

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 13 Dec 2018 18:14:04 -0500

> settle for hacks when it can be designed elegantly?

It depends on what elegance you're looking for.  There are ugly
real-world systems out there that can't support all kinds of new keys.

Furthermore, if you want a key digest to be bound to a specific name,
then either you incur an extra round trip (find out the name; then find
out the associated key digest) or you expect whoever ships the glue to
know how to ship additional glue cleverly.  not so elegant in terms of
actual delivery.

Stuffing a digest of a key in the name is useful in binding the key to
the server directly, without having to juggle multiple different RRsets.

So i agree -- it looks like a hack, and it does have some size limits.
but i don't think those limits are plausible for anything real-world to
hit, and compared to the other inelegancies, it seems pretty promising
to me.

> Nod. (can't help thinking that's another roundtrip, but perhaps that

if we're talking about DNS-over-TLS, then the server's key is going to
come down the pipe in the TLS handshake anyway, so it's no significant
extra burden to expect it there.

      --dkg

---

From: manu tman <[email-masked]>
Date: Thu, 13 Dec 2018 16:48:10 -0800

> > [muks@naina ~]$ echo -n
> "MFRGGZDFMZTWQ2LKNNWG23TPOBYXE43UOV3HO6DZPI3TQOJQGEZA====" | base32 -d
> > abcdefghijklmnopqrstuvwxyz789012[muks@naina ~]$ echo -n
> "MFRGGZDFMZTWQ2LKNNWG23TPOBYXE43UOV3HO6DZPI3TQOJQGEZA" | base32 -d
Yes, the padding MUST be removed from the name in order to form a
legitimate label.
Likewise, padding must be re-added when extracting the signature back.

> names long before we hit this one.

Agreed, it does form a long name but it fit the bill of the max size for
the label and still leave some room for a decently likewise already super
long name.

It may not be a nice target name, but this is not really for humans to
remember or even ever look at realistically.

Manu

---

From: "A. Schulze" <[email-masked]>
Date: Fri, 14 Dec 2018 19:12:41 +0100

Hello,

Am 11.12.18 um 06:38 schrieb Mukund Sivaraman:
> 1...4

5. Encoding a key as DNS name of a nameserver makes key rotation harder.
   Not impossible, but really much harder.

Andreas

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 14 Dec 2018 18:32:18 +0000

>   Not impossible, but really much harder.

More generally, encoding a key anywhere else makes key rotation harder. It doesn't matter if it's a NS record, an HTTP header, or a text list of current keys. All of these can be automated, and that automation will mostly work, and will cause massive problems in the rare times it doesn't. Having a second place to assure the value of a key is valuable, but that inherently adds some fragility. 'Twas always thus.

--Paul Hoffman

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 14 Dec 2018 17:26:24 -0500

>    Not impossible, but really much harder.

i agree that it makes it harder, but i'm not convinced that it is *much*
harder.

Pretty much all TLS stacks today will let you associate different
keys/certificates with different server names, so as long as resolvers
send SNI to their resolvers (should we MUST that?) then it works like
this:

As an authoritative server operator, for rotation, you'd:

 * create a new key
 * create a certificate for it (or just use TLS raw public key)
 * tell the TLS frontend to use both certificates/names
 * add a new NS record
 * remove the old NS record
 * once its TTL has expired, remove the old certificate/name

if you're serving many zones from a single authoritative server, it
would require you to update the NS records for all zones, though -- that
is maybe more of a challenge (especially if they all use different
registrars and you're trying to update glue) than the above process,
which is fairly well-defined.

But maybe it's worth reviewing what we're hoping to gain from the
keys-in-names approach too:

 a) indication that private queries are expected to work to this
    particular resolver

 b) cryptographic identity material

If we care about both (a) and (b), then keys-in-names makes sense
(though it has the friction for rotation that you describe).

But what if we cared only about (a) ?  could we signal with a
special/magic terminal label just that private queries are expected to
work, without embedding a key there?

then we could rely on "the usual mechanisms" (the CA system, DANE) to
address the authenticity problem, rather than an embedded key.

For example, maybe the terminal label of your NS record could be
"yes-it-does-dot" :)

    @ 1D IN NS yes-it-does-dot.a.ns.example.net.
    @ 1D IN NS yes-it-does-dot.b.ns.example.net.

what do folks think about the tradeoffs there?

      --dkg

---

From: Tony Finch <[email-masked]>
Date: Mon, 17 Dec 2018 12:36:44 +0000

> i agree that it makes it harder, but i'm not convinced that it is *much*

In my setup, if server keys are in the server name then rotating them
requires liaison work over email to humans at 8 other organizations.
(And my setup is not big.)

If server keys are alongside then it's easy.

> work, without embedding a key there?

That could be a useful approach.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Lundy, Fastnet, Irish Sea: South 6 to gale 8, increasing severe gale 9 at
times, perhaps storm 10 later. Moderate at first in Irish Sea, otherwise rough
or very rough, occasionally high except in Irish Sea. Occasional rain. Good,
occasionally poor.