Never post before lunch, or coffee, here are better O() guesses:
On 24 February 2015 at 12:07, Andrew Cagney <[email protected]> wrote:
> 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
r_p1_nr_encr * r_p1_nr_prf * r_p1_nr_integ * r_p1_nr_esn * r_p1_nr_dh
but there's a table saying at most 4 of those are valid
>
> 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)
It is probably O(N^4):
Given a payload with M transforms split evenly between 4 different
transform types then:
(M/4)^4
is the max combinations. If there's more than one proposal, that
leads to O((M/5)^4) which is smaller.
For our end, it is arguably just small constant (24 for PSK), or
perhaps a large constant.
> (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
> :-)
So O(N^8) or O(10) isn't true. From the pov of the attacker, it is
still just O(N^4), just with a bigger constant out front.
>
> --
>
> 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)
Actually, this is just:
O(N)
where N is the total number of transforms in the payload. How those
transforms are spread amongst proposals doesn't matter.
Our end is just a constant (the magnitude of which is determined by
the number of our proposals) - the initiator can't control that.
Further the below ....
> 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
which is just:
O(N)
where N is again the total number of transforms in payload. Just
reduces the size of the constant (the cost of processing each
transform). It doesn't reduce the complexity.
(this goes back to my argument that the middle option is probably good
enough for now :-)
> but this is idle speculation
>
> Andrew
_______________________________________________
Swan-dev mailing list
[email protected]
https://lists.libreswan.org/mailman/listinfo/swan-dev
