Subject: Re: [mobile-ip] RFC3012-bis: compatibility issues

From: Charlie Perkins <[email-masked]>
Date: Wed, 03 Apr 2002 14:39:40 -0800

Hello Luca,

I wonder why it is more expensive for multicast advertisements
than for unicast.

For each challenge used by a mobile node (multicast or not),
the foreign agent needs to keep track of the mobile node's IP
address and that challenge value.  What is different?  If  a
mobile node erroneously tries to re-use a value that is still
being multicast, then it would be rejected, right?

Regards,
Charlie P.

Luca Salgarelli wrote:

> Hi.
>
> I was wondering if anybody, e.g. at the last Connectathon, came across
> the following.
>
> How would a Mobile-IP client react if a FA:
>
> - did NOT include challenges in broadcast agent advertisements AND
> - did include challenges in unicast agent advertisements AND
> - did include challenges in every registration reply.
>
> The reason I am asking this is that it seems to me very computationally
> expensive at the FA to keep track of which client already used a
> challenge included in a multicast advertisement. This is even more true
> if the challenge window is more than 1.
>
> Including challenges only in unicast advertisements and registration
> replies would make the protocol much lighter to implement.
>
> Any thoughts?
>
> Thanks
> Luca

---

From: Luca Salgarelli <[email-masked]>
Date: 03 Apr 2002 18:39:40 -0500

Hello Charlie.

> being multicast, then it would be rejected, right?

Right. But then the question is: does the FA have to keep the list of
used challenges for every client for the entire duration of their
session, and check against that list every registration request? I hope
not, right?

If not, then how does the FA decide which challenge to delete and when
from the per-client "used challenges list"? Unless I am missing
something, this is the (very) expensive part of the procedure.

If instead the FA sent challenges only in reg. replies and in unicast
advertisements, then the check becomes very simple: a challenge from a
client is valid only if it was either in the last unicast advertisement
or in the last reg. reply. Implementation becomes trivial: the FA just
has to keep two fields per client with the last two challenges issued to
that client.

Does this make sense?

Luca

---

From: Luca Salgarelli <[email-masked]>
Date: 03 Apr 2002 16:22:33 -0500

Hi.

Any thoughts?

Thanks
Luca

---

From: Luca Salgarelli <[email-masked]>
Date: 04 Apr 2002 11:20:08 -0500

> something, this is the (very) expensive part of the procedure.

This is true with challenge windows larger than 1.

Luca

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 04 Apr 2002 08:56:26 -0800

Hello Luca,

Actually, I'm not so sure about the best way to answer your
question.  It is a good point.

My original conception of this operation was that the foreign
agent would have a _short_ list of recent acceptable challenges.
That is easily checked when a mobile node sends a Registration
Request.  The challenges would be advertised, and available for
use by multiple mobile nodes.

Now it is also possible to have the challenge supplied as part
of the Registration Reply, which is a good idea, but not "like"
the other Challenges because a long time might pass before the
challenge gets used.

My guess is that the foreign agent now has to check in two
places about the challenge for the mobile node.  The challenge
that was delivered with the Registration Reply would have to
be stored per-mobile.  That is not all that expensive.  The
other short list is not expensive.  Together, I don't think
they are all that expensive to maintain, even if the window
size is greater than 1.  Maybe the per-mobile challenge gets
stored along with the other information in the visitor list.
Perhaps the "window" size for per-mobile challenges is always
implicitly 1, in contrast to the other generally advertised
challenge values.

What do you think about this?

Regards,
Charlie P.

---

From: Luca Salgarelli <[email-masked]>
Date: 04 Apr 2002 12:38:08 -0500

Hello Charlie.

> use by multiple mobile nodes.

I think there is more to it than it appears.

The spec says, rightfully, that the FA should make sure to check that a
mobile does not reuse a previously used challenge. And this is the
sticky point. To satisfy it, it is not enough for the FA to maintain a
global list of "valid advertised challenges" only. It has to keep:

1) A global windowed list of valid advertised challenges
2) A per-mobile list of the last challenge sent in a reply

as you say, but also:

3) A *per-mobile* list of recently used challenges from (1)

Now, (1) is not a problem because it should be short. Same for (2)
because it is always composed of one entry only -- as you suggested, I
agree that the window of the challenges sent in replies should always be
'1'.

I have problems with (3), if the window is larger than one. As the
mobile uses challenges from advertisements, we have to add them to (3).
But we don't want (3) to grow indefinitely, so we want to delete the
ones that were already there and that we don't possibly need anymore. 

To select the ones that can be safely deleted, we would have to check
them against the current values in (1), and delete from (3) the ones
that are not present in (1). But this operation starts to become
increasingly expensive, even for windows of two or three. 

Furthermore, we will probably also have to keep (3) alive even after the
mobile de-registers, to make sure that an attacker does not replay a
request that used one of the still valid challenges values that this
mobile recently used (and that therefore is in (3)).

Now, it could be that there is another less expensive (and less complex
to explain!) way of having challenges sent with multicast
advertisements, a challenge-window greater than 1, and satisfy the
requirement of making sure that a challenge has not been already used by
a mobile. 

But I really cannot think of another one different than the above.

What do you think?

Luca

---

From: Gerald Maguire <[email-masked]>
Date: Thu, 4 Apr 2002 20:02:18 +0200 (MET DST)

But the elements of list (3) don't have to be retained longer than the
time period when these challenges are valid. Thus when a given
challenge is removed from (1) it can be removed from all lists of type
(3) {if the resulting list is empty, then the mobile is well and
truely gone, so the list can be removed altogether.}

Of course by actually just extending the element of list (1) to
include a list indicating which mobile(s) has(have) used this
particular challenge - then you don't even have to search during the
delete operation - you remove the challenge element (1) and all of
records of the mobiles which have used this challenge. Since this
challenge is now invalid, there is no reason to keep it or any records
of who used it; as clearly _any_ use of this challenge is invalid.

Chip

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 04 Apr 2002 10:19:48 -0800

HI Chip,

> truely gone, so the list can be removed altogether.}

I don't remember any such time period.  The Challenge Window is
purely based on the number of distinct Challenges offered, and not
on when they were offered.  Plus, it *might* be considered useful
that the mobile node can always have a usable challenge available
to it, without delay, even if the challenge was offered at some
much earlier point in the past -- as long as it was never used.

If you think there should be some time limit after which a
Challenge can no longer be used, then that is something more
which isn't in the current specification -- and which would
need to go through working group call again, at least according
to my understanding.  Or else, if it's already in there, then
I guess I just missed it (not to mention forgot about putting
it there in the first place!) -- but I don't think it's there.

Regards,
Charlie P.

---

From: Gerald Maguire <[email-masked]>
Date: Thu, 4 Apr 2002 20:36:38 +0200 (MET DST)

I don't suggest that the challenge window element necessarily has to
be removed based on time, but there must be some reason you remove
them (otherwise it would not be a Window).

At the point that you remove the challenge from the list of valid 
challenges (i.e., this challenges now falls outside the  Challenge
Window), then this challenge is no longer valid for anyone to use.
Hence the record of anyone having used it is no longer relevant,
because no one can use this challenge. Since there can be no problems
due to a replay - since the challenge is invalid, there is no need to
store any information concerning who has or has not used this challenge.

Chip

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 04 Apr 2002 10:48:09 -0800

Hello again Chip,

> them (otherwise it would not be a Window).

It's called a window because it looks like a sliding window
over the sequence of challenges, and leaves only the last N
visible.  Isn't that still a valid use of the terminology,
irrespective of any time dimension?

> store any information concerning who has or has not used this challenge.

I don't disagree with your statements, but I also don't think that
having the mobile node use a Challenge from its last Registration
Request introduces any replay vulnerability.

Regards,
Charlie P.

---

From: Luca Salgarelli <[email-masked]>
Date: 04 Apr 2002 14:15:15 -0500

Charlie,

please see comments inline.

On Thu, 2002-04-04 at 12:46, Charles E. Perkins wrote:
> What if we say that, if a mobile node uses a challenge from (1), that
> challenge _replaces_ the challenge (if any) from (3).  Thus, this
> "invalidates" the option to use any challenge that was supplied from
> a Registration Request.
> 
> I don't think this would impose any hardship, and it would seemingly
> eliminate the problem that you have identified.

Hmmm, I am not sure you could do that. Let's analyze: (3) contains a
list of challenges successfully used by a client in the recent past.
(3), along with (1) and (2), are kept by the FA so that it can run the
following checks when it receives a challenge C in a registration
request:

1: if (C is not in (1)) and (C is not in (2))
2:    return UNKNOWN_CHALLENGE
3: else
4:    if (C is in (3))
5:        return STALE_CHALLENGE
6: else
7:    add C to (3)
8:    proceed with processing of registration request

Now, if I understand your suggestion correctly, you are saying that the
FA at line 7 should replace the challenge C' (if any) that is already in
(3).

But this wouldn't work: if the window is larger than one, a malicious
mobile could now replay the older request that contained C', and the FA
would let it through.

Am I misintrepreting your suggestion?

Luca

Charlie also wrote:
> After deregistration, from the above, this would not impose very much
> additional hardship.  In fact, even when there is nothing from (3),
> the foreign agent should keep this information around.
> 
> Regards,
> Charlie P.

---

From: Luca Salgarelli <[email-masked]>
Date: 04 Apr 2002 14:19:22 -0500

Hello Chip.

> truely gone, so the list can be removed altogether.}

This would definitely have scalability problems: now the FA every time
it modifies the list of valid challenges, it has to go through the whole
list of visitors to modify (3). Also:

> records of the mobiles which have used this challenge. 

I think that this could also lead to scalability problems: now the FA
when it has to check for the validity of a challenge, it has to go
through a [potentially long] list of mobile nodes to check against.

Luca

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 04 Apr 2002 11:42:57 -0800

>>> 3) A *per-mobile* list of recently used challenges from (1)

I think I said the wrong thing.  What if, when a mobile node uses
a challenge from (1), it causes (2) to be nullified.  Thus, if a
mobile node uses one of the advertised challenges, it loses the option
of (ever) using the challenge from a Registration Reply.

Is this better?

Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 04 Apr 2002 11:48:39 -0800

Hello again,

One further clarification:

If a mobile node uses an advertised challenge, it loses the option
of ever using the last challenge from a Registration Reply, but not
the option of using future such challenges.

The latter additional restriction could have been a possible
interpretation of my suggestion in the text below.

Regards,
Charlie P.

---

From: Luca Salgarelli <[email-masked]>
Date: 04 Apr 2002 14:51:28 -0500

> of (ever) using the challenge from a Registration Reply.

Unfortunately, probably not. The problem is not the relationship between
(1) and (2). The problem is keeping track of which mobile used which
challenge *from the list of challenges sent in broadcast
advertisements*.

To repeat, the way (1), (2) and (3) should be used (in my opinion) is
the following:

So, in light of this, I don't think your suggestion would work.

If we want to abstract it, the problem is caused by the fact that
broadcast challenges are seen by all mobiles, but the check on who used
them must be done on a per-mobile basis. I am sure protocol theorists
could formalize the problem much better than I do.

Luca

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 04 Apr 2002 12:17:41 -0800

Hello again Luca,

I am not totally sure I see the problem, but one improvement
would be to reduce the amount of searching and list management.
So, we could say that:

- If mobile uses an advertised challenge, it can no longer use
  the Reply challenge, nor any previously advertised challenge.

- The foreign agent has to remember the last challenge used
  by the mobile node, and an ordered list of recently advertised
  challenges.

> 2:    return UNKNOWN_CHALLENGE

/* so far, no problems, right...? */

> 4:    if (C is in (3))

/* Here, maybe if (C "not-later-than" "last-challenge") */

> 5:        return STALE_CHALLENGE

/* Here, maybe C <-- "last-challenge"; (assignment) */

Is this better?

Regards,
Charlie P.

---

From: Erik Anderlind <[email-masked]>
Date: Thu, 04 Apr 2002 16:48:14 -0500

Hi Luca,
Why don't you just maintain a time stamped list of when 
FA changed advertisment. Same advertisement used for all 
mobiles. If there is a mobile request, check the global list 
which chalenge to use.
In practice would only need to store a couple of values.
...Erik

---

From: Luca Salgarelli <[email-masked]>
Date: 04 Apr 2002 17:55:16 -0500

Hello Charlie.

>   the Reply challenge, nor any previously advertised challenge.

I think that even a subset of this would at least limit the scalability
problems: 

- If a mobile uses an advertised challenge, it can no longer use
  any previously advertised challenges.

I think the addition of the following text at the end of the last
paragraph on page 5 of draft-ietf-mobileip-rfc3012bis-01 should reflect
this:

   The Foreign Agent MUST NOT accept any Challenge in the Registration
   Request unless it was offered in last Registration Reply issued
   to the Mobile Node, or else advertised as one of the last
   CHALLENGE_WINDOW (see section 9) Challenge values inserted into the
   immediately preceding Agent advertisements.  If the Challenge is
   not one of the recently advertised values, the foreign Agent SHOULD
   send a Registration Reply with Code value UNKNOWN_CHALLENGE (see
   section 10).  <NEW TEXT> In addition, if the Challenge is one of 
   the recently advertised values, but was issued before a Challenge
   already used by the Mobile Node, the Foreign Agent SHOULD send a 
   Registration Reply with code value STALE_CHALLENGE. </NEW TEXT>

What do you think?

Thanks
Luca

---

From: Charlie Perkins <[email-masked]>
Date: Thu, 04 Apr 2002 15:03:24 -0800

Hello Luca,

This is fine with me.  If there are no other objections, I'll put it into
the soon-to-be reissued RFC3012bis.

Regards,
Charlie P.