Subject: [mobile-ip] closing issue 98: "Concatenate 0/1 before making a cookie?"

From: gabriel montenegro <[email-masked]>
Date: Fri, 04 Oct 2002 02:12:44 +0200

This is an attempt to close issue 98 ("Concatenate
0/1 before making a cookie?"):

 http://www.piuha.net/~jarkko/publications/mipv6/issues/issue98.txt

This issue refers to rev 18 of the draft:

  draft-ietf-mobileip-ipv6-18.txt

and should be fixed for the upcoming rev 19.

BACKGROUND
==========

Route optimization in MIPv6 relies on the "Return Routability"
procedure. Section 5.2.5 of the draft contains a good overview
of it.
In essence, it is initiated by the mobile node via HoTi and CoTi
messages whose main purpose is to obtain the required cookies
from the correspondent node. These are sent by the correspondent
node in its response via the HoT and CoT messages.

Currently, the home and care-of cookies are generated by the
CN as follows:

	home cookie = First64(MAC_Kcn(home address | nonce))
	care-of cookie = First64(MAC_Kcn(care-of address | nonce))

Finally, these are used to authorize the BU via this Kbu:

	Kbu = Hash(home cookie | care-of cookie)

ISSUE
=====
In rev 16 of the draft, the cookies were defined slightly
differently:

           K0 = MAC_Kcn(HoA | Nj | 0)
           K1 = MAC_Kcn(CoA | Ni | 1)

Where K0  and K1 were the home and care-of cookies, respectively.

Despite the change in notation, the only difference is the use
of the "0" and "1" (both were 32 bit integers) to distinguish between
the home and care-of cookies. This distinction was dropped in
rev 17 of the draft, when the above cookie definitions were
adopted.

The issue is: Should this cookie distinction be reintroduced?

MALICIOUS INVERSE BINDINGS
==========================

Some folks fear that without cookie distinction, an attacker
could obtain a care-of cookie and use it as a home
cookie, and viceversa. Notice that the attacker must still be
reachable at both locations in order to receive both
cookies. The issue is merely that the attacker may try to
reverse the intended roles of these cookies.
Correct use of the cookies results in the
correspondent node creating a binding entry of this form:

	"addr1" currently at "addr2"

Where "addr1" is some mobile node's home address,
and "addr2" is its current location (care-of address).

Inverting the roles of the cookies may result in the
inverse binding:

	"addr2" currently at "addr1"

CREATING MALICIOUS INVERSE BINDINGS
===================================

Let's now see if it is indeed possible. To see it clearly,
instead of home address and care-of address, we'll use
"address1" and "address2", respectively (likewise for the
cookies, nonces and nonce indices).
Cookies are defined like this:

	cookie1 = First64(MAC_Kcn(address1 | nonce))
	cookie2 = First64(MAC_Kcn(address2 | nonce))

They are used to authorize the BU via this Kbu:

	Kbu = Hash(cookie1 | cookie2)

And the BU is of the form:

               Src = address2
               Dst = correspondent
               Parameters:
               - address1
               - MAC_Kbu(address2 | correspondent node address | BU)
               - nonce_index1
               - nonce_index2
               - sequence number
               - ...

Resulting in a binding of the form:
	
	"address1" currently at "address2"

The question is: can the above cookies be used in the inverse
order?

To do so, the malicious node would simply send a BU as follows:

               Src = address1
               Dst = correspondent
               Parameters:
               - address2
               - MAC_Kbu(address1 | correspondent node address | BU)
               - nonce_index2
               - nonce_index1
               - sequence number
               - ...

Ingress filtering may potentially drop this packet due to its
unexpected source address. If the packet does not get
dropped, given that it is otherwise a valid binding update
the correspondent node will insert this "inverse" binding
entry into its table:

	"address2" currently at "address1"

Notice that if ingress filtering is in effect, the attacker has a
very straightforward way of defeating it. It can use an Alternate
Care-of Address Mobility option to issue a BU as follows:

               Src = topologically_correct_address
               Dst = correspondent
               Parameters:
               - address2
               - MAC_Kbu(address1 | correspondent node address | BU)
               - nonce_index2
               - nonce_index1
               - sequence number
               - alternate care-of address: address1
               - ...

In the above, "topologically_correct_address" could even be
"address2" (if that is where the attacker happens to be) or
any other address it may have acquired at its current point
of attachment. This makes it trivial to authorize an
"inverse" binding."

ANALYSIS
========

What risk does this represent?

Presumably, a mobile node is entitled to create a binding
entry at a correspondent node in order to redirect its
packets away from its topological "home" to its current
location. What this attack allows is for a malicious node
to create a binding entry at a correspondent node in order
to redirect packets away from a care-of address to its
home address.

This does not seem to pose a huge risk, given that the
malicious node must be able to receive packets at both
locations (address1 and address2). Furthermore,
the exact same considerations that apply to usual
bindings apply to inverse bindings as well. In particular,
even though it is possible to hijack another node's
address and issue a binding for it, the return routability
procedure is designed to reduce this risk by limiting the
lifetime of the bindings.

Nevertheless, this attack does allow a malicious node
to use the protocol in a different way than was intended.
There may be other issues we can't see right now, perhaps
as other uses of the basic binding update mechanism are
defined in the future (mobile routers, anycast resolution,
etc). Whereas it now seems equally possible to establish
either a "proper" or an "inverse" binding, future enhancements
to network security (including for example, secure
neighbor discovery) may change this. As we know, any
inequality can and probably will be used inappropriately.
Granted, these considerations are currently more of a
speculative nature.

One attack certainly made worse by these inverse bindings is
that of denial-of service by resource exhaustion. In effect,
this permits to at worst double the amount of resources consumed
at a corresponding node by binding entries.

Even though the attack currently does not seem to pose major
risks, it is trivial to launch. It seems prudent and
also consistent with what Hugo Krawczyk has called
"good cryptographic hygiene" to prevent it by
reintroducing the distinction between home and care-of
cookies. The low cost of hashing a few additional bits
is justified by the increased security. Furthermore,
instead of 32 bits, we should represent the ``0''
and ``1'' as single octets each.

The downside to creating distinct home and care-of cookies
is that the former cannot be simply reused and substituted
for the latter when returning home, as specified in
section 11.6.1:

   Note also that when returning home, the mobile node MAY
   use the home cookie and nonce index as a care-of cookie
   and nonce index.

This is fixable, however, as one can simply mandate that
for BU's of the form:

	"home address" currently at "home address"

the care-of nonce index is ignored by the correspondent
node. This is a special case in which the Kbu calculation
is done based only on the home cookie as follows:

   Kbu = Hash(home cookie)

Notice that BU's of this form are already handled as a special
case in section 9.4.1.  In this case, there is no need for a
care-of cookie and care-of nonce index. Instead, a valid home
cookie and home nonce index can be used to deregister.

Notice that concatenating 0 or 1 to produce home and
care-of cookies only prevents using them for the inverse
purpose. In particular, this does not affect reuse of
home or care-of cookies as optimizations in handling
fast-moving or multihomed mobile nodes as mentioned
at the end of section 5.2.7.

RECOMMENDATION
==============

We recommend that the cookie definitions be modified to
distinguish between home and care-of cookies.

This implies the following changes:

1. In section 5.2.5-2a (Return Routability Procedure: Home Test),
change this:

             home cookie = First64(MAC_Kcn(home address | nonce))

         Here A | B denotes the concatenation of the strings A and B,
         with the string A appearing first in the result.  First64(X)
         denotes the first 64 bits of the string X.

to this:

             home cookie = First64(MAC_Kcn(home address | nonce | 0 ))

         Here A | B | C denotes the concatenation of the strings A,
         B and C, with the string A appearing first in the result.
         The final ``0'' inside the MAC function is a single
         octet containing the hex value 0x00, and is used to
         distinguish home and care-of cookies from each other.
         First64(X) denotes the first 64 bits of the string X.

2. In section 5.2.5-2b (Return Routability Procedure: Care-of Test),
change this:

             care-of cookie = First64(MAC_Kcn(care-of address | nonce))

         The cookie is formed from the first 64 bits of the MAC result.

to this:

             care-of cookie = First64(MAC_Kcn(care-of address | nonce | 1 ))

         Here, the final ``1'' inside the MAC function is a single
         octet containing the hex value 0x01, and is used to
         distinguish home and care-of cookies from each other.
         The cookie is formed from the first 64 bits of the
         MAC result.

3. Furthermore, for BU's in which the care-of address is equal
to the home address, only the home nonce index is required.

In section 9.4.1 (CN operation: Receiving Binding Updates),
change this:

    -  If the Lifetime specified in the Binding Update is zero or the
       specified care-of address matches the home address for the
       binding, then this is a request to delete the mobile node's
       cached binding.  If the Home Registration (H) bit is set in the
       Binding Update, the Binding Update is processed according to the
       procedure specified in Section 10.4; otherwise, it is processed
       according to the procedure specified in Section 9.4.3.

to this:

    -  If (1) the Lifetime specified in the Binding Update is
       zero, or (2) the specified care-of address matches the home
       address for the binding, then this is a request to delete
       the mobile node's cached binding.  If (2), the binding
       update MUST include a valid home nonce index (the care-of
       nonce index MUST be set to zero by the mobile node and it
       MUST be ignored by the correspondent node).  In this case,
       generation of the session key depends exclusively on the
       home cookie (section 5.2.5).  If the Home Registration (H)
       bit is set in the Binding Update, the Binding Update is
       processed according to the procedure specified in Section
       10.4; otherwise, it is processed according to the procedure
       specified in Section 9.4.3.

4. In section 11.6.1 (MN operation: Sending Home and Care-of
Test Init Messages):

Change this:

   Note also that when returning home, the mobile node MAY
   use the home cookie and nonce index as a care-of cookie and nonce
   index.

To this:

   Note also that when returning home, if the mobile node sets
   the care-of address in the binding update equal to its home
   address, it MAY use the home cookie and nonce index by itself
   (without a care-of cookie and nonce index).  In this case,
   generation of the session key depends exclusively on the
   home cookie (section 5.2.5).

5. In section 11.7.2 (MN operation: Correspondent Binding Procedure):

Change this:

   If, instead, the care-of address is set to the mobile node's home
   address and the Lifetime field set to zero, the Binding Update
   requests the correspondent node to delete any existing Binding Cache
   entry that it has for the mobile node.

To this:

   If, instead, the care-of address is set to the mobile node's
   home address, the Lifetime field set to zero and the care-of
   nonce index set to zero, the Binding Update requests the
   correspondent node to delete any existing Binding Cache entry
   that it has for the mobile node.  In this case,
   generation of the session key depends exclusively on the
   home cookie (section 5.2.5).

6. In section 6.1.7 (Binding Update (BU) Message):

Change this:

   The deletion of a binding can be indicated by setting the Lifetime
   field to 0 or by setting the care-of address equal to the home
   address.

To this:

   The deletion of a binding can be indicated by (1) setting the Lifetime
   field to 0, or (2) by setting the care-of address equal to the home
   address and the care-of nonce index to zero. For case (2),
   generation of the session key depends exclusively on the
   home cookie (section 5.2.5).

7. In section 5.2.5-2b (Return Routability Procedure: Care-of Test),
change this:

    Kbu = Hash(home cookie | care-of cookie)

To this:

    Kbu = Hash(home cookie | care-of cookie)

   A Binding Update may also be used to delete a previously
   established binding by setting the care-of address equal
   to the home address (section 6.1.7). In this case, the
   care-of cookie is not used. Instead, the session key
   is generated as follows:

    Kbu = Hash(home cookie)

--------------------------------------------------------------------------
-gabriel

---

From: Pekka Nikander <[email-masked]>
Date: Fri, 04 Oct 2002 08:20:05 +0300

>  http://www.piuha.net/~jarkko/publications/mipv6/issues/issue98.txt
...
> RECOMMENDATION

I strongly agree with Gabriel.

--Pekka

---

From: Vladislav Yasevich <[email-masked]>
Date: Fri, 04 Oct 2002 10:53:47 -0400

Gabriel

> RECOMMENDATION

Great analisys; however, it seems to hinge on the point that
the attacker must be able to get to the HomeAgent<->Correspondent
link.  Since we know that RR doesn't protect us when attacker
is on that link, this change doesn't seem all that worthwile
to me.  That attacker will be able to hijack a binding and
cause denial of service even with the proposed revision.

I also have some issues with the proposed text updates, but I'll
save those comments until there is concesus of whether to adopt
the text or not.

-vlad

-- 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Vladislav Yasevich		Tru64 UNIX - IPv6 Project Lead
Hewlett Packard 		Tel: (603) 884-1079
Nashua, NH 03062		ZKO3-3/T07

---

From: Jari Arkko <[email-masked]>
Date: Sat, 05 Oct 2002 08:53:29 +0300

> cause denial of service even with the proposed revision.

It is true that the attacker must have access to this path
for him to be able to cause any trouble related to swapping
the cookies. It is also true that attackers who are on this
path will be able to do much greater damage in any case.

However, the main argument for the change is that folks can
sleep better knowing that we have followed "good cryptographic
hygiene" (and that the change does not cost prevent the
optimizations dear to us). And as has been noted, we don't
know how future changes in extensions to mobility or
advances in other parts of IPv6 will affect our designs.
Better safe than sorry...

 > save those comments until there is concesus of whether to adopt

Please do post them.

Jari

---

From: Vladislav Yasevich <[email-masked]>
Date: Mon, 07 Oct 2002 11:51:40 -0400

>  > save those comments until there is concesus of whether to adopt

All right, I'll go along with the 0/1 concatenation.

Below are some comments on the proposed text itself.

>        specified in Section 9.4.3.

This change and some of the subsequent text leads to some special
handling of the "care-of nonce index == 0".  Depending on the
implementation, 0 (zero) may be a perflectly valid nonce index.

I belive that simply requiring the the CN to ignore the care-of
index when CoA == HoA is a more neuteral way of doing this (essentially
remove the "the care-of nonce index MUST be set to zero by the mobile node")

This leads to keeping the conditional in Section 11.7.2 the same as
before only adding reference text on how the Kbu is generated.

Also, the does not introduce any additional failure checkpoing conditions
that are not currently covered in the proposed text.  For example,

>    home cookie (section 5.2.5).

What happens if the care-of nonce index is NOT zero?

-vlad

---

From: gabriel montenegro <[email-masked]>
Date: Mon, 07 Oct 2002 18:29:13 +0200

> implementation, 0 (zero) may be a perflectly valid nonce index.

Yes, it does remain a perfectly valid index.

> remove the "the care-of nonce index MUST be set to zero by the mobile 

Notice that this only relates to when CoA == HoA. Otherwise, the
index==0 still remains valid. I agree that the current wording
may mislead some folks into thinking that 0 is not a valid value.
But, if we don't say what to set it to in this case, some one will
ask. How about modifying that (2) clause to say something like:

         If (2), the binding
         update MUST include a valid home nonce index (the care-of
         nonce index MUST be ignored by the correspondent node
	and SHOULD be set to zero by the mobile node).

> before only adding reference text on how the Kbu is generated.

Condition would still remain unchanged, yes.

> What happens if the care-of nonce index is NOT zero?

Good point, one less thing to check.

tnx,

-gabriel

---

From: Vladislav Yasevich <[email-masked]>
Date: Mon, 07 Oct 2002 14:39:15 -0400

Gabrial

>     and SHOULD be set to zero by the mobile node).

I am OK with a should.  I was actually thinking that if the mobile
node doesn't to special code this, they can just set the index
to whatever they thing the care-of idex is at the time (i.e normal
construction of BU).  The only special code then resides in the
construction of the key.

> -gabriel

Later
-vlad

---

From: gabriel montenegro <[email-masked]>
Date: Mon, 07 Oct 2002 23:07:33 +0200

Vladislav Yasevich wrote:
> I am OK with a should.  

Cool.

> I was actually thinking that if the mobile

We agree, I'm just trying to be "conservative in
what you send".

As for special code, this *is* a special case already.

-gabriel

---

From: Joe Lau <[email-masked]>
Date: Mon, 7 Oct 2002 15:35:38 -0700 (PDT)

When the H-flag is set in the Modified Router Advertisement Message,
can we have a router advertisement such that one Prefix Information Option
has the R-flag set while the other Prefix Information Options have the
R-flag not set (assuming that the there are multiple prefixes on the
advertisement)?  Is this allowed by the MIPv6 draft?  It is not clear
by just reading the text.

Joe Lau