Re: update on the djbdns bugs? (fwd)

I think I've forwared this before.

		--Dean

---------- Forwarded message ----------
Date: Sat, 4 Oct 2008 15:18:34 -0400 (EDT)
From: Dean Anderson <[email protected]>
To: Dan Kaminsky <[email protected]>
Cc: Kevin Day <[email protected]>, [email protected]
Subject: Re: update on the djbdns bugs?

On Fri, 3 Oct 2008, Dean Anderson wrote:
> 
> I didn't say the birthday attack was obscure. I said that neither Kevin
> Day nor Dan Kaminsky has reported an actual flaw in the implementation
> of DJBDNS.  BTW, a birthday attack is not a flaw in DJBDNS, and isn't an
> _implementation_ flaw in anything.
> 
> A 'birthday attack' can happen anytime there is a modular combination
> that can be repeated. It affects RSA, etc.  You can't program your way
> out of it.  You can't algorithm your way out of it. Its a mathematical
> fact.  Saying you aren't vulnerable to a birthday attack is like saying
> you do particle physics without the heisenberg uncertainty principle.
> Its just nonsense.

I decided that Joe Biden has the right approach, so I did the math:  
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.

Supposing Kaminsky's claim that DJBDNS can have 256 outstanding queries
was correct, and the attacker sent 256 responses, the math is:

model B (2 urns, no replacement)
p4(63488, 256, 256)
exact formula: 1 - (perm(m, n1+n2) / (perm(m, n1) * perm(m, n2))
   simplified (n1 = n2): 1 - (perm(m, 2n) / (perm(m,n) ^ 2))

(%i1) float( 1 - ( 64510! / ( 64510 - 512)! ) / ( ( 64510! / ( 64510 - 256)! ) ^ 2 ) );
(%o1)                          0.63938588531995


about 64% probability of at least one coincidence (attacker gets a right
port)

(%i2) (%o1 * (1/65536));
(%o2)                        9.7562543536369527E-6
(%i3) (1 / %o2);
(%o3)                          102498.3527235756

(%i7) 102499 * 256;
(%o7)                              26239744

On those assumptions, one would have to send 26 million packets to
succeed. Inexplicably, Kaminsky asserts only 21 million, and that one
has a 1/256 chance of succeeding. There is no basis for either of
Kaminsky's claims.  No matter.

Kaminsky's assertion about DNSCache operation is also not correct.  
Multiple outstanding packets for the same query are only sent to
different servers. Each repeated query has a different query id and a
different port. (see the thisudp() function). Repeats are only sent
after a timeout.  And the response must contain the correct query,
besides being on the correct port with the correct queryid. (see the
irrelevant() function).  Arranging for 256 different queries does not
aid the attack as Kaminsky asserts.

The correct math is 

model B (2 urns, no replacement)
p4(64510, 256, 1)
exact formula: 1 - (perm(m, n1+n2) / (perm(m, n1) * perm(m, n2))

(%i8) float ( 1 - ( 64510! / ( 64510 - 257)! ) / ( ( 64510! / ( 64510 - 256)! ) * (64510! / ( 64510 - 1 )! ) ) );
(%o8)                         0.0039683769958146
(%i9) (%o8 * (1/65536));
(%o9)                        6.0552627499612468E-8
(%i10) (1 / %o9);
(%o10)                       1.6514559999999998E+7
(%i43) 256 * %o10;
(%o43)                       4.2277273599999995E+9
                     
If you repeat this attack 16 million times, one would need to send 4.2
billion packets. This is higher than I expected. Surprisingly, if you
increase the packets per try, the total sent remains the same:

model B (2 urns, no replacement)
p4(64510, 4096, 1)
(%i35) float ( 1 - ( 64510! / ( 64510 - 4097)! ) / ( ( 64510! / ( 64510 - 4096)! ) * (64510! / ( 64510 - 1 )! ) ) );
(%o35)                         0.063494031933034
(%i36) %o35 * (1/65536);
(%o36)                       9.6884203999379948E-7
(%i37) 1 / %o36;
(%o37)                             1032160.0
(%i38) 4096 * %o37;
(%o38)                       4.2277273599999995E+9

The attacker can arrange to expend the available udp ports until the
available ports are substantially less than 64510. If the attacker can
reduce the ports to 32000 (about half), one also cuts the expected
number of packets in half. Of course, the attacker has to know (via
receipt) which ports are actually in use, thus possibly revealing their
location. Maybe not a good strategy, after all.

(%i44) float ( 1 - ( 32000! / ( 32000 - 4097)! ) / ( ( 32000! / ( 32000 
- 4096)! ) * (32000! / ( 32000 - 1 )! ) ) );
(%o44)                               0.128
(%i45) %o44 * (1/65536);
(%o45)                            1.953125E-6
(%i46) 1 / %o45;
(%o46)                             512000.0
(%i47) 4096 * %;
(%o47)                            2.097152E+9




		--Dean

-- 
Av8 Internet   Prepared to pay a premium for better service?
www.av8.net         faster, more reliable, better service
617 344 9000