Subject: Proposed resolution to LLMNR Issue 39: Name Conflict Detection Algorithm

From: Bernard Aboba <[email-masked]>
Date: Wed, 21 May 2003 08:58:30 -0700 (PDT)

The text of LLMNR Issue 39 (and the ensuing discussion) is enclosed below.
The proposed fix is to delete the text relating to detection of conflicts
on healing of a network partition.  It was noted that the partition
healing problem is not considered serious in cases where the
probability of conflict is low. For example, partition healing is
not addressed in IPv6 neighbor discovery, whereas it is addressed in IPv4
linklocal addressing (via broadcasting of ARP replies) because the
probability of conflicts is much higher.  In the case of LLMNR, it is
possible to choose hostnames in such a way that the conflict probability
is relatively low, so that it is not clear that conflict detection on
partition healing is a real requirement.

In any case, the algorithm suggested for use in -19 is inappropriate
for several reasons:

a. It requires the processing of responses for which no query was sent.
This is not sensible from a security perspective.

b. Carrying out the algorithm becomes unwieldly in the case where a
cluster name is queried.  In this case the algorithm would require the
sender to forward cluster name responses to each member of the cluster,
requiring the sending of N(N-1) packets.

c. The algorithm appears to violate the rule that hosts should only
respond to queries for names over which they are authoritative.

The proposed fixes are as follows:

In Section 2.2, change:

"Responders MUST NOT respond to LLMNR queries for names they are not
authoritative for, except in the event of a discovered conflict, as
described in Section 4.  Responders SHOULD respond to LLMNR queries for
names and addresses they are authoritative for.  This applies to both
forward and reverse lookups."

To:

"Responders MUST NOT respond to LLMNR queries for names they are not
authoritative for.  Responders SHOULD respond to LLMNR queries for
names and addresses they are authoritative for.  This applies to both
forward and reverse lookups."

In Section 4, change:

"The name conflict detection mechanism doesn't prevent name conflicts
when previously partitioned segments are connected by a bridge.  In such
a situation, name conflicts are detected when a sender receives more
than one response to its LLMNR multicast query.  In this case, the
sender sends the first response that it received to all responders that
responded to this query except the first one, using UDP unicast.  A host
that receives a query response containing a UNIQUE resource record that
it owns, even if it didn't send such a query, MUST verify that no other
host within the LLMNR scope is authoritative for the same name, using
the mechanism described above.  Based on the result, the host detects
whether there is a name conflict and acts accordingly."

To:

"The name conflict detection mechanism doesn't prevent name conflicts
when previously partitioned segments are connected by a bridge.  In
order to minimize the chance of conflicts in such a situation, it
is recommended that steps be taken to ensure hostname uniqueness. For
example, the hostname could be chosen randomly from a large pool of
potential names,  or the hostname could be assigned via a process
designed to guarantee uniqueness."

In Section 4.1, delete:

"Host myhost will then send the first responder's response to the second
responder, who will attempt to verify the uniqueness of host RR for its
name, but will not discover a conflict, since the conflicting host
resides on a different link.  Therefore it will continue using its name."

------------------------------------------------------------------------
Issue 39: Name conflict detection algorithm
Submitter: Bernard Aboba
Submitter email address: [email-masked]
Date first submitted: May 12, 2003
Reference:
Document: LLMNR-18
Comment type: T
Priority: S
Section: 4
Rationale/Explanation of issue:

It isn't clear to me that the name conflict detection mechanism
defined in Section 4 makes sense. Here is what it says:

"The name conflict detection mechanism doesn't prevent name
conflicts when previously partitioned segments are connected by a
bridge. In such a situation, name conflicts are detected when a sender
receives more than one response to its LLMNR multicast query.
In this case, the sender sends the first response that it received to all
responders that responded to this query except the first one, using UDP
unicast. A host
that receives a query response containing a UNIQUE resource record that it
owns, even if it didn't send such a query, MUST verify that no other
host within the LLMNR scope is authoritative for the same name, using
the mechanism described above. Based on the result, the host detects
whether there is a name conflict and acts accordingly."

I don't like the idea of sending unsolicited UDP responses. The
goal here is to enable hosts involved in a conflict to become
aware of it more quickly.

Joshua Graessley <[email-masked]>:
It seems another alternative might be to send all responses using
multicast instead of unicast. This would give hosts a chance to detect
conflicts much quicker. The same trick is used with IPv4LL and ARP. The
ARP responses are broadcast to facilitate in quicker discovery of
conflicts. The multicast responses could be used to populate a local
LLMNR cache on all hosts possibly reducing the number of queries that
must be sent.

> Wouldn't it be wasteful to send all responses to the same
> multicast group?

The response packet has to be sent. If it's sent using multicast
instead of unicast it will reach more machines but at least a packet
wouldn't be sent when it isn't needed. Sending every 30 seconds is a
precaution, in case something is wrong. If two hosts are configured to
respond differently to LLMNR requests, there is no problem until
another host actually queries for the conflicting record. If no host
ever queries for that record, what do we gain by spewing traffic every
30 seconds?

The multicast response could be used to build a cache on hosts
implementing LLMNR resolvers. This cache could be hit before a query
packet is generated on the wire, potentially eliminating additional
traffic.

[MikaL]:

I agree. There is no need to detect conflicts proactively.

If people are worried about the CPU usage (and that is certainly a valid
point), we can just leave the unicast responses as they are, but using
multicast would simplify the code.

> The multicast response could be used to build a cache on hosts
> implementing LLMNR resolvers. This cache could be hit before a query
> packet is generated on the wire, potentially eliminating additional
> traffic.

I'm not sure I'm comfortable with this one. This might make cache
poisoning a bit too easy.

Note that, for UDP unicast responses, comparing received responses to
pending queries is currently our only defence against spoofed UDP
unicast responses from off-link, since we no longer test TTL=255 for
responses.

[Erik Guttman]:

I agree that multicasting the name with the conflict would be easier
to implement (and specify correctly).

If this multicast occurs to a link local multicast group destination, it
would be hard for an attacker send it to another link. This mitigates
the security risk of caching.

I assume the host (llmnr responder) receiving these multicast
unsolicited replies can distinguish the difference between a message
sent to multicast and unicast destinations. Either a separate listener
(socket, or whatever) should be used to listen for unicast requests, to
differentiate them from multicast requests - or the 'destination
address' of the received datagram should be examined.

Erik

[Christian Huitema]:

I am afraid that there is no good solution to this problem. I don't like
the idea of multicasting all replies, as it is either wasteful or
dangerous; and I also really don't like anything that relies on periodic
broadcast by all hosts on a network, as it has obvious potential for
melt-down.

Let's expand on why multicast replies are wasteful or dangerous. There
is a proposed design in which hosts listen to all replies, even those to
queries they did not issue, and cache the response. The idea is that
multicast may be costly, but this cost would be compensated by more
extensive caching. The problem is that such design is a powerful tool
for an on-link attacker: the attacker can issue a spoofed query and then
broadcast spoofed responses, effectively polluting the caches of all
on-link hosts. In practice, a responsible host will only accept
responses to its own queries. It will ignore the other broadcast
responses. The multicast will just be wasteful.

My real issue with name conflict detection is whether it is actually
needed. Take the IETF network. Suppose that two attendees come in with
the laptops "zeus.example1.com" and "zeus.example2.net". There will be a
conflict for the unqualified name "zeus", but is that a bug that needs
be fixed? None of the two laptops is going to change its name, as that
would probably invalidate various security credentials and other
certificates. I guess we will just have to live with it.

If names are picked at random, then we can just as well pick them from a
space large enough to avoid the birthday paradox, and periodic checks
will not be particularly useful. If we assume that names are configured,
then periodic checks are not needed either. The administrator may
perform the check during the configuration procedure, or compare to a
master file kept somewhere, on a computer or a notebook. The
administrator may also at a later stage perform inventories of the
network, e.g. by listening to traffic, collecting IP addresses and
performing reverse look-ups.

In summary, I would rather rely on occasional checks triggered by an
administrative action, rather than increase the amount of broadcast on
the network.

[Eric Hall]:

Another option is to stick the client name into the request message,
perhaps using a special RR in the authority or additional-data sections.
Other clients which are monitoring the multicast channel can watch for
collisions and take whatever recovery steps are needed.

That would only increase the request size by a small percentage, and
wouldn't generate any additional messages.

[Joshua Graessley]:

> I am afraid that there is no good solution to this problem. I don't
> like the idea of multicasting all replies, as it is either wasteful or
> dangerous; and I also really don't like anything that relies on
> periodic broadcast by all hosts on a network, as it has obvious
> potential for melt-down.

We have operational experience with a wide deployment of an
implementation of something similar to LLMNR that uses multicasts for
responses to quickly detect conflicts and to implement caching. We have
received no reports of melt-downs nor have we experienced any such
problems here at Apple.

> Let's expand on why multicast replies are wasteful or dangerous. There
> is a proposed design in which hosts listen to all replies, even those
> to queries they did not issue, and cache the response. The idea is that
> multicast may be costly, but this cost would be compensated by more
> extensive caching. The problem is that such design is a powerful tool
> for an on-link attacker: the attacker can issue a spoofed query and
> then broadcast spoofed responses, effectively polluting the caches of
> all on-link hosts. In practice, a responsible host will only accept
> responses to its own queries. It will ignore the other broadcast
> responses. The multicast will just be wasteful.

A node can do the wrong thing and wreck havoc on the local network. In
the case you note, the multicast would be detected by anyone
advertising conflict data and the conflict detection would kick in.
Someone could use a unicast hardware address with a multicast IP
address to spoof a response to just one node. The network is a shared
resource, unless encryption and authentication is used, it can not be
made secure.

[Erik Guttman]:

The real question is - what is the problem? Early on in the work on
this protocol it was asserted that it would be unacceptable to allow
multiple hosts to respond to the same name. (I do not remember who
asserted this.)

If we accept it is necessary to detect and correct the situation where
more than one LLMNR responder responds authoritatively to the same
name we need either a proactive or reactive approach. But do we really
need to accept this requirement? There are for example cases where we
*want* multiple responders to answer to the same name (if the hosts
support redundant identical services, for example.)

It could be inconvenient and confusing for a user to get inconsistent
results to a request. But in this case, can't the user intervene?
The host had to have *gotten* its name somehow. If this was a manual
administrative assignment, only a similar assignment should be done
to change the name. The name may have been assigned automatically ,
by a program which attempted to assign a unique name. This same program
could periodically test to see if the name is still unique.

I argue that duplicate name detection and suppression does not need to be
part of the base LLMNR protocol.

> I don't like
> the idea of multicasting all replies, as it is either wasteful or
> dangerous; and I also really don't like anything that relies on periodic
> broadcast by all hosts on a network, as it has obvious potential for
> melt-down.

I agree both are undesirable and with your argument.

> In summary, I would rather rely on occasional checks triggered by an
> administrative action, rather than increase the amount of broadcast on
> the network.

That is basically what I am suggesting above.

--
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/>