Subject: Outstanding queries vs. source port randomization entropy

From: Jefferson Ogata <[email-masked]>
Date: Sun, 31 Aug 2008 20:24:47 +0000

[I posted a variation on this message as a comment on Dan Kaminsky's 
blog earlier today, but I'm skeptical he'll have the time to respond, so 
I'm throwing it out to a wider audience.]

So here's a question. With source port randomization, what prevents the 
following attack?

Attacker sets up a nameserver for example.com that receives queries but 
sends no responses, with an appropriate delegation. Attacker then asks 
the victim nameserver ~2^16 distinct queries under example.com in a 
short time frame. This effectively consumes the entire source port range 
with outstanding queries. The example.com nameserver observes the source 
port for each inbound recursive query from the victim nameserver; the 
one remaining source port that was not observed is the only port left to 
the victim nameserver for its next query. Attacker then asks victim 
nameserver for the domain to be poisoned, and forges the poison response 
targeting the remaining port.

I'm presenting an idealized attack here for the purpose of illustration. 
The principle is to deplete the entropy included in source port 
randomization by consuming the majority of available ports with 
outstanding queries. The attack would only be effective against a 
nameserver that allows close to 2^16 outstanding queries, i.e. high open 
file descriptor limit, FD_SETSIZE appropriately redefined, etc.; a 
nameserver that could have only 1024 outstanding requests, for example, 
would be DoSed before it would lose significant entropy. The outstanding 
requests could be distributed among many domains and distinct 
nameservers if necessary, as long as the nameservers coordinate. The 
attack could be partly mitigated on nameservers that allow ~2^16 
outstanding requests if the victim nameserver can reuse randomly chosen, 
already open sockets for multiple successive requests once ~2^16 ports 
are bound. The efficacy of this attack depends on the precise algorithm 
by which the victim uses new ports, and what limits are enforced.

I have to wonder how this has been addressed in the various resolvers 
that implement source port randomization. Where has this scenario been 
discussed before? It's too obvious not to have been considered earlier, 
but I've done some Googling and skimmed some list archives and haven't 
come up with anything.

-- 
Jefferson Ogata : Internetworker, Antibozo

--
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: Mark Andrews <[email-masked]>
Date: Mon, 01 Sep 2008 09:26:11 +1000

> but I've done some Googling and skimmed some list archives and haven't 

	Use connected UDP socket then kernel can also use the source
	address as a differentiator when delivering replies.  You
	can then support <ports> x <txid> to an individual destination.

	You still need to randomly select ports and randomly select
	txid.  When you have a collision you just need to repick
	one and/or the other.   A port collision alone lets you use
	a existing socket.

	For queries to another server you just set SO_REUSEADDR
	when you have a port collision with a port you already have
	open as the existing one is in a connected state.  If it
	is a port that is not already in use you don't set SO_REUSEADDR
	so you detect collisions with other applications.
	
	Mark
-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: Jefferson Ogata <[email-masked]>
Date: Sun, 31 Aug 2008 23:35:49 +0000

On 2008-08-31 23:26, Mark Andrews wrote:
> Jefferson Ogata wrote [attribution restored]:
>>  The 
>> are bound.

I believe I considered that possibility in the above part of my comment. 
The question in that case remains: does any existing resolver that 
supports source port randomization actually do this?

> 	so you detect collisions with other applications.

I don't see why you need SO_REUSEADDR. Why not simply leave the UDP port 
unconnected and use sendto in the first place?

---

From: Mark Andrews <[email-masked]>
Date: Mon, 01 Sep 2008 10:30:18 +1000

> unconnected and use sendto in the first place?

	Because you really want to have the kernel do the initial
	filtering of responses.  You don't want your recursive
	server seeing every stray UDP packet being sent to you.
	With the amount of malware out there that is trying to get
	in over UDP your recursive server will be getting lots of
	noise if you randomly choose such a port.  Connected sockets
	don't interfere with other uses of UDP (e.g. traceroute).
	You can't probe to see what ports are in use by the recursive
	server without making the server actually make queries to
	you.

	Mark

---

From: Jefferson Ogata <[email-masked]>
Date: Mon, 01 Sep 2008 00:50:07 +0000

> 	server without making the server actually make queries to

I see. That clarifies it. So, since you're writing from ISC, does BIND 
do this, or is it on the roadmap if not?