Subject: RE: [SeaMoby] Topic #3: Cache contamination

From: [email-masked]
Date: Thu, 13 Mar 2003 18:43:38 -0500

> I'm not sure I understand the attack.
> 
> If an attacker sends a completely bogus AP, the AR compares 
> against the AAPL
> (Authorized AP List) and rejects. 
> If an attacker sends an AP that is not bogus but is not a 
> GAAP, then it will
> pass the AAPL test but it will remain in the cache for one 
> iteration and be
> flushed aftewards.
[Govind] This is assuming a particular cache replacement policy and assumes
the server approach. I think we should first settle whether the server is needed
or not before coming to cache contamination and other cache related issues. 
However, if we are not going to do that, then we should propose how any
scheme involving protecting the cache works in either of the proposed solutions.
> 
> So, I don't see how interrouter capability and update 
> exchange are affected.
[Govind]  First thoughts about this cache replacement policy. I will think about this replacement
policy more later.. Its been a long day already, so sorry if I'm wrong :)

If the number of malicious MNs increase, then wouldn't you have an increase of the number
of entries? Also, they might not be removed from the cache. More such entries and more
the unnecessary capability messages. Note, if we are using the server scheme, each MN has
the possibility of reporting a large number of such non-GAAPs. Consider this scenario,
10 malicious MNs each report say 100 genuine non-GAAPs. Also assume that
each AP is assigned to a different AR. Further assume that
you have a limit of 100 reports per MN.  In your scheme, the chance
of it being not removed is (1-1/10)  = 0.9. There is a 90% chance that 100 cache entries of
non GAARs are in the cache after each flush. So the current AR will communicate
unnecessarily with 100 non CARs. Depending on the size and frequency of capabilities
exchanged you do have an unnecessary burden on the ARs. You will never be able
to detect this and yet keep exchanging messages between non-CARs.

Another point, by flipping a coin as you suggest
based on the number of MNs reporting, and removing the cache entry, you have a non-zero probability
of (1 - 1/ n_{good MNs} ) that the cache entry is removed. This policy therefore has the chance that you
keep relying on the server, thus increasing the average response time. 
Instead with a better scheme to reduce the possibility of incorrect cache entries along with lifetimes
 to remove bad entries may be a better approach. I'm not saying that this is a bad
cache replacement scheme yet but I'll think about this tomorrow.

-Govind.
_______________________________________________
Seamoby mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/seamoby

---

From: "James Kempf" <[email-masked]>
Date: Thu, 13 Mar 2003 20:09:27 -0800

> scheme involving protecting the cache works in either of the proposed
solutions.

Why do you say it assumes the server approach? The AAPL could be programmed into
the router through a Web page. It doesn't have to come from a server. Something
like the AAPL will even be needed in Dycard, else how does a router know that an
access point connected to it is authorized?

> of entries?

Right, the assumption here is that the probability of an attack decreases
according to the number of MNs involved. Remember, for an MN to even get on the
link, it must be auth/authz-ed. So, multiple MNs means a bunch of the operator's
authorized customers decided to get together and attack. Maybe not such a
completely outlandish idea these days, but a much lower probablity event than
one lone customer who is having a bad day and decides to cause some mischief.

>Also, they might not be removed from the cache. More such entries and more
> the possibility of reporting a large number of such non-GAAPs.

Why do you assume the server scheme? The cache state would need to be timed out
for Dycard as well.

>Consider this scenario,
> 10 malicious MNs each report say 100 genuine non-GAAPs.

If I, as an operator, have 10 malicious customers, then I'm pretty bad off.
After that attack, they get their service cancelled forthwith.

>Also assume that

OK, so its a hundred. How big is a cache entry? Let's be conservative and say
it's 1K (actually, it's probably a lot smaller). that's still only 100K. Given
Moore's law, that costs nothing.

The point is, it's not a million. The attack becomes less probable and easier to
detect the more entries.

It is all a matter of matching the threat. The highest probability threat, in
this case, is a single MN having a bad day and deciding to try some mischief.
Now if an average MN reports, say 2 or three APs and suddenly the router starts
to get a report of 100, it knows something is amiss. If 10 MNs each start
reporting 100, it's time to call the Department of Homeland Security. :-)

> cache replacement scheme yet but I'll think about this tomorrow.

Sure. There are always false positives. But typically any one GAAP will be seen
by more than one MN. And, there are other ways to reduce the probability of
flushing good entries, for example, using a weighed moving average of reports.
That way, if the cell suddenly empties out after having been full, the cache
entries will stick around for a while.

                jak

---

From: "James Kempf" <[email-masked]>
Date: Thu, 13 Mar 2003 20:09:27 -0800

jak