[Swan-dev] a better unified proposal matcher

[Andrew Cagney]

Forgive what is something of a brain dump.  I'd like to get what I've
noticed out there so we can figure out a solution.  My complexity
calculations are hopefully not too far off base.

I should also disclose a conflict of interest.  I'm less interested in
a better proposal matcher, and more interested in a unified proposal
matcher (so I can match ESP with D-H for instance).  So I'm
approaching the algorithm side from the pov of good enough for now.

Ref: http://tools.ietf.org/html/rfc7296#page-77

--

First lets look at what is currently happening.  Lets just ignore edge
cases and how not all combinations are valid :-)  The initiator sends
us a list of proposals.  Each containing 0 or more transforms of the
form:

   ENCR
   PRF
   DH
   INTEG
   ESN

from that proposal you can derive a sequence of combinations:

   ENCR(1) + PRF(1) + DH(1) + INTEG(1) +ESN(1)
   ENCR(1) + PRF(1) + DH(1) + INTEG(1) +ESN(2)
   ....
   ENCR(nr_i_encr) + PRF(nr_i_prf) + INTEG(nr_i_integ) + ESN(nr_i_esn)

i.e., there are (Initiator, Proposal 1, nr ...):

   i_p1_nr_encr * p1_nr_prf * i_p1_nr_integ * i_p1_nr_esn

combinations.  That's a lot.

Similarly, on the responder end (pluto), we've the same structure (ok,
I lie, more on that later) which gives us (responder, proposal 1, nr
...):

    r_p1_nr_encr * r_p1_nr_prf * r_p1_nr_integ * r_p1_nr_esn

combinations to compare against.  This leads to our current
implementation just matching the first initiator proposal with the
first responder proposal requires:

   (i_p1_nr_encr * i_p1_nr_prf * i_p1_nr_integ * i_p1_nr_esn) *
(r_p1_nr_encr * r_p1_nr_prf * r_p1_nr_integ * r_p1_nr_esn)

put that into a for loop:

   for each initiator proposal:
       for each responder proposal:
           do above

(perhaps I'm exaggerating slightly :-)  Which is badly polynomial.  If
I assume that the evil initiator made everything a very large N, while
our end has very small values (or perhaps just 1).  I get something
like:

   O(N^5)

(Since some combinations are not valid, it is probably O(N^4).  (If
everything is bad it goes up to O(N^10)  At least it isn't exponential
:-)

--

Fortunately, several characteristics of the protocol let us be
slightly more efficient:

- each transform type can be compared separately
- (less important) ordering is important - we can stop once we've got
a match of a transform type

This gives us a second approach.

Ahead of time:

- the responder (us), for each proposal set, and for each transform
type, builds a lookup structure (lets assume it is O(n) where n << N).

Then the initiator's proposal is processed something like:

for each initiator proposal
  for each responder proposal
    for each initiator transform
      if we've not got a match for this transform type
        look it up and if valid save it

processing each initiator vs responder proposal then takes roughly:

    (nr_i_encr + nr_i_prf + nr_i_integ + nr_i_esn) * O(n)

Assuming nr-initiator-proposals ==
nr-initiator-transforms-per-proposal == N, and n<<N and
nr-responder-proposals << N, we get roughly:

   O(N^2)

At this point, it is worth explaining the "lie" I mentioned above and
why I specified O(n) and not O(1).

Currently, at least for IKE, be it the default proposal, or a custom
proposal, pluto (for v2) doesn't exploit transforms - each proposal
only contains one element of each type.  Consequently, there's no need
for an O(1) lookup table.  Even if there were multiple transforms of
each type, the number would be small so again an O(1) structure
wouldn't make much difference.  Our total number of proposals is also
relatively small (~24) so the above is going to be dominated by the
initiator so reducing it to O(N^2)

My instinct, given I just desperately want a unified sa proposal
matcher, is to stop here and first implement this - while it might
still be dumb, at least it isn't stupid :-)
(We've also got enogh other deck chairs that will need shuffling
without trying to implement something more complicated as part of a
first pass).

--

This leads us to the question of can things be got down to O(N).  Some
O(1) structure that maps a transform onto the proposals thats that
contain that transform might do it leading to (suite is a single
combination of ENCR, PRF, ...):  Something like:

  for each initiator proposal in initiator proposals
    for each initiator transform in initiator proposal transforms
      for each responder proposal in
responder_proposals_containing_transform(initiator transform)
        suite = suite for responder proposal
        if suite does not contain initiator transform type
          add it
        (optional) if suite is #1 and full
          bail
  look for first suite that is fully matched

but this is idle speculation

Andrew