[Swan-dev] a better unified proposal matcher

[Andrew Cagney]

I've finally got something concrete (think proof-of-concept :-) to discuss ...

The premise was is that the current code selecting the crypto-suite
from an SA proposal payload was too slow.  For instance, using some
very rubbery math and assuming a 2K payload only containing an SA
proposal:

-> 2K SA payload
-> 200 transforms (approx 2K / 8 bytes-per-transform)
-> 50 transforms of each type (assuming 4 types)
-> 50^4 proposal combinations
=  6 250 000 inner loop iterations

if the then assume our end is as bad (while ~32 combinations is more
realistic, this does make for big numbers:-)

-> 50^4*50&4
-> 40 000 000 000 000 inner loop comparisons

a more realistic number is 200 000 000 iterations.

On 2 March 2015 at 10:17, Andrew Cagney <andrew.cagney at gmail.com> wrote:
> On 1 March 2015 at 22:04, Paul Wouters <paul at nohats.ca> wrote:
>> On Fri, 27 Feb 2015, Andrew Cagney wrote:
>>
>>> By bits I'm guessing you mean the different transform types: ENCR,
>>> INTEG, PRF, DH, ...
>>
>>
>> Yes.
>>
>>> The critical change is to not do any combinatory explosion at all.
>>> Instead just go through the transforms once; and look at each
>>> independently.
>>
>>
>> Sure, but you have to do that per received proposal set, which are sent
>> in order of preference by the sender.
>
> Yes, agreed, I see no way out of doing:
>
> for proposal in received proposals
>     [set up for proposal]
>     for transform in proposal
>         match transform against local proposals
>     [did the proposal get a match?]

I've reached the proof-of-concept stage (there's a branch lurking
somewhere containing this; run a test then look for XXX: in the logs),
which consists of:

- a table of proposals, within each proposal the transforms are grouped by type:

    local_proposals[nr-proposals][nr-transform-types] = {
        {
            [ENCR] = { aes-gcm-256, aes-gcm-128, ... }
            [PRF] = { sha1, sha2, ... }
            [DH] = { modp2048, ... }
        },
        .....
    }

- an  "inline" matcher function:

    do
        read remote_proposal
        matched[nr-local-proposals][nr-transform-types] = zero
        while more-remote-transforms-in-proposal
            read remote_transform
            for local_proposal in local_proposals
                if matched[local_proposal][remote_transform.type]
                    continue
                if local_proposal[remote_transform.type] == remote_transform
                    matched[local_proposal][remote_transform.type] = "yes"
        for local_proposal in local_proposals
            if all required matched[local_proposal]
                return "matched"
    while more-remote-proposals
    return no-match

worst case, this code takes 200*200 == 40 000 transform comparisons,
and more realistically something like 6 000 comparisons worst case

While there's still lots too do, there are several interesting
immediate results:

- the code can stop parsing the payload on first match - i.e,  does
_not_ need to parse/verify the entire payload (my prototype doesn't
:-)
- generating an SA payload from the local_proposal table should be
straight forward (and more compact)
- I'm finding it simpler then the old ikev2_spdb_struct.c code (this
is most likely because it doesn't yet contain all the hairy edge
cases)

Next steps are:

- clean up the data structure and code (can the local proposal table
contain "struct ike_alg" pointers? don't use dynamic arrays)
- using the result of the match
- dealing with a user-defined list of proposals (this could be a
stumbling point)
- having ESP, EH use this code
- deleting the old code
- see if I found another compiler bug

Andrew