Subject: Re: a question on SPP draft ...

From: Matthew Condell <[email-masked]>
Date: 26 Apr 2001 12:41:02 -0000

Sami,

> Most IPsec/IKE implementations rely on an ordered list of
> IPsec policies for policy matching.  Is there an efficient
> method of converting the decorrelated representation into
> an (efficient) ordered list, that only requires 'standard'
> selectors (ie no exclusion lists or such)?

We don't have an algorithm for converting the decorrelated
representation into a correlated version, however, I don't understand
why that is necessary.  Decorrelated policy rules do not have to be
represented using an exclusion list, it's just easier to write it that
way when doing it by hand.  For example, !10.0.0.0/8 is equivalent to
the inclusive list of ranges: 
0.0.0.0 - 9.255.255.255, 11.0.0.0 - 255.255.255.255 

In terms of searching, a set of decorrelated policies _can_ be used as 
an ordered list for SPD lookups. It's just a list of policy rules that
have the same meaning no matter what order they are in.

Does this address your concerns?

Matt

---

From: "Sami Vaarala" <[email-masked]>
Date: Fri, 27 Apr 2001 09:36:13 +0300

Matthew,

> the inclusive list of ranges:

I realize this, but this would seem to be less efficient than checking
against an ordered list.  Or am I mistaken?

Eg. the correlated, ordered list:
    1. 10.0.0.0/8 -> 10.0.0.0/8
    2. 0.0.0.0/0   (catch all)

turns into the decorrelated
    1. 10.0.0.0/8 -> 10.0.0.0/8
    2. 0.0.0.0-9.255.255.255 OR 11.0.0.0-255.255.255.255

If I am using the decorrelated version and I have already checked step
1, the range checking is redundant.  I would like to optimize this
redundancy from the policy checking that is actually used.

In addition, when doing an IKE negotiation to establish SAs that
these policies require, the correlated (2) is negotiable whereas
the decorrelated (2) is not (IKE does not, currently, support
unions of ranges for instance).

IKE will be undergoing changes in the near future, but from what
I understood from the WG charter, the work should be in line with
the current IPsec RFCs.

-S

---

From: Greg Troxel <[email-masked]>
Date: 27 Apr 2001 09:24:30 -0400

For a list of size two, you are arguably correct, but the CPU time for
such a small list is unlikely to matter.  For an ordered list with n
entries, the search time is \theta(n).  With a decorrelated SPD, one
can use tree search algorithms, which should operate in log time.
Note that a given ordered SPD may result in more decorrelated entries
(2 to 3, above), so this broad linear-vs-log claim is somehat unfair
and I don't claim to have fully substantiated the point I'm making.

That said, if one has hardware that searches ordered SPDs efficiently,
it might be useful to have a "recorrelation" algorithm.  The
decorrelated example above has many possible recorrelated examples,
including the original, but also (dropping the RHS):

     1. 0.0.0.0/5
     2. 8.0.0.0/7
     3. 10.0.0.0/8
     4. 11.0.0.0/8
     5. 12.0.0.0/6
     6. 16.0.0.0/4
     7. 32.0.0.0/3
     8. 64.0.0.0/2
     9. 128.0.0.0/1

This recorrelation doesn't appear useful; the needed approach is
probably to identify ranges that if pulled out allow coalescing of
larger blocks.

        Greg Troxel <[email-masked]>

---

From: "Sami Vaarala" <[email-masked]>
Date: Fri, 27 Apr 2001 17:03:12 +0300

Greg,

>   Eg. the correlated, ordered list:

You are right, the decorrelated representation does have several
advantages, and I think it is a valuable concept in many ways.

> including the original, but also (dropping the RHS):
[snip]

This is actually the point I am more concerned about.  For IPsec without
IKE, the fact that there are several recorrelated ordered policies is
not a problem.  However, with IKE in the picture things get more
complicated,
since IKE also negotiates traffic selectors, and does not only compare the
selectors of a single packet.

For instance, an offer for protecting 0.0.0.0/0 using a tunnel mode
is accepted by the ordered policy (supposing the action is to use
tunnel mode, etc).  For the decorrelated (and differently recorrelated)
examples this is not so simple.  How should this work?

-Sami