Subject: [dnsext] My Final Thoughts/Conclusions for forgery resistance...

From: Nicholas Weaver <[email-masked]>
Date: Fri, 14 Nov 2008 11:26:44 -0800

these are my personal thoughts/recommendations for the IETF meeting,  
based on all that has gone on in the list and in various people's IDs.

The big Big BIG deal stuff:

Recursive and stub resolvers MUST have at least 30b of entropy in each  
query.

[One other issue to be discussed in person]

The big deal stuff:

Recursive and stub resolvers SHOULD have at least 40b of entropy in  
each query.  This makes attacks require a better part of a  
terapacket.  Even over GigE, it would take ~4 days to launch such an  
attack with no other protections.

Recursive and stub resolvers SHOULD contact a properly constructed  
authority to check if entropy sources (eg, port #, IP address, 0x20)  
are being removed upon startup and upon changing IP address.

If duplication is used to generate a query with additional entropy,  
the following policy SHOULD be used: [1]

a)  If both responses agree, accept the response into the cache and  
return it.
b)  If both responses have an overlap on the returned RRSet, accept  
and return the intersection of the two RRsets

c)  If there is no intersection between the returned RRSets, generate  
a THIRD query:
c1)  If two of the three responses have overlap on the returned  
RRSets, accept and return the intersection of the two RRSets
c2)  If there is no overlap between all three RRSets, DO NOT cache any  
value, return a randomly selected one of the responses with TTL=0.

Any volatile authority (one which would return different responses to  
back-to-back queries for the same resource from the same remote host)  
is strongly encouraged to ensure that, if the same remote resolver  
conducts two or more queries for the same record within a 1 second  
time-window, the remote resolver will receive responses which at least  
have some overlap in their RRSets.  Note that as long as such  
authorities are returning records with TTL !=0, they are not actually  
benefiting from being volatile.  Without such a change, the  
authority's responses would resolve but not cache.

If a resolver is using 0x20 to increase query entropy, it MUST use  
either a random string or a pseudo-random function (preferably HMAC)  
to generate the random string used for xor'ing with the query name.  [2]

Recursive resolvers MUST NOT return a valid response for a dotless  
name unless specifically configured to do so.

Less important but IMO still very valuable:

Recursive and stub resolvers SHOULD implement scoping rules or an  
approximation thereof (eg, Unbound) on glue acceptance to eliminate  
race-until-win attacks and other cache-poisoning attacks.  [3]

Less important:

Resolvers MAY interpret "changed duplicate response" (two valid  
responses to the same query but with different values) as an attack,  
and may void the cache entry for the response.  If interpreting this  
as an attack, a recursive resolver should also forward the second  
response to the originating client, with the TTL changed to 0 seconds,  
to act as an indicator of a detected attack.

[1]  This policy has the following effect when not under attack:  If  
an authority is not volatile (returns consistent responses), it will  
always resolve and cache properly, and this will not add latency as  
the first two queries can be conducted in parallel.  If an authority  
is volatile, it will resolve but not cache and experience higher load,  
and will also experience one additional RTT of latency when resolving  
a name.

When under attack, if the authority is not volatile, the attacker  
needs to win two races out of three, creating an effective query  
entropy greater than 2k-2 for protecting both the transaction and cache.

When under attack, if the authority is volatile, the attacker needs to  
win two races out of three to affect the cache, creating an effective  
query entropy greater than 2k-2 for protecting the cache.  In order to  
affect the transaction, the attacker needs to win the randomly  
selected race, giving an effective entropy of k for protecting the  
transaction.

Thus this duplication strategy provides both transaction and cache  
protection for non-volatile names, and cache protection for volatile  
names, while not reducing transaction protection for volatile names.

Also, duplication is only needed if the remote authority doesn't  
support 0x20, the full name in question is less than 8 characters with  
0x20, or if the recursive resolver is behind an entropy-stripping  
device (a NAT), to achieve the 40b target entropy.  The other case for  
duplication is as a response in a detection-and-response cycle when a  
resolver detects that it is under attack.

[2] Hovav Shacham and I have a small draftlet of text on how to do  
this and why written in the past week as an outgrowth of a discussion  
with David Dagon at CCS, but we can't put it up on the IETF site until  
monday.  Its not really designed to be standalone, but as a piece of  
text with additional justification to include in the 0x20 document  
should this become an RFC.

Temporarily, a copy is available at http://www.icsi.berkeley.edu/~nweaver/draft-weaver-dnsext-0x20-string-selection-00.txt 
  .  HMAC allows the 0x20 process to be stateless.

[3] This COMPLEMENTS increasing query entropy:  Increased query  
entropy increases attacker work in PACKETS.  No race-until-win  
increases attacker work in TIME to target an individual name.  Eg,  
with a TTL of just 1 second, and a RTT to the legit authority of  
200ms, no-race-until-win means that targeting a single name protected  
by 40b of entropy on a GigE requires 20 days instead of 4.  With a TTL  
of 60 seconds, targeting a single name now requires 3 years.

If no response is received for a name, there should be an implicit TTL  
of 60 seconds before that name would be queried again (prevents any  
incentive for blocking the legitimate authority.).

--
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: Jim Reid <[email-masked]>
Date: Fri, 14 Nov 2008 19:58:41 +0000

On Nov 14, 2008, at 19:26, Nicholas Weaver wrote:

> Recursive and stub resolvers MUST have at least 30b of entropy in  
> each query.

Why 30b? What numbers do you have to back this up?

---

From: Nicholas Weaver <[email-masked]>
Date: Fri, 14 Nov 2008 12:16:38 -0800

> Why 30b? What numbers do you have to back this up?

30b requires ~1/2 a gigapacket to have a reasonable expectation of  
poisoning an entry.  For a 100 Mbps connection to the recursive  
resolver, this requires ~1+ hour to corrupt a single name with no race- 
until-win protection, and a VERY noticeable amount of traffic (a  
nontrivial DOS attack).

If you DO have race-until-win protection and the attacker is targeting  
a name with a 60s TTL, an attacker with 100 Mbps requires 300 hours to  
corrupt a singly targeted name.

And sending a spoofed gigapacket of UDP is not cheap, even for a botnet.

More importantly, as long as there are significant numbers of  
resolvers who DON'T randomize their source port (16b of entropy),  
nobody will actually bother attacking the resolvers with ~30b of  
entropy anyway unless there is a specific reason for targeting THAT  
resolver, while actually gaining 30b of entropy is straightforward  
(port randomization is sufficient).

30b also gives plenty of safety margin if you are doing a detection &  
response strategy, where response is duplication (which gets 58b of  
entropy in that case)

It actually takes ~27b in many cases to blind-RST attack a TCP flow,  
as ACKs aren't checked and most TCP stacks are predictable in port  
creation and accept any in-window RST.

---

From: "George Barwood" <[email-masked]>
Date: Mon, 17 Nov 2008 17:22:11 -0000

> c)  If there is no intersection between the returned RRSets, generate  a 
> THIRD query:
> c1)  If two of the three responses have overlap on the returned  RRSets, 
> accept and return the intersection of the two RRSets

This last (c2) implies that when port randomization is unavailable,
protection may be only 16 bits.

It seems more logical to repeat until suitable protection is obtained, at
least for "essential" resource record sets. This is entirely practical, I
have been testing such a resolver now for more than a month with no
problems. I describe this in more detail in my draft

http://www.ietf.org/internet-drafts/draft-barwood-dnsext-fr-resolver-mitigations-08.txt
https://datatracker.ietf.org/drafts/draft-barwood-dnsext-fr-resolver-mitigations/

Generally I agree that repetition is fundamental, although I prefer to
formulate it in a more general way.

It needs some programming effort to implement, but does work perfectly well.