Subject: Re: I-D Action:draft-ietf-dnsext-forgery-resilience-02.txt

From: Edward Lewis <[email-masked]>
Date: Tue, 11 Mar 2008 10:55:55 -0400

Referring to:

>Title           : Measures for making DNS more resilient against 
>forged answers
>Date            : 2008-02-18
>A URL for this Internet-Draft is:
>http://www.ietf.org/internet-drafts/draft-ietf-dnsext-forgery-resilience-02.txt

In Section 3:

#   DNS data is accepted by a resolver if and only if:
#
#   1.  The question section of the reply packet is identical to that of
#       a question packet currently waiting for an answer
#
...
#
#   5.  It is the first answer to match the previous four conditions.

I"m not sure if this is a statement of historic fact, current 
recommended behavior, or a proposed set of rules.  So my comments 
might just slide off the table.

I think #1 isn't a "given" rule, as there is another proto-draft 
distributed to try to make it so.

I disagree with #5.  In one scenario, the "last" answer to match is 
the best - that is, if the true responder is "further away" than the 
source of a stuffed answer.  (Such as a DNS spoofer on the same 
wireless LAN the client is on.)

All in all, there's no hard and fast rule about whether it is the 
"first" or "last" that is most credible or trustworthy.

# 4.5.  Have the answer arrive before the authentic answer
#
#    Once any packet has matched the previous four conditions, no further
#    answers should be accepted.

Again, not sure of the tone of this statement, I think this is a bad 
recommendation and, fwiw, a general weakness in DNSSEC?TSIG/SIG(0) 
implementations.

It isn't the first answer that is the end of the network transaction, 
it's the first verifiable answer that is needed.  Receivers of DNS 
responses ought to keep listening past the first receipt of an answer 
that matches the superficial criteria, listening until they verify an 
answer or hit the timeout for a non-response.

# 5.  Birthday attacks
#
#    The so called birthday paradox means that a group of 22 people
#    suffices to have a more than even chance of having two or more
#   members of the group share a birthday.

Such a statement of fact should be supported by a reference to a 
proof, or include a proof.

Doesn't the number 22 have to do with the fact that there are just 
366 possible dates?

# 6.  Accepting only in-zone answers
#
#   Answers from authoritative nameservers often contain information that
#   is not part of the zone for which we deem it authoritative.  As an
#   example, a query for the MX record of a domain might get as its
#   answer a mail exchanger in another domain, and additionally the IP
#   address of this mail exchanger.
#
#   If accepted uncritically, the resolver stands the chance of accepting
#   data from an untrusted source.  Care must be taken to only accept
#   data if it is known that the originator is authoritative for that
#   data.
#
#   One very simple way to achieve this is to only accept data if it is
#   part of the domain we asked the question for.

What if you ask a root server for the A record of 
a.root-servers.net.?  (Let's forget that most of the root servers are 
"illegitimate" authoritative servers for that zone.)

The root server is also authoritative for root-servers.net. and will 
choose to respond with data from that zone.  The server doesn't know 
what zone the query is being "shot" at, so it can't tune the answer 
to be a referral from the root to dotNET (net.).

Queries aren't sent to domains, they are sent to servers.  Answers 
are generated from zone data available at a server.

Perhaps what should be recommended is that a server should answer 
from only one zone at a time and provide the "proof" that is is 
authoritative for the zone providing the source for the answer.

# 7.  Combined difficulty

A question on these numbers

#   A realistic minimal DNS answer consists of around 80 bytes, including
#   IP headers, making the packet rate above correspond to a respectable
#   burst of 416Mb/s.
#...
#   These numbers change when a window of a full second is assumed,
#...
#   This reduces the needed bandwidth to 42 Mb/s.
#
#   If in addition the attacker is granted more than a single chance and
#   allowed up to 60 minutes of work on a domain with a time to live of
#   300 seconds, a meagre 4Mb/s suffices for a 50% chance at getting fake
#   data accepted.

There are bandwidths needed to attack (cache poison) ONE resolver for 
ONE RRset or at most ONE domain name, right?   I.e., you can't easily 
pull off a widespread cache poisoning with only this amount of 
bandwidth.

# 9. Countermeasures

#   If a resolver sends out multiple equivalent questions to any
#   authoritative server, before receiving an answer, all MUST have
#   identical ID, source address and source port.

Not a MUST, when I wrote some probing software I purposefully altered 
the ID so that I could detect which query (1st, 2nd, Nth) was being 
answered.

#   Resolvers SHOULD favour authoritative nameservers with which a trust
#   relation has been established; Stub-resolvers SHOULD be able to use
#   TSIG ([RFC2845]) or IPSEC ([RFC2401]) when communicating with their
#   recursive resolver.

Or SIG(0) or some other message authentication method or 
point-to-point links or other security precautions taken on the LAN 
or ... i.e., an open ended list of mechanisms are available and in 
use.

-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                                +1-571-434-5468
NeuStar

Mail archives, backups.  Sometimes I think the true beneficiaries of
standards work are the suppliers of disk drives.

--
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: Tue, 11 Mar 2008 15:54:29 +0000

--On 11 March 2008 10:55:55 -0400 Edward Lewis <[email-masked]> wrote:

> I"m not sure if this is a statement of historic fact, current recommended
> behavior, or a proposed set of rules.  So my comments might just slide
> off the table.
>
> I disagree with #5.  In one scenario, the "last" answer to match is the
> best - that is, if the true responder is "further away" than the source
> of a stuffed answer.  (Such as a DNS spoofer on the same wireless LAN the
> client is on.)
>
> All in all, there's no hard and fast rule about whether it is the "first"
> or "last" that is most credible or trustworthy.

As DNS resolvers are not yet clairvoyant, they have no way of knowing
whether additional answers will arrive after the one they have received.
Unless the resolver waits under all circumstances for further answers
(with some timeout) and uses some heuristic to determine which will
be valid, or waits under certain circumstances, they default is as
by logically elimination the one described above.

If you are suggesting allowing the possibility of waiting, how about
"No answer has arrived before this one which as met the four conditions
and has been accepted by the resolver" (as 'accepted' appears to mean
'has been treated as valid). This leaves the possibility open to the
resolver to 'not make a decision' whilst it waits or gathers further
information.

> Such a statement of fact should be supported by a reference to a proof,
> or include a proof.
>
> Doesn't the number 22 have to do with the fact that there are just 366
> possible dates?

I think it's actually 23, and is normally calculated on a 365 day year.

If this is really necessary, how about adding:

"This is a special case of a collision problem: where x independent random
variables each have having n possible values, the probability of
all such variables having distinct values is:

        / 0                  (where x>n)
        |
p(n,x) =|           n!
        | 1 - ----------     (where x<=n)
        |       x
        \      n  . (n-x)!

For large n,x this approximates to a normal distribution, i.e.

                   2
                - x / (2.n)
p(n,x) ~= 1 - e

Therefore, to avoid a collision with probability p, using the above
approximation, the number of variables x must be such that

         __________________
        /           (  1  )
  x <  / 2 . n . ln ( --- )
      V             ( 1-p )

In this case p is the acceptable probability of a collision, and n the
number of possible tuples making the query distinct and undiscoverable
by the attacker."

I suspect however, that this is not necessary.

Alex

---

From: Steve Crocker <[email-masked]>
Date: Tue, 11 Mar 2008 12:09:10 -0400

I'm not entirely sure why there's a discussion of birthday attacks  
because I haven't been following this thread closely, but I can  
clarify the math on birthday attacks.  See below.

> Doesn't the number 22 have to do with the fact that there are just  

As noted, a randomly selected group of about 23 people there's a 50%  
probability that two or more people will share the same birthday  
(month and year).  The number does indeed depend on the number of  
possibilities.

For a group of k people, the probability of no duplication is

P(k) = (366 - 0)/366 * (366 - 1)/366 * (366 - 2)/366 ... (366 - k +1)/ 
366

When k is 23, the probability crosses below the 50% mark.

(This assumes all dates are equally probable.  Feb 29 is not equally  
probable, so this shifts the probabilities slightly.)

One application of the birthday problem which is very important is  
the potential for collision of hashes.  The SHA-1 hash is 160 bits,  
which means the population is 2^160, or about 1.46*10^48.  This is  
obviously a much bigger number than 366, and the method of  
calculating the 50% probability point shown above isn't practical.

With a little bit of math -- available in suitable textbooks or on  
request -- there is an excellent approximation.  The 50% balance  
point is approx 1.17 * sqrt(N).  The sqrt term has the effect of  
cutting the number of bits in half, so for SHA-1, when there is a  
total of roughly 2^80 messages, there will be approximately a 50%  
probability that two more messages will have the same hash.

Repeating the caveat, this calculation depends on uniform  
probabilities.  If the probabilities are skewed, the number needed  
for possible clash drops.

Steve

---

From: Alex Bligh <[email-masked]>
Date: Tue, 11 Mar 2008 16:18:56 +0000

--On 11 March 2008 15:54:29 +0000 Alex Bligh <[email-masked]> wrote:

> variables each have having n possible values

Not clear enough: try "where x independent random variables in a discrete
uniform distribution each having n possible values".

Alex

---

From: Edward Lewis <[email-masked]>
Date: Tue, 11 Mar 2008 12:52:45 -0400

At 15:54 +0000 3/11/08, Alex Bligh wrote:
>be valid, or waits under certain circumstances,

Exactly...

>the(y) default is as

Which I claim is an implementer taking the easy way out.

>resolver to 'not make a decision' whilst it waits or gathers further

It's like this, once you get a good answer, you are done.  When you 
get an answer that proves to be bad, instead of declaring defeat, see 
if another has fallen into the in basket.

You "destroy" the in-basket when you have a success or you give up 
(=hit the timeout).  If you destroy the in-basket without getting a 
good answer, you declare defeat.

(Regarding the birthday attack comment)

>I suspect however, that this is not necessary.

My first suggestion is to include a reference that covers what it is.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                                +1-571-434-5468
NeuStar

Never confuse activity with success.  Activity pays more.