Re: 2 forwarded messages...DNSEXT discussion of Day and Kaminsky

On Fri, Feb 13, 2009 at 04:44:01PM -0500, Dean Anderson wrote:

> Again, you have the math incorrect. The 200 outstanding queries each 
> have a unique QID.  Therefore, the attacker must conduct a birthday 
> attack, trying to mache a correct port with a correct QID.

OK, I tried to follow your math. But it really doesn't make any sense to
me.

How is this about a birthday attack matching QID and port? Is it not
about a birthday attack matching one of the attacker's spoofed packets
to the QID/port combination selected by dnscache?

Which would mean:

> The CRC handbook of Applied Cryptography gives the formulas needed in
> section 2.1.5, Birthday problems. On a regular unix system, the first
> 1025 ports usually won't be assigned to a socket, leaving 64510 ports
> available for use.  The math for the first case:
> 
> model B (2 urns, no replacement)
> p4(64510, 200, 200)

...that the first parameter (the random space) would be 64510*65536. The
second parameter (number of balls in one urn) can remain 200 (MAXUDP).
The third parameter (number of balls in the other urn) is actually the
number of packets sent by the attacker.

And p4 is the _probability_ of at least one coincidence. So the formula
does not yield the number of expected packets; you calculate the
probability based on a particular number of packets. So you might ask
about the number of packets required to make the probability 50%.

So the number we really want to know is "n", where 0.5 = p4(64510*65536,
200, n).

Which turns out to be around 16 million.

-Peff