Subject: Treatment of Bad IDs in entropy calculation

From: "George Barwood" <[email-masked]>
Date: Tue, 26 Aug 2008 18:57:09 +0100

I just realised that Bad IDs can be neatly fitted into the entropy discounting mechanism I described earlier

( http://ops.ietf.org/lists/namedroppers/namedroppers.2008/msg01439.html ).

The idea is to take into account the observed rate at which we are being attacked.

After computing the amount of entropy as before, we subtract Log2( BadIdCount ), where BadIdCount is the number of incorrect IDs observed while waiting for a response to the query.

For example:

ID = 16 bits
0x20 = 13 bits ( wWw.eXAmPle.Com )
200 Bad IDs seen = 8 bits

Effective entropy = 16 + 13 - 8 = 21 bits.

Dos ( denial of service ) can still occur if the attacker is sending enough spoof packets, so that effective entropy is reduced to zero, but if he can only spoof at moderate rates ( say a few thousand to the correct port per second ), resolution can still occur, albeit with extra requests.

Can anyone see a problem with this? It seems quite elegant to me.

---

From: Evan Hunt <[email-masked]>
Date: Tue, 26 Aug 2008 19:11:05 +0000

> After computing the amount of entropy as before, we subtract
> Log2( BadIdCount ), where BadIdCount is the number of incorrect IDs
> observed while waiting for a response to the query.

Interesting thought.  Why log2(), exactly?  I'm not objecting, just not
quite sure I follow your reasoning.  I guess it's "we've gotten 256 bad
packets, so let's make it 256 times harder to guess"--but why not 512, or
1024, or a million?

Are you thinking of BadIdCount as counting incorrect responses for *all*
pending queries, or just for race that's currently being run?

-- 
Evan Hunt -- [email-masked]
Internet Systems Consortium, Inc.

--
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: "George Barwood" <[email-masked]>
Date: Tue, 26 Aug 2008 21:11:44 +0100

> packets, so let's make it 256 times harder to guess"--but why not 512, or

At a trivial level, it's simply that probabilities are being computed in the 
log space ( or some similar jargon ). This seems reasonable, as high 
precision is not required.

To try to be more explicit:

Suppose I calculate the entropy for a single query / response to be 29 bits.

This is intended to mean that an attacker has only a 1 in 2^29 chance of 
spoofing the response.

If the attacker is using multiple guesses, then clearly his odds are 
improved by that factor.

The nice part is that his multiple guesses can be easily seen, and the 
appropriate adjustment made, so that the calculated effective entropy is 
still realistic.

> pending queries, or just for race that's currently being run?

Just for the race that is currently being run.

---

From: David Dagon <[email-masked]>
Date: Tue, 26 Aug 2008 22:23:30 -0400

> ( http://ops.ietf.org/lists/namedroppers/namedroppers.2008/msg01439.html ).

In short: I suspect you are describing a variation of channel
capacity, or some measure of signal/noise.  (There are many valid
security applications of such measurements.)

Caveat: I'm still digesting the GbDns source.  I'd like to offer some
preliminary comments on your minimum entropy calculation, based on
your email in this forum.  Please correct me if I've missed your
point.

> The idea is to take into account the observed rate at which we are

I think there are two (or more) ways to understand your minimum
entropy analysis:

  a) from a DNS operator's perspective, the minimum entropy is
     a potential distraction.  For some DNS operators, this is
     not as important as the discrete probability that a
     forged packet might match the {qid, sport, 0x20, etc.} 

> Effective entropy = 16 + 13 - 8 = 21 bits.

     Generally, if there are 2^{N} possible unique transaction tokens,
     the naive probability of success is 200/(2^{N}) ... and much,
     much more if there's a birthday window, of course.   Precisely,
     the failure of such a poisoning attack is:

\[
  1-p(n) = \bar{p}(n) = \prod_{k=0}^{n-1} \left(1 - \frac{1}{N-k}\right)
\]

     But most DNS servers have long since implemented duplicate
     upstream query protection.  We can therefore use the simple
     fraction to emphasize independence: the 200st failure does not
     make the 201st guess any more likely to (independently) match a
     transaction ID (again: *assuming* there is no birthday window,
     which otherwise significantly reduces the transaction integrity.)

     Another perspective, one I suspect you're considering, is:

  b) From a channel capacity perspective, the bad guesses are
     divisive (log 2) of the total keyspace, exactly as you proposed.
     Attacks are 'noise' compared to 'signal' from messages.
     Your ratio is not exactly S/N (you did not provide a bandwidth
     dimension).  But otherwise, it's the right idea and (as we say in
     Georgia) "good enough for government work".

     Seriously though, this perspective is useful for high-level
     decisions, such as research monitoring, characterizing DNS
     poisoning attempts as a "signal/noise" problem, and the mutual
     information found in large numbers of DNS transactions and
     poisonings.  I.e., one might care about the macro-level
     performance of DNS messaging as a channel to plan a lower-bound.

     A simple example: I might not make an embedded device that uses
     only 16 bits for TX tracking, based on minimum entropy analysis;
     I might instead consider the benefits of sport randomization
     (perhaps too expensive on my chosen platform), or 0x20 (variable,
     depending on the target users[0]), or some other protections.

     With a bandwidth dimension (not covered in minimum entropy
     analysis, AFAIK), one can perform this sort of risk analysis.

>  Can anyone see a problem with this? 

I think you'll encounter differences of opinion, depending on the
operator's perspective.  These may be expressed in terms that range
from sympathetic/appreciative to unhelpful/cynical.  But your general
S/N analysis (bandwidth and minimum entropy) is quite useful for
lower-bound estimation, I think.

Disagreement will depend on values: Local administrators will want
assurances that each malicious response has a low discrete probability
of being successful.  Network architects (particularly those realistic
about DNSSEC deployment, or facing hardware barriers for sport
adoption), will appreciate a S/N analysis.

In some networks, the need for improved security is measurably more
urgent, based on your minimum entropy analysis.  The solutions may
include not only sport randomization, but 0x20 encoding, DNSSEC,
stealthy forwarding, rfc 2181 gymnastics/policy, TCP fallback, etc.
Each solution has a cost, and may not be acceptable for everyone else,
or seen as anti-social if widely deployed.  

But you've proposed a way to measure the (bandwidth-adjusted)
benefit--one needs only compare this to costs.  I've not seen that
before; that's useful.

I don't know if I've described the differences in perspective
correctly.  I'd recommend reviewing the
'draft-wijngaards-dnsext-resolver-side-mitigation-00' document, which
seems to nicely capture much of the conversation Paul Vixie, Nick
Weaver and others have offered in this forum re: modality.

>  It seems quite elegant to me.

I agree; just add bandwidth (or point out where I've missed this).

I am still looking for a universal solution that satisfies the needs
of local admins ("make me secure; at all times; damn your numbers"),
and the oft-overlooked realities of large-scale DNS deployments
("locally clued users may be secure; but how can we herd 16M+ cats
into upgrading?")

[0] We've completed an overview of DNS-0x20, to appear at the CCS08
    conference:

     http://fritz.cc.gt.atl.ga.us/ccs08/ccs202-dagon.pdf

    We state: we find roughly ~12-16 bits; you found ~12.  This is a
    bias in any measurement, and there is no 'right' number, only
    densities.  Where one stops caring is a cost function, that
    you seem to propose.

-- 
David Dagon              /"\                          "When cryptography
[email-masked]      \ /  ASCII RIBBON CAMPAIGN    is outlawed, bayl
Ph.D. Student             X     AGAINST HTML MAIL      bhgynjf jvyy unir
Georgia Inst. of Tech.   / \                           cevinpl."