Re: Outstanding queries vs. source port randomization entropy
Mark Andrews
> [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 namedroppe...@ops.ietf.org with
> the word 'unsubscribe' in a single line as the message text body.
> archive: <http://ops.ietf.org/lists/namedroppers/>
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: Mark_A...@isc.org
--
to unsubscribe send a message to namedroppe...@ops.ietf.org with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>
Mark Andrews
> On 2008-08-31 23:26, Mark Andrews wrote:
> > Jefferson Ogata wrote [attribution restored]:
> >> 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.
> >>
> > 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.
>
> The question in that case remains: does any existing resolver that
> supports source port randomization actually do this?
>
> > 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.
>
> 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
> --
> Jefferson Ogata : Internetworker, Antibozo
>
> --
> to unsubscribe send a message to namedroppe...@ops.ietf.org with
> the word 'unsubscribe' in a single line as the message text body.
> archive: <http://ops.ietf.org/lists/namedroppers/>
Mark Andrews
Additionally with sendto() you will tend to get locked onto
a open set of ports as you need to wait for the next response
whenever you re-use a port. With connect() each transaction
becomes almost completely independent of other transaction.
Note all the probability analysis being done assume
independent transactions. If you have depenancies between
transactions (i.e. re-use of a socket) then all the analyses
needs to be redone to factor in that socket re-use.
Even without doing such a analysis I can tell you that
re-use makes the system weaker not stronger.
Mark Andrews
> On 2008-09-01 00:46, Mark Andrews wrote:
> > Additionally with sendto() you will tend to get locked onto
> > a open set of ports as you need to wait for the next response
> > whenever you re-use a port. With connect() each transaction
> > becomes almost completely independent of other transaction.
>
> you get locked into a sub-optimal set of ports?
Ususally you don't have 2^16 ports in use.
> Your point about combining connected UDP sockets with SO_REUSEADDR in
> order to take advantage of kernel filtering and avoid impacting on other
> uses of UDP is well taken, but a drawback I see is that your file
> descriptor set has to continue to grow past 2^16 if you don't actually
> reuse existing sockets.
Yes. There are tradeoffs everywhere in this space.
Mark
JINMEI Tatuya / 神明達哉
Jefferson Ogata <bind-...@antibozo.net> wrote:
> >> I don't see why you need SO_REUSEADDR. Why not simply leave the UDP port
> >> 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.
>
> I see. That clarifies it. So, since you're writing from ISC, does BIND
> do this, or is it on the roadmap if not?
If "this" means connecting UDP query sockets, the latest beta versions
of BIND9 (e.g., BIND 9.4.3b2) do that. These versions also set the
SO_REUSEADDR option so that the same port can be simultaneously chosen
for different sockets as long as the destinations are different. This
implementation choice is actually based on the concern you mentioned:
possibly reduced entropy when we completely prohibit the simultaneous
use of the same port number. (For that matter it also allows to reuse
the same QID for different queries for the same reason).
In practice, however, this doesn't matter much in this context anyway,
since by default the server doesn't open more than 4096 sockets.
Naively limiting the max number of open sockets is subject to a
trivial DoS as you mentioned, so this implementation also introduces a
notion of quota on the number of open queries: if the number exceeds
the quota, the already queries will be aborted (and the associated
sockets will be closed) so that new queries are reasonably accepted.
Using non-connected sockets and allowing it to be reused for multiple
queries are another option, again, as you indicated. If I understand
the code correctly, unbound takes this approach.
---
JINMEI, Tatuya
Internet Systems Consortium, Inc.