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 _______________________________________________ Swan-dev mailing list Swan-dev@lists.libreswan.org https://lists.libreswan.org/mailman/listinfo/swan-dev