Subject: Reason for the explicit link-layer address options in ND?

From: Pekka Nikander <[email-masked]>
Date: Wed, 12 Feb 2003 15:43:21 +0200

On the behalf of the SEND DT, I'd like to get
a clarification to the current ND design from
those who were around back when RFC2461 and
RFC2462 were written.

Specifically, we'd like the know the exact
reasons why RFC2461 uses separate source/target link
layer address options instead of relying on the
actual source link layer addresses used in the
link layer frame?  Furthermore, why are the actual
link layer addresses used in the link layer frame
completely ignored, and not checked to match with
the options?

Is this just a layering question, an attempt to
avoid layer violations?  Or were there behind
other goals, like allowing proxy ND?

The reason why I am asking this is that the current
situation makes security design tricky.  That is,
the Secure ND part of SEND (as opposed to Secure RD)
is all about creating a secure binding between an IP
address and a link layer address.

The WG decided to pursue the idea of using public
key based AH to secure the NA (and NS) messages.
That requires that the hosts learn the public keys
of the other hosts on the local link.  Basically,
there are two know methods for distributing the
public keys:  Using certificates and relying on
a (local) CA, or using Cryptographically Generated
Addresses (CGA).

Now, for zero-config operation, we would like to
use the CGA ideas.  Furthermore, there is a possible
attack against link local addresses, and that attack
can be partially dwarfed if we bind both the link
layer address and the public key to the IP address
in CGA.

Under the current design, the CGA processing at the
AH layer becomes very tricky, if we attempt to include
the link layer address into the CGA process.

--Pekka Nikander

--------------------------------------------------------------------
To unsubscribe from this list, send email with "UNSUBSCRIBE" in the
body to <[email-masked]>.
Archive: http://standards.ericsson.net/lists/ietf-send/maillist.html
--------------------------------------------------------------------

---

From: Francis Dupont <[email-masked]>
Date: Wed, 12 Feb 2003 15:58:18 +0100

In your previous mail you wrote:

=> both reasons. In the same kind of design ideas, it is
forbidden to mix unicast and multicast between layers, i.e.,
if the IPv6 destination is unicast, the link-layer destination
MUST be unicast, and same with multicast in place of unicast.

=> this problem is the same than creating a secure binding
between a DNS name and an IP address (i.e., the DNSSEC one).

=> I stronly disagree: CGAs are very different: they
don't provide authentication, only ownership.
And there is a third way, Key-Based Addresses (KBA),
i.e., the opposite of CGAs.

   
=> I don't understand your problem: with public keys you
can sign NAs so secure the IPv6 to link-layer address binding.
To secure the reverse binding we can reuse inverse ND (RFC 3122).
So the only issue (:-) is the public key distribution...

Regards

[email-masked]

---

From: "Fred L. Templin" <[email-masked]>
Date: Wed, 12 Feb 2003 09:56:09 -0800

> MUST be unicast, and same with multicast in place of unicast.

Can you point me to the text that forbids this? I was under the
impression that multicast emulation mechanisms (e.g. MARS, etc.)
use unicast link-layer destination addresses when the IPv6
destination is multicast. The whole point of multicast
emulation is to propagate network-layer multicasts over
unicast-only link layers - not true?

Thanks,

Fred
[email-masked]

---

From: "Tony Hain" <[email-masked]>
Date: Wed, 12 Feb 2003 13:45:02 -0800

There is an explicit unjustified one-liner in 1812 (pg 34):
A router MUST not believe any ARP reply that claims that the Link
Layer address of another host or router is a broadcast or multicast
address.

While it is clearly the intent of the security do-gooders to avoid arp
cache pollution as a dos tool, there is a vast difference between
'SHOULD NOT do this without explicit intent', and 'MUST NOT do this'. As
you point out there are cases where multicast over unicast makes sense,
and there are cases where IP-anycast over multicast link layer make
sense for load sharing. Unfortunately, the line above ends up as the
basis for declarations that the types have to match.

Tony

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Fred L. Templin
> Sent: Wednesday, February 12, 2003 9:56 AM
> To: Francis Dupont
> Cc: Pekka Nikander; IPV6 WG; SEND WG
> Subject: Re: Reason for the explicit link-layer address options in ND?
> 
> 
> Francis Dupont wrote:
> forbidden to 
> > mix unicast and multicast between layers, i.e., if the IPv6 
> > destination is unicast, the link-layer destination MUST be unicast, 
> > and same with multicast in place of unicast.
> 
> Can you point me to the text that forbids this? I was under 
> the impression that multicast emulation mechanisms (e.g. 
> MARS, etc.) use unicast link-layer destination addresses when 
> the IPv6 destination is multicast. The whole point of 
> multicast emulation is to propagate network-layer multicasts 
> over unicast-only link layers - not true?
> 
> Thanks,
> 
> Fred
> [email-masked]
> 
> IETF IPng Working Group Mailing List
> IPng Home Page:                      http://playground.sun.com/ipng
> FTP archive:                      ftp://playground.sun.com/pub/ipng
> Direct all administrative requests to [email-masked]

---

From: Pekka Nikander <[email-masked]>
Date: Thu, 13 Feb 2003 13:18:18 +0200

Francis,

[I've removed IPV6 WG from CC since this discussion
  belongs to SEND, IMHO.]

> i.e., the opposite of CGAs.

Sorry about forgetting ABK/KBA; they require some sort
of a central agency, so I tempt to classify them with
the cert/CA based solution.  Anyway, it should be
mentioned for completeness.  Thanks for the correction.

Now, what comes to the difference between CGA and certs,
there is indeed a difference, but it is more subtle than
what you seem to imply.

   - When certificates are used, the nodes trust on
     an external party (the local CA) to tell what
     nodes are trustworthy and what nodes are not.
     Furthermore, iff the certificates contain an
     IP address, the certificates also provide authorization
     over IP address usage.  Likewise, iff the certificates
     contain a link layer address, they provide authorization
     over ll address usage.  But, of course, usually the
     certificates do not contain either, for obvious
     practical reasons.

   - When CGA is used, the nodes do not trust on any
     external party but rely on the computational
     difficulty of creating another set of <public key,
     IP address, (link layer address)> that matches with
     a given set.

In both cases the goal is to have a reasonable bases
to believe that a given <IP address, link layer address>
mapping is valid.  In the first case, the resulting
belief is based on trust on the local CA and possibly
also on trust on the nodes.  In the second case, the
resulting belief is based on assumptions on computational
complexity.

> So the only issue (:-) is the public key distribution...

Signing the NA is certainly enough if you have a resonable
bases to rely on the honesty and competence of the key
holder.  If you are using certificates, you may have.
However, if you are using CGA, you don't.  You just have
some unknown party having a public key and claiming a
binding between an IP address and link layer address.

Now, since creating a suitable key that matches a given
IP address is a hard problem in CGA, it *may* be enough
to just sign the NA, and rely on the signature for the
link layer address.  Personally, I tend to believe that
it is currently secure enough for global addresses, since
in that case the CGA input includes the routing prefix.
Furthermore, including the link layer address into the
CGA input parameters would be bad for privacy.

However, the situation is different for link layer
addresses.  Firstly, there are no privacy problem since
the link layer addresses are visible at the local link
anyway.  Secondly, we *do* have a (slight) security problem
since the link local routing prefix is always the same.
Consequently, there appears to be an almost practical
precomputation attack where an attacker creates a table
of precomputed <public key, link local address> pairs.
The amount of memory needed for such a table is fairly
large today (in the order of 2^66..2^72 bytes), but the
attack is clearly becoming feasible within the next 20
years.

Thus, one possible way of defeating the link local
pre-computed table attack is to include the link layer
address into the CGA input parameters.  That would force
the attacker to use a pre-determined link layer address,
thereby reducing the attractivity of the attack.

It should be noted that including the link layer address
into the CGA input parameters does not completely stop
the pre-computation attack, since in an attack situation
the recipient would receive two different but valid NAs:
one would be sent by the actual node, and the other one
from the pre-computed table.  Without any other prior
knowledge, the recipient would not be able to make a
difference between these two, thereby creating confusion
between which node is the right one.  In practise, however,
it might be easier to isolate the attacker since it would
be forced to use the pre-determined link layer address(es).

Does this matter?  I don't know.  We are still discussing
this in the DT.  Opinions from the WG are very welcome.

--Pekka Nikander

---

From: Francis Dupont <[email-masked]>
Date: Thu, 13 Feb 2003 18:15:17 +0100

> MUST be unicast, and same with multicast in place of unicast.
   
   Can you point me to the text that forbids this?

=> RFC 1122 3.3.6 but I recognize this needs to be clarify
for IPv6.

   I was under the
   impression that multicast emulation mechanisms (e.g. MARS, etc.)
   use unicast link-layer destination addresses when the IPv6
   destination is multicast.

=> in the case of MARS for ATM there is no real link-layer addresses
for the point-to-multipoint virtual circuits. Even if MCS are used
in fact we can argue the link-layer address is a set of addresses
with possible indirection.

   The whole point of multicast emulation is to propagate
   network-layer multicasts over unicast-only link layers - not true?
   
=> yes but the special mark for link-layer broadcast/multicast packets
is still needed.

Regards

PS: the exact quote is (see also TCP/IP illustrated V2 page 1101):

         When a host sends a datagram to a link-layer broadcast address,
         the IP destination address MUST be a legal IP broadcast or IP
         multicast address.

         A host SHOULD silently discard a datagram that is received via
         a link-layer broadcast (see Section 2.4) but does not specify
         an IP multicast or broadcast destination address.
--------------------------------------------------------------------
To unsubscribe from this list, send email with "UNSUBSCRIBE" in the
body to <[email-masked]>.
Archive: http://standards.ericsson.net/lists/ietf-send/maillist.html
--------------------------------------------------------------------

---

From: Julien Laganier <[email-masked]>
Date: Fri, 14 Feb 2003 15:04:47 +0100

Hi Pekka,

What you wrote below triggered some questions in my mind. 

I must admit that I am not sure that I've caught well all implications...
My questions are included in the text. 

I am also wondering if another scheme (gabriel and I called it CLE) 
would permit to reduce as well the easyness of precomputation attacks.
WG's inputs on CLE are welcomed.

> thereby reducing the attractivity of the attack.

Alice has a (link-local) IP addr L and (MAC) link-layer addr a,
where Pekka's assuming a is predetermined (perhaps by IEEE EUI info):

	(1) L = h(PK,a)

The goal of the NA is convincing folks to cache the mapping

	(2) link-local IP addr L @ link-layer a

So presumably you would only enter (2) into your cache if you were 
able to verify (1).

An attacker not using link-layer addr a would not be able to do this
as easily as if (1) were simply L=h(PK).

> be forced to use the pre-determined link layer address(es).

Yes, so an attacker can persevere in usurping link-layer address
a by doing this:

    (3) L' = h(PK', a)

and using that to send an NA:

    (4) link-local IP addr L' @ link-layer a

Since (2) and (4) are equally consistent, you as a recipient wouldn't
know which to believe, but at least forcing the attacker to use "a"
makes it more traceable.

Another way to reduce precomputed attacks could be to define the link layer
address as a CGA as well, using as input the same PK that the one used to
generate the link local IP address. Thus, both IP and LL addresses are bound
to a given PK. We've called that Cryptographic Layering Enforcement (CLE):

     (7)  L = h_top(PK), a = h_bottom(PK)

With an NA producing a mapping as in (2) verifiable as per the above.
With (4) you're fixing only one element (either L or a), whereas in (7) we're
fixing both elements. If an attacker wishes to produce a valid mapping 
with (7) using bogus PK', it has two events to reproduce:

	(8) P(a) = probability that he'll find a collision
	 	with PK' such that a = h_bottom(PK')

	(9) P(L) = probability that he'll find a collision
	 	with PK' such that L = h_top(PK')

In CLE, our assumption is that (8) and (9) are indeed independent
events. Someone who knows about hash functions can tell us better...

Assuming they're independent events, then the probability of
finding a valid (7) is then:

	(10) P(a&L) = P(a)P(L)

So we've made the attacker's task much much harder.
Furthermore, if we then define another application of CLE,
like for example, Mobile IP, we could define the care-of
address:

	(11) C = h_middle(PK)

and the objective of the binding update is to establish the mapping:

	(12) L  @ C

(Where L should be replaced by "G" a global-unicast address.)
Then the probability of establishing such a mapping for an attacker
using trial and error is:

	(13) P(L&C) = P(L)P(C)

and we've made the task much harder. We could even think that for an
attack to succeed completely, the attacker would have to beat the
following odds:

	(14) P(a&L&C) = P(a)P(L)P(C)

Assuming the hash function in question produces bottom, middle and
top bits independently of each other, we're making the task even
harder. True, such a mapping as (13) is really 2 mappings produced
by NA and BU, and both may not be available to most observers, but
if at least some systems see this, they can detect and signal
fishiness.

Nevertheless, current implementations of either (10) or (13) can be
considered secure.

Also, quoting RFC 2373, IP Version 6 Addressing Architecture :

--->"
  |   10     |
  |  bits    |        54 bits          |          64 bits           |
  +----------+-------------------------+----------------------------+
  |1111111010|           0             |       interface ID         |
  +----------+-------------------------+----------------------------+
"<--

I am wondering if making a CGA link local address by concatenating a 
reduced link-local prefix (fe80) with 118 bits extracted from the secure
hash output would make sense? That would certainly reduce the easyness
of PK-jar attacks... But it's not currently allowed by [ADDRARCH] where all 
54 bits between IID and LL prefix are set to zero.

Thanks,

--julien

---

From: "James Kempf" <[email-masked]>
Date: Fri, 14 Feb 2003 08:46:19 -0800

Making the link layer address a CGA too makes sense, but is not always possible.
I don't think it would be for ATM for example.

Regarding using 118 bits, the latest v6 AddrArch document is fairly strict about
the 64 bit boundary for global unicast, though the current wording doesn't make
it a requirement. I've actually thought about this too, but more along the lines
of having the router use a hash of the fqdn for the domain or its own fqdn as a
way to tie the identifier for a X.509 certificate to an address without putting
the address in the certificate.

        jak

----- Original Message -----
From: "Julien Laganier" <[email-masked]>
To: "Pekka Nikander" <[email-masked]>
Cc: <[email-masked]>; "SEND WG" <[email-masked]>
Sent: Friday, February 14, 2003 6:04 AM
Subject: Notes about CGA in SEND (was Re: Reason for the explicit link-layer
address options in ND?)