Subject: dns hop by hop transaction security for queries

From: Paul Vixie <[email-masked]>
Date: Sun, 20 Jul 2008 17:15:45 +0000

i have learned quite a lot about what's possible and how things work from
the recent thread "transaction security in the last mile" and i now have
a proposal to float.  i'm sorry i won't be in dublin to discuss this in
the hallways, but hopefully discussions will occur and i will hear about
them through this mailing list.

problem statement: BCP38 can never be nonfalsifiably universally deployed,
so any given IP datagram's source address must always remain suspect.  the
basic DNS query transaction uses two-packet UDP (request and response), and
each side (initiator and responder) is vulnerable to spoofed-source attacks,
where the initiator can be poisoned by untrue DNS data sent by an attacker
and the responder can be made to amplify a DDoS against innocent parties.

background:

DNSSEC offers both end to end data authenticity through its DNSKEY, RRSIG,
and NSEC{3} records, and stub/RDNS data authenticity through its {RR}SIG(0)
protocol.  deployment of DNSSEC in the root and COM zones is stalled for
political and economic reasons (respectively), and there is no path forward
involving private right of action by interested subsets of the community.
(leaving aside DLV, which is such a way, but is shrouded in controversy.)

GSS-TSIG offers stub/RDNS transaction authenticity but requires that the
stub and RDNS both be inside a fully functioning Kerberos realm, which is
not practical outside the enterprise (for example, in ISPs or hotel rooms.)

TSIG offers stub/RDNS transaction authenticity but requires that a shared
secret be installed by some out of band method, which is impractical for
query relationships due to the number of stub/RDNS relationships.  TSIG is
very successful for zone transfer and update relationships, which are fewer.

TKEY offers a way to establish a TSIG shared secret where the only starting
configuration data is that the initiator must know the responder's IP
address (which is true in the case of stubs and their RDNS'.)

DHCP could be made to carry an additional configuration element, "TSIG key",
to be associated with a given responder.  this follows from the fact that if
DHCP is spoofable, then the entire DHCP response is suspect, including the
elements for "RDNS IP".  as long as responder-side TSIGs were kept longer
than the DHCP lease time, this would work.  however, it's known that many
DNS initiators do not use DHCP at all, so this solution would be incomplete.

IPSEC and VPN's in general can be used to protect stub/RDNS transactions at
a higher configuration cost which is unjustifiable for the average DNS client
and which generally requires greater than average technical expertise.

be it noted, ICMP is also subject to spoofed-source attacks, and any UDP
flow even of short two-packet duration can be interrupted and made to fail.
this is true but to a lesser extent for TCP flows.

parameters:

a solution here would be opportunistic and pairwise deployable, requiring
no flag days; it would require no new technical expertise for end users; it
would have only graceful failure modes; it would not be subject to downgrade
attacks; and ideally, it would require no new protocol development work.

proposal:

stubs, and caching forwarding servers, when acting as initiators, should
use TKEY over TCP/53 to try to set up a shared secret with their
responders.  if successful, this secret should be used for UDP/53 queries
to that responder.  if TKEY over TCP/53 is successful for some responders
but not others, then the successful ones will be used exclusively.  if at
least one TSIG signed query transaction succeeds to a responder, and then
later transactions fail with TSIG errors (BADSIG) then TKEY over TCP/53
should be repeated.  if no TSIG signed query ever succeeds, then after some
small number of retries, the TKEY should be discarded and no longer used.
in cases where there is TKEY over TCP/53 fails, or where a TKEY was
acquired but then discarded, then TSIG must not be used on transactions to
that responder.

discussion:

there would be no protocol changes and no API changes.  this uses only DNS
protocol elements which are already defined, requiring only implementation
and deployment.  there is no reason for an API change since applications
are not expected to behave differently based on the degree of certainty in
the stub/RDNS transaction.

this could be argued as applicable to RDNS/ADNS relationships as well,
perhaps even when the RDNS contains a DNSSEC validator, but whereas the
number of TKEY over TCP/53 transactions is manageable, the amount of state
that both RDNS and ADNS would have to store and access, may not be.

initiators who implement the logic described in this proposal may have an
additional configuration knob, "TKEY and TSIG must succeed", either on a
per-responder basis, or globally.  this would disable fallback to UDP/53
and would render that endsystem unusable if the last mile DNS is not secure.
note that initiators with that knob would experience "flag day" behaviour,
rather than the softer opportunistic behaviour experienced otherwise.

that's all.

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Alex Bligh <[email-masked]>
Date: Sun, 20 Jul 2008 20:12:41 +0100

--On 20 July 2008 17:15:45 +0000 Paul Vixie <[email-masked]> wrote:

> should be repeated.  if no TSIG signed query ever succeeds, then after
> some small number of retries, the TKEY should be discarded and no longer
> used. in cases where there is TKEY over TCP/53 fails, or where a TKEY was

Data point: several reasonably large deployments use UDP
only RDNS configured in an anycast manner. A typical configuration for
a dial ISP many years ago and a DSL ISP now might be several DNS servers
sharing the same pair of IP addresses at each POP. This means there are
only 2 IP addresses to present at a tech support level. As far as I know,
most implementations either don't do TCP at all or just hope it works
over short session periods. The above proposal would require (I think)
that they all somehow shared state (or at least that state was shared
at the POP, or that the same IP address was always mapped to the same
RDNS, at least by hashing). That doesn't make this undoable, but
complicates it if the idea is to avoid fallback in such scenarios.

Alex

---

From: Paul Vixie <[email-masked]>
Date: Sun, 20 Jul 2008 19:25:14 +0000

> From: Alex Bligh <[email-masked]>
> 
> Data point: several reasonably large deployments use UDP only RDNS
> configured in an anycast manner. A typical configuration for a dial ISP
> many years ago and a DSL ISP now might be several DNS servers sharing the
> same pair of IP addresses at each POP. This means there are only 2 IP
> addresses to present at a tech support level. As far as I know, most
> implementations either don't do TCP at all or just hope it works over
> short session periods. The above proposal would require (I think) that
> they all somehow shared state (or at least that state was shared at the
> POP, or that the same IP address was always mapped to the same RDNS, at
> least by hashing). That doesn't make this undoable, but complicates it if
> the idea is to avoid fallback in such scenarios.

if there's a routing change so that the RDNS you did TKEY with moves away
and you become close to a different anycast instance (same IP new host)
then TSIG will start failing and you'll go back and do a new TKEY.  this
strikes me as a better model than state-sharing in wide area anycast.  for
local area anycast ("load balancing") i agree that state sharing would be
required among all members of a local anycast cluster.  i'm sure that RDNS
vendors who implement TKEY would happily compete on their anycast usability.

---

From: Duane <[email-masked]>
Date: Mon, 21 Jul 2008 07:22:09 +1000

> address (which is true in the case of stubs and their RDNS'.)

I see at least a few major flaws with TKEY because most of the
information is sent plain text, so to speak, and could easily be
tampered with by anyone doing a man in the middle attack.

It was suggested I use this for my draft but the more I think about it
the more I come to the conclusion it's poorly thought out from a
security perspective as it will only defend against spoofed packets.

-- 

Best regards,
 Duane

---

From: Paul Vixie <[email-masked]>
Date: Sun, 20 Jul 2008 23:11:48 +0000

> From: Duane <[email-masked]>
> 

a persistent MiTM who can both send and receive packets from/to an IP is not
part of my current problem statement.  (in that case one might also ask why
we expect non-DNSSEC transactions between RDNS/ADNS to work, or why we think
that UDP port randomization or DNS-0x30 or even XQID would help.)

> security perspective as it will only defend against spoofed packets.

since spoofed packets are the problem statement i've got, i'll quibble with
"poor... security".  spoofed packets are far more commonly available as a
tool for attackers than persistent MiTM (send and receive from/to an IP.)

i am especially attracted to any proposal that can be developed and
implemented without new protocol or API development, and which can be
deployed pairwise without any action at a distance by unknown parties.

---

From: Duane <[email-masked]>
Date: Mon, 21 Jul 2008 09:35:59 +1000

> deployed pairwise without any action at a distance by unknown parties.

Ok if spoofing is the problem you wish to solve, the simple solution
would be to increase the number of random bits to the point that it is
statistically improbable to be successful with such an attack, because
really 2^17 as best case is really really small, and based on what
everyone is implying what the recent patching is supposed to fix I'm
guessing up until recently most resolvers must be coming up with a much
smaller pool of numbers than that.

A trivial solution that wouldn't break anything might be just to prefix
something to the front of all hostnames that both ends strip before
processing them, 63 octets will give you 504 bits.

This doesn't require DH or any kind encryption or what not, it does
require a good source of entropy and/or a good cryptography hashing
algorithm to change the prefix for every request, the requests/replies
could still be cached after stripping the randomness from the front etc.

-- 

Best regards,
 Duane

---

From: Duane <[email-masked]>
Date: Mon, 21 Jul 2008 09:54:14 +1000

> processing them, 63 octets will give you 504 bits.

This was assuming only hexadecimal was used, if you use the full range
of characters allowed for hostnames you get almost 2400 bits.

-- 

Best regards,
 Duane

---

From: Paul Hoffman <[email-masked]>
Date: Sun, 20 Jul 2008 17:47:30 -0700

At 9:35 AM +1000 7/21/08, Duane wrote:
>processing them

I'm confused. How would a responder know to strip them without a 
change of the protocol?

--Paul Hoffman, Director
--VPN Consortium

---

From: Duane <[email-masked]>
Date: Mon, 21 Jul 2008 11:00:37 +1000

> of characters allowed for hostnames you get almost 2400 bits.

Actually I'm having a bad math day all round.

64 bytes of hex is 2^256, so 63 bytes of hex would be 2^252, using a 38
 character set instead would give you 2^441.

-- 

Best regards,
 Duane

---

From: Duane <[email-masked]>
Date: Mon, 21 Jul 2008 11:08:22 +1000

Paul Hoffman wrote:
> I'm confused. How would a responder know to strip them without a change
> of the protocol?

I don't know what the best way to implement such a method would be,
which is why I didn't want to suggest anything, in any case if the goal
is simply to prevent spoofing, rather than protecting against man in the
middle attacks you need to increase the Query ID size significantly.

If I was going to take a stab at this maybe something along the lines of
what most binary file types use, some kind of a 2-3 byte header, so if
the first 3 characters of such a prefix were _XID that still leaves 59
other characters to expand the number of bits, if you get a nonsense
reply back you know that the host doesn't support such queries, but the
reply should still have the complete "hostname" so that should prevent a
downgrade attack.

-- 

Best regards,
 Duane

---

From: Paul Vixie <[email-masked]>
Date: Mon, 21 Jul 2008 02:18:40 +0000

> ...

forget for a moment all your bad math (note, i can't count quatloos either.)
if we wanted to use the question section to hold more nonce bits, we'd set
QDCOUNT=2 and the second question would be for <longrandomthing>.ECHO and
the RFC on this topic would just say, if QDCOUNT is 2 and the TLD of the
second question is ECHO, then this must be copied into the response along
with the rest of the question section (bit for bit, to accomodate DNS-0x20),
and will not affect the processing of the response in any other way.

fallback would mean the server did not answer or sends a FORMERR or ignores
the second question.  since an of those can be spoofed by a downgrade attack,
this approach would require a more-than-two-packet negotiation sequence.

your approach of adding another label to the front of the QNAME of QDCOUNT=1
is also subject to downgrade attacks, and would require more-than-two-packet
negotiation as well.

if we're going to negotiate, then that means either DTLS or TKEY-over-TCP.
and if we're going to do TKEY-over-TCP then we should just use TSIG for the
queries.  whereas if we're going to use DTLS to negotiate then we should use
DTLS to protect the queries.  so, i can't find a case in which we would use
either an extra label in the question, or an extra question, to encode extra
bits.

---

From: "Donald Eastlake" <[email-masked]>
Date: Sun, 20 Jul 2008 22:28:23 -0400

If you are going to have to teach DNS implementations to strip these funny
name prefixes, why not teach them to use cookies or something like them:
http://www.ietf.org/internet-drafts/draft-eastlake-dnsext-cookies-03.txt.
Donald

-- 
=============================
Donald E. Eastlake 3rd +1-508-634-2066 (home)
155 Beaver Street
Milford, MA 01757 USA
[email-masked]

---

From: Duane <[email-masked]>
Date: Mon, 21 Jul 2008 12:35:02 +1000

Donald Eastlake wrote:
> If you are going to have to teach DNS implementations to strip these
> funny name prefixes, why not teach them to use cookies or something like
> them: http://www.ietf.org/internet-drafts/draft-eastlake-dnsext-cookies-03.txt.

Session IDs in cookies is exactly the thing I was thinking of actually,
how many languages that use Session ID on websites of only 2^17
combinations? (answer: none)

Although if you have already solved this I'll stop making guesses.

-- 

Best regards,
 Duane

---

From: Paul Hoffman <[email-masked]>
Date: Sun, 20 Jul 2008 19:42:48 -0700

>reply should still have the complete "hostname" so that should prevent a

Let me try again. Paul wants a method that is an operational change, 
not a protocol change. Your suggestions seem like protocol changes to 
me. Is that correct, or am I missing something?

--Paul Hoffman, Director
--VPN Consortium

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 20 Jul 2008 20:37:28 -0700

At Mon, 21 Jul 2008 12:35:02 +1000,
> Although if you have already solved this I'll stop making guesses.

I'm trying to come up to speed here, so apologies if what I'm about
to say is confused or if I'm using the wrong terminology.

As I understand the situation, it's pretty well agreed that there's no
approach that provides the requisite level of entropy without
enhancing both the client and the server. Moreover, it's
straightforward to design a system with acceptable security where we
change both client and server. The only issue is how best to pack the
entropy into the protocol.

So, the tricky issue is how to construct a system which doesn't
allow off-path attackers to convince the client that the server
doesn't speak the new, stronger version. In order for this to
happen, even an unenhanced server needs to echo back the
entropy value provided by the client. Otherwise, an offpath
attacker can forge a negative response. It seems like Duane's
suggested name mangling scheme has this property, no?

-Ekr

---

From: Paul Vixie <[email-masked]>
Date: Mon, 21 Jul 2008 04:11:35 +0000

Donald Eastlake wrote:
> them:

i prefer donald's previous work (TKEY) which, with TCP transport, is not
subject to downgrade attacks as XQID, cookies, and EDNS all are.

> From: Eric Rescorla <[email-masked]>
> 
> ... 
> approach that provides the requisite level of entropy without enhancing
> both the client and the server. Moreover, it's straightforward to design
> a system with acceptable security where we change both client and server.
> The only issue is how best to pack the entropy into the protocol.

this is close, but subtly incorrect on a factual basis.  it is easy to think
about and propose and discuss protocol changes that would add entropy, but
it is very hard (where difficulty is measured in number of years before wide
public use of the new mechanism) to standardize, implement, and deploy such.

> So, the tricky issue is how to construct a system which doesn't allow
> off-path attackers to convince the client that the server doesn't speak
> the new, stronger version. In order for this to happen, even an
> unenhanced server needs to echo back the entropy value provided by the
> client. Otherwise, an offpath attacker can forge a negative response. It
> seems like Duane's suggested name mangling scheme has this property, no?

again, this is close, but there are wheels within wheels.  the thing we have
to prevent a forger from doing is convincing us (erroneously) that the new
higher-strength mechanism did not work, and it's nec'y to go back to normal
DNS without the additional protections.  one way to do that is, as you say,
to have even unenhanced responders echo back the new entropy.  that's what
draft-forgery-resilience does, and that's what draft-0x20 does.  it's not
what draft-xqid or draft-cookies or any form of RFC-TSIG does, and it's not
what "add an extra label to the QNAME" or "add an extra question" would do
and it's not what anything based on EDNS would do.  those things all require
changes to the responder in order to get new entropy echoed, so the responder
in those proposals would be "enhanced" rather than "unenhanced."

but, the other way to prevent forgers from convincing an initiator to fall
back to lower-strength mechanisms, is to negotiate the use of new higher
strength mechanisms using a negotiation protocol, such as TKEY over TCP,
which is really "nontrivial" if not outright "damned difficult" to interfere
with from off-path, even if an attacker has the ability to spoof IP source
addresses, and time their packets perfectly well.  that's what i proposed
in my message here yesterday which is at the top of this thread ("dns hop
by hop transaction security for queries").

---

From: Tony Finch <[email-masked]>
Date: Mon, 21 Jul 2008 13:20:21 +0100

On Sun, 20 Jul 2008, Paul Hoffman wrote:
> > A trivial solution that wouldn't break anything might be just to
> > prefix something to the front of all hostnames that both ends strip
> > before processing them
>

If you append the cookie to the end of the domainname, e.g.
cyan.csi.cam.ac.uk.d41d8cd98f00b204e9800998ecf8427e.xqid.arpa,
then an old resolver doesn't need to be changed to strip the
extra labels so long as there's an AS112-alike handling queries
to xqid.arpa. However the nonce doesn't appear early in the
packet so Paul Vixie's worries about ICMP still apply. It's
also a disgusting hack.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
SOUTH UTSIRE: NORTHWESTERLY 5 TO 7. ROUGH OR VERY ROUGH DECREASING MODERATE OR
ROUGH. SHOWERS. MODERATE OR GOOD.

---

From: "Donald Eastlake" <[email-masked]>
Date: Mon, 21 Jul 2008 10:39:27 -0400

> packet so Paul Vixie's worries about ICMP still apply. It's

And if you ever had names at or approaching the name length limit, you can't
use it.
Donald

---

From: David Conrad <[email-masked]>
Date: Mon, 21 Jul 2008 21:37:22 -0700

> acquired but then discarded, then TSIG must not be used on  

Oh.  I get it.  You're trying to make deploying DNSSEC look easy in  
comparison.

:-)

Regards,
-drc

---

From: Paul Vixie <[email-masked]>
Date: Tue, 22 Jul 2008 04:59:48 +0000

> Oh.  I get it.  You're trying to make deploying DNSSEC look easy in

:-).

if there are no configuration knobs, no new error messages, no changes to
DHCP or /etc/resolv.conf or rendezvous, and no dependencies on the U S Gov't
to approve signing something before we can all start using the technology,
then it will be extraordinarily easier to deploy than DNSSEC.  it's just code
and there are no forklifts.

---

From: Alex Bligh <[email-masked]>
Date: Tue, 22 Jul 2008 07:53:49 +0100

--On 22 July 2008 04:59:48 +0000 Paul Vixie <[email-masked]> wrote:

> DHCP or /etc/resolv.conf or rendezvous, and no dependencies on the U S
> Gov't to approve signing something before we can all start using the
> technology, then it will be extraordinarily easier to deploy than DNSSEC.
> it's just code and there are no forklifts.

How much of the perceived problem is lack of signing by USG in your
opinion? I think there are other options (along the lines of DLV) that
would allow faster deployment if this was substantially the longest
pole in the tent and would allow CNOBIN, ccTLDs etc. to sign their
zones if they were so minded. Clearly this would leave individual
users to sign their zones, but those being spoofed / phished would
have every incentive to get on with it.

Alex

---

From: Paul Vixie <[email-masked]>
Date: Tue, 22 Jul 2008 07:05:19 +0000

> > if there are no configuration knobs, no new error messages, no changes
> > to DHCP or /etc/resolv.conf or rendezvous, and no dependencies on the U
> > S Gov't to approve signing something before we can all start using the
> > technology, then it will be extraordinarily easier to deploy than
> > DNSSEC.  it's just code and there are no forklifts.
> 
> How much of the perceived problem is lack of signing by USG in your opin?

icann can't make a change of this kind to the root zone without permission
from a lot of people, definitely including its board and USG, probably
including IAB or IESG, and possibly including its SSAC and RSSAC and GAC
and ALAC committees.  i don't know that USG is the last remaining approval,
and for that matter i don't know if USG has been asked to approve anything.

> I think there are other options (along the lines of DLV) that would allow
> faster deployment if this was substantially the longest pole in the tent
> and would allow CNOBIN, ccTLDs etc. to sign their zones if they were so
> minded. Clearly this would leave individual users to sign their zones,
> but those being spoofed / phished would have every incentive to get on
> with it.

suck though it may, we have to deploy dnssec.  if icann can't sign the root
zone then the TLDs and/or everybody else will have to make other arrangements,
in which roy arends' DLVPTR work could be very important, or in which DLV
could play a transition role.  had we been able to bite, chew, and swallow
dnssec, we could just use SIG(0) for stubs, and UDPPORT / QID predictability
would not matter.

i apologize for not making this case clearly enough when we launched DLV.  i
think most folks were so concerned about DLV being a power/glory grab that
the merits and justifications and goals just didn't seem to register at all.

---

From: Alex Bligh <[email-masked]>
Date: Tue, 22 Jul 2008 08:25:37 +0100

Paul,

> and ALAC committees.  i don't know that USG is the last remaining
> approval, and for that matter i don't know if USG has been asked to
> approve anything.

Sorry, question incorrectly posed. How much of a perceived problem is
lack of signing of the root zone? IE if a magic wand was waved and the
root zone suddenly signed, how much of the problem would that fix? As
I think there may be other spells to cast which would give sufficient
band-aid without the root being signed (not involving ICANN or anyone
else signing the zone).

> suck though it may, we have to deploy dnssec.  if icann can't sign the
> root zone then the TLDs and/or everybody else will have to make other
> arrangements, in which roy arends' DLVPTR work could be very important,
> or in which DLV could play a transition role.  had we been able to bite,
> chew, and swallow dnssec, we could just use SIG(0) for stubs, and UDPPORT
> / QID predictability would not matter.

I think my question is then "is making other arrangements actually that
hard technically?..."

> i apologize for not making this case clearly enough when we launched DLV.
> i think most folks were so concerned about DLV being a power/glory grab
> that the merits and justifications and goals just didn't seem to register
> at all.

"... or does it boil down to a similar but different set of political
organisational problems to signing the root?"

Alex

---

From: Paul Vixie <[email-masked]>
Date: Tue, 22 Jul 2008 07:31:23 +0000

> root zone suddenly signed, how much of the problem would that fix?

i predict that 50 or so CCTLDs would sign within six months, and that COM
would be signed within two years.  i suppose it's saying something about
the real expectations that those are optimistic "magic wand" numbers.

> I think my question is then "is making other arrangements actually that

no.  DLV works today.  its problem, similar to the two-query approach's
problem, is that it won't scale to the size of the internet and the lifetime
of our grandchildren's grandchildren.  for that, we need roy arends' DLVPTR.